반응형 Computer Science63 프림 알고리즘(Prim Algorithm) 이번에 배워볼 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 같이 최소 비용 신장 트리(MST)를 구하는 프림 알고리즘(Prim Algorithm)이다. 크루스칼 알고리즘은 간선 선택을 기반으로 하는 알고리즘이었다면, 프림 알고리즘은 정점 선택을 기반으로 하는 알고리즘이다. 또한, 크루스칼 알고리즘은 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이라면, 프림 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장하는 방식이다. 프림 알고리즘은 그리디 알고리즘에 속한다. 그 이유는 추가할 새로운 정점을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다. 프림 알고리즘의 동작 원리는 다음과 같다. 시작 정점을 선택한다. 현재 구성된 신장 트리에 속.. 2021. 7. 4. 크루스칼 알고리즘(Kruskal Algorithm) 최소 비용 신장 트리(MST)를 구하는 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim Algorithm)이 존재한다. 이번에 배워볼 알고리즘은 이전에 배운 합집합 찾기(Union Find)에서 언급한 크루스칼 알고리즘(Kruskal Algorithm)이다. 크루스칼 알고리즘은 그리디 알고리즘이라고 불린다. 그 이유는 추가할 새로운 간선을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다. 우선 크루스칼 알고리즘을 배우기 전에 신장 트리가 무엇인지에 대해서 알고 넘어가자. 신장 트리란 그래프 내의 모든 정점을 포함하는 트리를 뜻한다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안 된다. 따라서 신장 트리는 .. 2021. 7. 4. 합집합 찾기(Union Find) 이번에 배워볼 알고리즘은 합집합 찾기(Union Find) 알고리즘이다. 서로소 집합(Disjoint Set) 알고리즘이라고도 불리는 이 알고리즘은 그래프 상의 두 개의 노드가 같은 그래프에 속하는지를 판별하기 위해 사용되는 알고리즘이다. 다음에 배울 최소 비용 신장 트리(MST)를 구성하는 알고리즘 중 하나인 크루스칼(Kruskal) 알고리즘이 합집합 찾기 알고리즘을 응용한 알고리즘이다. 합집합 찾기 알고리즘의 원리는 다음과 같다. 자신의 부모 노드를 저장하는 1차원 배열을 선언 후 각 정점의 부모를 자신을 가리키도록 초기화한다. 두 개의 노드를 선택하여 Union 연산을 수행하면 두 개의 노드의 부모를 하나의 노드로 통일한다. 이때 더 작은 번호를 가리키도록 부모를 통일한다. 두 개의 노드를 선택.. 2021. 7. 3. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 이번에 배워볼 알고리즘은 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이다. 이전에 배운 다익스트라, 벨만-포드 알고리즘은 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 플로이드 워셜 알고리즘은 벨만-포드 알고리즘처럼 음의 간선이 존재하여도 모든 최단 경로를 구할 수 있다. 물론 음의 사이클이 존재하면 불가능하다. 또한, 이전에 저장해놓은 최단 경로를 이용해서 새로운 최단 경로로 갱신하는 과정에서 플로이드 워셜 알고리즘 역시 다이나믹 프로그래밍이라고 할 수 있다. 플로이드 워셜 알고리즘의 핵심은 간단하다. 이전에 다익스트라나 벨만 포드 알고리즘에서 정점 A에서 정점 C까지 가.. 2021. 7. 3. 벨만-포드 알고리즘(Bellman-Ford Algorithm) 이번에 배워볼 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘 또한 이전에 배운 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다. 벨만 포드 알고리즘이 다익스트라 알고리즘보다 시간이 오래 걸리는 이유는 다익스트라는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 경우의 수를 줄여가며 비용을 갱신하였다. 하지만 벨만 포드 알고리즘.. 2021. 7. 3. 다익스트라 알고리즘(Dijkstra Algorith) 이번에 배워볼 알고리즘은 그래프에서 최단 경로를 찾기 위한 알고리즘 중 하나인 다익스트라 알고리즘(Dijkstra Algorith)이다. 다익스트라 알고리즘은 한 정점에서 나머지 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 단, 그래프 내에 음의 간선(경로)이 존재한다면 다익스트라 알고리즘을 적용할 수가 없다. 다익스트라 알고리즘은 다이나믹 프로그래밍, 그리디 알고리즘으로 분류된다. 이전에 구했던 최단 경로 정보를 이용하기 때문에 다이나믹 프로그래밍이라고 불리며, 가장 최단 경로인 간선을 선택하기 때문에 그리디 알고리즘이라고 불린다. 다익스트라 알고리즘의 동작원리는 다음과 같다. 시작 정점을 선택한다. 시작 정점을 기준으로 다른 정점으로 가는 비용을 저장한다. 현재 방문하지 않는 정점.. 2021. 7. 3. 너비 우선 탐색(Breadth First Search) : BFS 이번에 배워볼 알고리즘은 너비 우선 탐색(Breadth First Search)이다. 줄여서 흔히 BFS라고 부른다. 깊이 우선 탐색은 깊이를 우선시하였다면 너비 우선 탐색은 너비를 우선시하는 탐색 방법이다. 또한, 노드에서 다른 노드로 가는 최단 경로를 구할 때 깊이 우선 탐색은 한 노드의 끝까지 탐색하기 때문에 최단 경로를 보장해 주지 않지만 너비 우선 탐색은 항상 같은 깊이 내에 있는 모든 노드들을 탐색하기 때문에 최단 경로를 보장해 준다는 장점이 있다. 깊이 우선 탐색은 스택(Stack)을 이용하여 구현하였다면, 너비 우선 탐색은 큐(Queue)를 이용해서 구현한다. 너비 우선 탐색의 원리는 다음과 같다. 큐에서 노드 하나를 꺼낸다. 큐에서 꺼낸 노드에 인접한 노드들 중 아직 방문하지 않은 .. 2021. 7. 2. 깊이 우선 탐색(Depth First Search) : DFS 그래프의 모든 정점들을 방문하는 방법은 크게 두 가지가 있다. 이번에 배워볼 알고리즘은 그중 하나인 깊이 우선 탐색(Depth First Search)이다. 줄여서 흔히 DFS라고 부른다. 이 알고리즘은 깊이 우선 탐색이란 말 그대로 깊이(Depth)를 우선순위로 두고 탐색을 하겠다는 의미이다. 깊이 우선 탐색은 스택(Stack)을 이용해서 구현한다. 또한, 컴퓨터는 구조적으로 함수를 호출할 때 스택의 원리를 이용하기 때문에 스택을 선언하여 사용하지 않고 재귀적 함수 호출로 구현할 수도 있다. 필자는 재귀적인 구현이 훨씬 간단하고 직관적이기 때문에 보통 재귀적으로 구현을 많이 하는 편이다. 다만, 과도한 재귀 함수 호출은 스택에 함수가 계속 쌓이게 되면서 메모리에 많은 부담을 주기 때문에 이런 경우는 .. 2021. 7. 2. Lower_bound & Upper_bound 이전에 배운 이분 탐색(Binary Search)은 리스트 내에 찾고자 하는 Key 값이 있을 때만 위치를 반환하고 만약 Key 값이 존재하지 않는다면 아무것도 반환을 하지 않았다. 또한, Key 값이 중복된 경우 정확히 우리가 원하는 Key의 위치를 얻을 수가 없었다. 따라서 Key 값이 존재하지 않더라도 Key에 가장 가까운 원소의 위치를 찾아야 하거나, 중복된 Key 값의 범위, 중복 값을 활용하는 등의 문제를 해결하기 위해선 이분 탐색은 한계가 있다. 이를 위해 이분 탐색을 응용한 두 개의 알고리즘이 존재한다. 당연한 말이지만 이분 탐색을 응용하는 알고리즘이기 때문에 리스트는 정렬이 되어있어야 한다. 첫 번째는 Lower_bound라는 알고리즘이다. Lower_bound는 하한선이라는 뜻으로 .. 2021. 7. 2. 이전 1 2 3 4 5 6 7 다음 반응형
