공부한 내용 기록하기 공부한 내용 기록하기

1. 플로이드-워셜 알고리즘이란?플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘이다. 그래프의 각 정점에서 다른 모든 정점까지의 최단 경로를 효율적으로 계산하며, 음수 가중치를 허용하지만 음수 사이클이 존재하는 경우에는 사용할 수 없다.이 알고리즘은 동적 계획법(Dynamic Programming)을 기반으로 하며, 각 정점을 경유지로 활용해 최단 경로를 점진적으로 갱신한다.1.1 플로이드-워셜 알고리즘의 특징모든 정점 쌍의 최단 경로를 구함음수 가중치 허용 (음수 사이클은 감지 불가)동적 계획법을 활용한 최단 경로 갱신시간 복잡도: O(V³) (V는 정점의 수)2. 플로이드-워셜 알고리즘의 동작 원리플로이드-워셜 알고리즘은 다음과 ..

1. 벨만-포드 알고리즘이란?벨만-포드 알고리즘(Bellman-Ford Algorithm)은 가중치 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 유사하지만, 음수 가중치를 포함한 그래프에서도 동작한다.이 알고리즘은 그래프의 모든 간선을 여러 번 확인하며 최단 경로를 반복적으로 갱신하는 방식으로 동작한다. 특히 음수 가중치를 처리할 수 있으며, **음수 사이클(Negative Cycle)**이 있는지도 판별할 수 있다.1.1 벨만-포드 알고리즘의 특징음수 가중치 허용: 음수 가중치를 포함한 그래프에서 사용 가능음수 사이클 탐지: 음수 가중치의 무한 루프 발생 여부 확인 가능시간 복잡도: O(V × E) (V는 정점 수, E는 간선 수)2. 벨만-포드 알..

1. 다익스트라 알고리즘이란?다익스트라 알고리즘(Dijkstra's Algorithm)은 양수 가중치를 가진 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.1.1 다익스트라 알고리즘의 특징비용 최소화: 출발점에서 각 정점까지의 최소 비용 경로 탐색양수 가중치 그래프에서 사용 가능: 음수 가중치는 허용되지 않음우선순위 큐 사용 시 효율적: 시간 복잡도 O((V + E) log V)2. 다익스트라 알고리즘의 동작 원리다익스트라 알고리즘은 다음과 같은 단계로 동작한다:초기화:출발 노드의 거리를 0으로 설정하고, 나머지 노드는 무한대로 초기화방문하지 않은 모든 노드를 저장하는 우선순위 큐 생성최단 경로 갱신:현재 노드에서 인접한 노드로 가는 비용을 계산계산한 비용이 기존 값보다 작으..

1. 그래프 알고리즘이란?그래프 알고리즘(Graph Algorithms)은 **정점(Vertex)**과 **간선(Edge)**으로 이루어진 그래프 구조에서 경로를 찾거나 연결 관계를 분석하는 데 사용되는 알고리즘이다. 그래프는 다양한 관계와 연결을 표현할 수 있어 네트워크 분석, 지도 경로 탐색, 데이터 연결 구조 분석 등에서 중요한 역할을 한다.1.1 그래프의 기본 요소정점(Vertex): 그래프에서의 노드(Node)간선(Edge): 정점 간의 연결무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프방향 그래프(Directed Graph): 간선에 방향이 있는 그래프가중 그래프(Weighted Graph): 간선에 가중치(Weight)가 부여된 그래프1.2 그래프의 표현 방법인접 ..

1. 삼진 탐색이란?삼진 탐색(Ternary Search)은 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘으로, 탐색 범위를 세 부분으로 나누어 진행한다. 이진 탐색(Binary Search)이 탐색 범위를 두 부분으로 나누는 것과 달리, 삼진 탐색은 탐색 범위를 세 부분으로 나누기 때문에 비교 횟수를 줄일 수 있다.삼진 탐색은 이진 탐색과 유사하지만, 각 단계에서 두 개의 중간점을 확인한다는 점이 차별화된다. 주로 범위가 넓고 정렬된 배열에서 빠른 탐색이 필요할 때 사용된다.2. 삼진 탐색의 동작 원리삼진 탐색은 다음과 같은 과정으로 수행된다:탐색 범위의 첫 번째와 두 번째 중간점을 계산한다.목표 값을 중간점들과 비교한다.목표 값이 첫 번째 중간점보다 작으면 왼쪽 구간 탐색목표 값이 두 중간점 사이에 ..

1. 이진 탐색 트리(BST) 탐색이란?이진 탐색 트리(Binary Search Tree, BST) 탐색은 이진 탐색 트리 구조에서 특정 값을 찾는 알고리즘이다.이진 탐색 트리는 다음과 같은 특성을 가진다:각 노드의 왼쪽 서브트리에 있는 모든 값은 해당 노드의 값보다 작다.각 노드의 오른쪽 서브트리에 있는 모든 값은 해당 노드의 값보다 크다.이러한 구조를 활용해 데이터를 정렬된 상태로 유지하며 효율적인 탐색을 가능하게 한다.이진 탐색 트리 탐색은 평균적으로 O(log n)의 시간 복잡도를 가지며, 최악의 경우 O(n)의 시간 복잡도를 가진다.2. 이진 탐색 트리 탐색의 동작 원리이진 탐색 트리 탐색은 다음과 같은 절차로 이루어진다:루트 노드에서 시작한다.현재 노드의 값과 찾고자 하는 값을 비교한다.찾는 ..

1. 너비 우선 탐색이란?너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리를 탐색하는 대표적인 방법 중 하나로, 시작 노드에서 가까운 노드를 먼저 탐색한 후, 점차 더 깊은 노드를 탐색하는 방식으로 동작한다.BFS는 큐(Queue, 선입선출 구조)를 활용하며, 최단 경로 탐색, 네트워크 분석, 퍼즐 해결 등 다양한 분야에서 사용된다.2. 너비 우선 탐색의 동작 원리BFS는 다음과 같은 과정으로 수행된다:시작 노드를 큐에 삽입하고 방문 처리를 한다.큐에서 노드를 하나 꺼내고, 해당 노드와 연결된 모든 인접 노드를 확인한다.인접 노드 중 아직 방문하지 않은 노드를 큐에 삽입하고 방문 처리를 한다.큐가 빌 때까지 2번과 3번 과정을 반복한다.2.1 너비 우선 탐색 과정 예제다음과..

1. 깊이 우선 탐색이란?깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리를 탐색하는 대표적인 방법 중 하나로, 특정 경로를 따라 최대한 깊이 내려간 후 더 이상 진행할 수 없으면 되돌아가면서 미탐색 노드를 방문하는 방식으로 동작한다.DFS는 스택(LIFO: 후입선출) 구조를 활용하며, 재귀 호출이나 명시적인 스택 자료구조를 사용해 구현할 수 있다.2. 깊이 우선 탐색의 동작 원리DFS는 다음과 같은 과정으로 수행된다:시작 노드를 방문하고 방문 표시를 한다.현재 노드에서 인접한 노드를 차례대로 탐색한다.아직 방문하지 않은 노드가 있다면 해당 노드로 이동하고 위 과정을 반복한다.더 이상 방문할 노드가 없으면 이전 노드로 되돌아간다.2.1 깊이 우선 탐색 과정 예제다음과 같은 그래..