[Algorithm] 최단 경로 - 플로이드-워셜 알고리즘
* Python을 기준으로 합니다 최단 경로 - 플로이드-워셜 (Floyd-Warshall) 알고리즘 - 개념 플로이드-워셜 알고리즘 : 최단 경로를 구하는 알고리즘 중 하나로, 존재하는 모든 노드에서 다른 노드로의 최단 경로를 모두 계산해야 하는 경우 사용함 다익스트라와 달리 플로이드-워셜은 한 지점에서의 최단 경로가 아닌 모든 노드로의 경로를 반환함 - 이때 벨만-포드와 비슷하게 음의 가중치가 있는 경우에서도 사용가능 하지만, $O(n^{3})$의 time complexity를 소모하는 단점이 있음 플로이드-워셜 알고리즘은 다이나믹 프로그래밍으로써 구현되고, 다음의 점화식을 가짐: (Eq. 1) $D_{ab} = \min(D_{ab}, D_{ak}+D_{kb})$ - 시작 노드 $A$에서 노드 $K$..
[Algorithm] 최단 경로 - 벨만-포드 알고리즘
* Python을 기준으로 합니다 최단 경로 - 벨만-포드 (Bellman-Ford) 알고리즘 - 개념 벨만-포드 알고리즘 : 최단 경로를 찾는 알고리즘 중 하나로, 매 단계마다 모든 간선의 가중치를 확인하여 최단 거리를 갱신하는 방식으로 동작함 다익스트라와 달리 음의 가중치를 가지는 그래프에서도 동작 가능 벨만-포드 알고리즘의 동작 시작 노드를 선정하고, 최단 거리 테이블을 시작 노드는 0 나머지 노드는 최대값 INF로 초기화 아래 과정을 노드 개수 -1 만큼 반복 - 현재 노드에서 갈 수 있는 각 노드들에 대해, 전체 노드 각각을 거쳤을 때 더 짧은 최단 거리가 있는지 확인 - 더 짧은 최단 거리가 있다면 최단 거리 테이블을 갱신 위 과정을 한번 더 수행하여 갱신되는 최단 거리가 있는지 확인 - 있다..
[Algorithm] 최단 경로 - 다익스트라 알고리즘
* Python을 기준으로 합니다 최단 경로 - 다익스트라 (Dijkstra) 알고리즘 - 개념 다익스트라 알고리즘 : 그래프의 최단 경로를 찾기 위한 알고리즘 중 하나로, BFS를 기반으로 가장 비용이 적은 노드만을 선택하는 그리디 방식으로 동작함 그래프에서 간선의 가중치가 모두 양수라는 조건하에서 사용 가능함 - 다익스트라 알고리즘은 각 노드에 대한 최단 거리를 배열 저장하고 계속 갱신한다는 특징이 있음 다익스트라 알고리즘의 동작 과정 시작 노드를 설정하고, 최단 거리를 저장할 배열을 매우 큰 값(INF)으로 초기화함 방문하지 않은 노드 중에서 가장 최단 거리(최소 비용)를 가진 노드를 선택함 해당 노드를 거쳐 다른 노드로 가는 최단 거리를 계산하고, 현재까지 구한 최단 거리와 비교하여 작은 값으로 ..
[Algorithm] 위상 정렬
* Python을 기준으로 합니다 위상 정렬 (Topology Sort) - 개념 위상 정렬 : 방향 비순환 그래프 (Directed Acyclic Graph, DAG)의 모든 노드를 순서대로 나열하는 것 진입차수 (Indegree) : 그래프에서 특정 노드를 가리키는 간선의 개수 위상 정렬의 동작 진입차수가 0인 노드를 큐에 push 큐에서 노드를 pop 하면서, 인접 노드의 진입차수를 1씩 줄임 이후 진입차수가 0이 된 노드를 큐에 push 위 2~3번 과정을 큐가 빌 때까지 반복 위상 정렬의 동작 과정에서 모든 노드들을 방문하기 전에 큐가 비어지면, cycle이 존재하는 것으로 볼 수 있음 - Cycle이 존재하는 경우 어떠한 노드도 큐에 push 되지 못하기 때문 - BUT, 일반적으로 위상 정렬..
[Algorithm] DFS, BFS
* Python을 기준으로 합니다 DFS (Depth-First Search), BFS (Breadth-First Search) - 개념 DFS (깊이 우선 탐색), BFS (너비 우선 탐색) : 그래프의 모든 노드를 한 번씩 방문하는 그래프 순회 작업을 위한 알고리즘 완전 탐색과 같이 탐색 방향을 결정하고, 다음 탐색의 유효성을 검사해야 하는 경우 사용 방문 처리 : 그래프에서 한번 처리되어 탐색된 노드가 다시 탐색되지 않게 체크하는 과정 DFS : 스택, 재귀로 주로 구현됨 그래프에서 더 이상 탐색할 노드가 없을 때까지 진행한 다음, 탐색할 노드가 없으면 가장 최근의 방문 노드로 돌아가 다른 노드를 탐색하는 방법 DFS의 동작 과정 스택에 시작 노드를 push 스택이 비어있다면 탐색을 종료 비어있지 ..
[Algorithm] 이진 탐색, 파라메트릭 서치
* Python을 기준으로 합니다 이진 탐색 (Binary Search), 파라메트릭 서치 (Parametric Search) - 개념 이진 탐색 : 정렬된 데이터가 있을 때, 검색 범위를 절반으로 줄여나가면서 값을 탐색하는 방식 반드시 정렬된 데이터에서만 사용 가능하지만, $O(\log n)$의 time complexity를 가짐 이진 탐색의 동작 배열의 시작점과 끝을 start, end로 정함 가운데를 mid로 정하고, mid에 해당하는 값이 탐색 값이면 탐색을 종료하고 값을 반환 mid에 해당하는 값이 탐색하려는 값보다 크면 mid의 오른쪽 배열에 대해 이진 탐색 수행, 작으면 mid 왼쪽 배열에 대해 이진 탐색 수행 위 2~3 과정을 반복 이진 탐색의 응용 - 이진 탐색은 탐색 범위를 계속해서 좁..