본문 바로가기

Algorithm

사이클 찾기: DFS 유향 그래프에서 사이클이 있는지 판단하고, 사이클에 포함되는 노드의 개수가 몇 개인지 세는 알고리즘으로 백준 알고리즘 저지의 9466번: 텀 프로젝트 문제가 이에 해당한다. 9466번: 텀 프로젝트 - Baekjoon Online Judge https://www.acmicpc.net/problem/9466 구글링만 해봐도 해당 문제에 대한 많은 풀이가 존재하지만, 아무래도 이런 로직은 내 코드로 정리하는게 제일 이해도 잘가고 나중에 봐도 이해하기 쉬울 것 같아서 풀이 위주로 정리해봤다. 문제에서는 프로젝트를 함께하고 싶은 학생을 선택하는 것이 나오는데 선택은 한명씩 하게 되있으므로, 각 노드에서 나가는 간선은 하나씩이라는 것을 알 수 있다. 주의해야할 것은 자기 자신도 선택할 수 있으므로 나가는 간선이 ..
12. 최소 공통 조상 (LCA: Lowest Common Ancestor) 최소 공통 조상은 트리구조에서 특정 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 트리구조라는 용어 자체가 생소하신 분들은 나무위키의 트리(그래프) 항목을 참고하시기 바랍니다. 트리(그래프) - 나무위키https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84) LCA(Lowest Common Ancestor) 알고리즘은 일반적으로 앞에서 이야기한 정의에 따라 가장 가까운 위치의 공통 조상을 찾는데 쓰이지만 이는 또한 두 노드의 가장 가까운 거리를 찾는다는 의미도 있기 때문에 노드간 거리를 구할 때도 사용됩니다. LCA 알고리즘은 단순하게 loop를 이용하여 공통조상을 찾는 방식과 DP나 세그먼트 트리를 이용하여 찾는 방식이 있습니다..
11. 최소 신장 트리(MST): 크루스칼 알고리즘(Kruskal's Algorithm) 최소 신장 트리 혹은 최소 스패닝 트리라고 불리는 MST(Minimum Spanning Tree)는 가중치가 포함된 무향의 그래프가 주어졌을 때, 모든 노드들이 포함되면서 비용은 최소가 되는 부분 그래프인 트리를 의미합니다. 이와 같은 조건을 만족하는 MST를 찾기위해 크루스칼 알고리즘(Kruskal's Algorithm)이나 프림 알고리즘(Prim's algorithm)을 사용합니다. 이 두가지 알고리즘은 동일한 시간복잡도를 갖고 있기 때문에 어느 알고리즘이 더 우월하다고 할 수 없으나, 크루스칼 알고리즘은 간선을 기준으로 구현되고, 프림 알고리즘은 노드 기준으로 알고리즘이 구현된다는 부분에서 차이를 갖고 있습니다. 이번에는 간선을 기준으로 한 크루스칼 알고리즘을 설명해보도록 하겠습니다. 크루스칼 알고..
10. 유니온 파인드 (Union-Find) 유니온 파인드는 앞에서 공부한 최단 경로 탐색 알고리즘과 맥락을 달리하는 그래프 문제입니다. 최단 경로 탐색 알고리즘은 여러 노드와 간선 정보가 주어졌을 때 특정 노드에서 다른 노드로 이동하는데 얼마나 적은 비용으로 이동할 수 있는지 비용을 최소화 시키는 것을 목적으로 한다면 유니온 파인드 알고리즘은 노드간 연결 관계를 파악하고 특정 간선을 연결할 시 노드 연결관계가 어떻게 변화하는지 파악하는 알고리즘입니다. 예를 들어 설명하도록 하겠습니다. 어느 나라에 여러 도시들이 있었는데 도로가 하나도 안깔려있어서 서로 단절되어 있었습니다. 도시를 연결해야겠다고 생각한 한 사람이 도시 사이에 도로를 놓기로 했습니다. 하지만 어떤 도시들 사이에는 산이 있어서 직접 도로를 못 놓는 경우도 있었기 때문에 연결이 가능한 ..
9. 최단 경로 탐색: 벨만-포드 알고리즘(Bellman-Ford Algorithm) 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 탐색 알고리즘입니다. 노드와 가중치가 포함된 간선 정보를 이용하여 시작점과 도착점 사이의 최단 거리를 찾는 것이 이 알고리즘의 목적입니다. 설명만 들어서는 다익스트라 알고리즘과 일치합니다. 하지만 기본적인 최단 경로 탐색 알고리즘의 조건과 목적에 더하여 벨만-포드 알고리즘은 특정한 조건을 포함하고 있을 때 사용됩니다. 가중치에 음수가 포함된 경우입니다. 다익스트라 알고리즘은 기본적으로 가중치가 양수와 0으로 이루어져 있다는 것을 가정하고 있습니다. 그렇기 때문에 음수 가중치가 포함되어있다고 해도 알고리즘 자체에서 음수 가중치 부분을 처리할 수 없습니다. 벨만-포드 알고리즘의 원리는 다음과 같습니다. 우리가 특정 노드에서 다른 어떤 노드로 이..
8. 최단 경로 탐색: 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 최단 경로 탐색 알고리즘중 가장 대표적인 알고리즘이라고 할 수 있습니다. 일반적으로 최단 경로 탐색 알고리즘 교육에서는 가장 첫 장으로 소개되기 마련이며, 최단 경로 탐색 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 중에서 가장 시간복잡도가 낮습니다. 하지만 모든 최단 경로 탐색 문제에 다익스트라 알고리즘을 사용할 수 있는 것은 아닙니다. 다익스트라 알고리즘의 위키백과 정의를 살펴보겠습니다. 컴퓨터 과학에서, 데이크스트라 알고리즘(=다익스트라 알고리즘)(영어: Dijkstra algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허..
7. 동적계획법(DP: Dynamic Programming)의 기초 동적계획법은 어떤 문제에서 최적해를 구해야할 때, 문제를 더이상 쪼갤 수 없는 단위로 쪼개서 제일 작은 부분부터 최적해를 누적해 나가는 방식으로 문제를 푸는 알고리즘을 의미합니다. 동적계획법이 가능한 것은 문제를 동일 형식의 연산이 반복될 수 있는 더 작은 문제로 쪼갤 수 있고, 작은 문제의 최적해를 이용해서 그보다 조금 더 큰 문제의 최적해를 도출할 수 있다는 것이 보장되기 때문입니다. 이러한 동적계획법의 풀이 방식에 근거하여 동적계획법 풀이는 크게 두가지가 핵심적으로 작동한다고 할 수 있는데 한 가지는 초기조건, 다른 한 가지는 점화식입니다. 초기조건은 말그대로 문제를 가장 작은 단위로 쪼개었을 때 연산없이 확정되어있는 최적해를 의미합니다. 동적계획법은 동일 연산을 가장 작은 크기의 문제부터 반복 적..
6. DFS와 BFS 깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breadth First Search)는 탐색방법 중 가장 기본이 되는 방식입니다. 이름에 어떠한 방식으로 탐색이 이루어지는지 압축적으로 제시된 것만큼 그 사용목적과 방법이 확실한 알고리즘이라고 할 수 있습니다. DFS는 말그대로 깊이를 우선하여 탐색하는 알고리즘입니다. 만일 격자 모양으로 구성된 하나의 그래프가 주어졌다고 생각해보겠습니다. 중간에 끊김없이 한칸한칸을 모두다 탐색해야한다고 했을 때 우리가 취할 수 있는 방법은 마치 한 손 그림을 그리듯 쭉 타고 가면서 하나씩 노드들을 방문하는 것입니다. 오른쪽으로 쭉타고 가다가 더이상 오른쪽으로 갈 수 없으면 밑으로 그리고 더이상 밑으로 갈 수 없으면 왼쪽으로 또 더이..

티스토리툴바