이 글은 각 알고리즘의 자세한 구현 방법에 초점을 맞추고 있지 않습니다.
실전에서 어떤 문제에 어떤 알고리즘을 써야하는지를 빠르게 파악하는데 초점을 맞추고 있습니다.
실전에서는 문제에 어떤 알고리즘을 써야하는지 알려주지 않습니다.
때문에 어떤 알고리즘을 써야하는지 빠르게 파악하고 불 필요한 혼란을 겪지 않는 것이 시간압박을 피하는 최고의 방법입니다.
크게 두 가지의 섹션으로 나누었습니다.
1. 그래프에서 자주 쓰이는 알고리즘의 종류와 특징을 살펴본다.
2. 각 알고리즘을 어떤 문제에 써야하는지 알아보겠습니다.
1. 그래프에서 자주 쓰이는 알고리즘의 종류와 특징을 살펴보겠습니다
1. BFS (넓이 우선 탐색) : 한 정점에서 다른 모든 정점까지의 최단거리를 계산하는 알고리즘
- 특징 : 자신 주변의 노드부터 차례차례 탐색합니다. 탐색 과정이 마치 물결이 퍼져나가듯 시작점에서부터 원 형태로 확장되는 특징이 있습니다.
- 최단 경로 조건 : 가중치가 없는 그래프. 가중치가 두 종류만으로 이루어진 경우 0-1 BFS라는 방법으로 최단 경로를 찾을 수 있습니다.
- 한계 : 세 종류 이상의 가중치가 있으면 다익스트라를 사용합니다.
- 내부 기술 : 큐
- 시간 복잡도 : O(정점 + 간선)
2. DFS (깊이 우선 탐색) : 한 정점에서 시작하여 연결된 노드를 깊게 탐색하는 알고리즘
- 특징 : 출발 지점으로 부터 더 이상 가지 못하는 지점까지 탐색한 후 다시 돌아와 탐색합니다.
- BFS와 차이점 : 최단 경로를 보장하지는 않지만, 모든 노드를 탐색하는 데 사용됩니다.
- 내부 기술 : 스택, 재귀 (재귀에는 스택의 원리가 있기 때문에 일반적으로 재귀를 사용하여 구현합니다)
- 시간 복잡도 : O(정점 + 간선)
3. 다익스트라 : 한 정점에서 다른 모든 정점까지의 최단거리를 계산하는 알고리즘
- 특징 : 그래프의 간선에 가중치가 있을 때 사용합니다. (가중치란? 코딩테스트에서 도시들 사이의 버스비나 거리의 길이를 말합니다 가중치는 일종의 개념으로 간선들이 공평하지 않게되면 어떤 것이든 가중치가 될 수 있습니다.)
- 최단 경로 조건 : 음수 가중치가 없는 그래프.
- 한계 : 음수 가중치가 있으면 최단 경로를 보장하지 못합니다. (특수한 상황에서는 가능합니다만, 음수 가중치 상황에서는 보통 벨만포드 알고리즘을 사용하는것이 실전에서 편합니다.)
- 내부 기술 : 우선순위 큐, 완화
- 시간 복잡도 : O((정점 + 간선) log 정점)
4. 벨만포드 : 한 정점에서 다른 모든 정점까지의 최단거리를 계산하는 알고리즘
- 특징 : 그래프의 간선에 음수 가중치가 있을 때 사용합니다.
- 최단 경로 조건 : 음수 사이클이 없는 그래프.
- 한계 : 음수 사이클이 있을 경우 최단 경로를 보장할 수 없습니다.
- 다익스트라와 차이점 : 다익스트라와 달리 음수 사이클의 탐지가 가능합니다.
- 시간 복잡도 : O(정점 * 간선)
5. 플로이드워셜 : 모든 정점에서 다른 모든 정점 사이에 최단거리를 계산하는 알고리즘
- 특징 : 그래프의 간선에 음수 가중치가 있어도 최단 경로를 보장합니다.
- 최단 경로 조건 : 음수 사이클이 없는 그래프
- 한계 : 음수 사이클이 있을 경우 최단 경로를 보장할 수 없습니다. 음수 사이클의 탐지는 가능합니다.
- 사용 기술 : 완화, 동적 계획법 (DP) (DP 점화식에 완화의 개념이 내장되어있습니다.)
- 시간 복잡도 : O(정점^3)
6. 유니온파인드 : 어떠한 원소가 같은 집합에 속하는지 알아내고 두 집합을 합치는 알고리즘
- 특징 : 연결성과 집합 관리에 쓰입니다. Union(합치기), Find(찾기) 두 개의 함수로 이루어진 알고리즘 입니다.
- 활용 : 두 원소가 같은 그룹에 속하는지 판별, 여러 원소들이 어떻게 연결되어 있는지 판별, 그래프에 사이클이 존재하는지 판별, 최소 신장트리의 크루스칼 알고리즘의 핵심 부품
- 내부 기술 : 트리 기반의 서로소 집합 (트리, 부모 포인터 방식)
- 최적화 기술 : 경로 압축, 랭크 기반 합치기
- 시간 복잡도 : 최적화 적용하지 않은 경우 : O(N), 최적화 적용한 경우 : O(1)
시간 복잡도 순위
(빠름) 유니온파인드 < BFS = DFS < 다익스트라 < 벨만포드 < 플로이드워셜 (느림)
2. 각 알고리즘을 어떤 문제에 써야하는지 알아보겠습니다.
1. 한 정점에서 다른 정점까지의 최단경로를 계산해야하는 문제
결론
1단계 : BFS 씁니다 (백준 2178 (미로탐색))
.... 앗!!! 그런데 가중치가 있네
2단계 : 다익스트라 씁니다. (백준 1753 (최단경로))
.... 앗!! 그런데 가중치가 음수잖아
3단계 - 벨만포드 씁니다. (백준 11657 (타임머신))
1. 왜 이렇게 써야할까요??
시간 복잡도 문제
시간 복잡도가 BFS - 다익스트라 - 벨만포드 순으로 빠릅니다
BFS의 시간복잡도는 O(정점+간선) 으로 모든 정점과 간선을 한 번씩만 방문하므로 거의 선형 시간에 가깝게 동작합니다.
다익스트라의 시간복잡도는 O((정점 + 간선) log 정점) 으로 로그시간 복잡도를 가집니다.
벨만포드의 시간복잡도는 O(정점 * 간선) 으로 정점과 간선이 많을 수록 느려지고 다른 두 알고리즘에 비해서 가장 느립니다.
알고리즘 구현 난이도 차이
BFS는 내부적으로 큐를 사용하여 가장 간단합니다.
또한 다익스트라와 벨만포드는 완화(relaxation)의 개념을 알고 있어야합니다
다익스트라는 우선순위 큐를 사용하고 우선순위를 지정해줘야하고 노드클래스를 만들어야하는등 구현이 더 복잡합니다.
벨만포드는 구현할 줄 알면 다익스트라 보단 쉬울 수 있습니다! 다만 시간복잡도의 문제때문에 시간초과 이슈가 있을 수 있어요
2. 완화란? 완화의 개념을 비유를 통해 쉽게 알아보겠습니다.
완화란 친구집까지 가는 경로를 계속 업데이트하는 과정이라고 생각하면 쉽습니다.
이 글을 보는 A가 친구 집에 가려고 합니다
A는 대충 카카오 맵을 보고 음.... 역에서 내리면 큰 길 따라서 쭉 가면 친구 집 나오겠네 라고 생각합니다.
근데 길을 가다보니 지나가는 할아버지가 말합니다!
"젊은이.. 큰 길 따라가지말고 뒷 골목으로 가면 5분 더 빠르다네..."
그래서 A는 역 -> 큰 길 -> 친구 집의 계획을 역 -> 뒷 골목 -> 친구 집으로 바꿉니다. 이것이 완화(relaxation)입니다!
그리고 뒷 골목을 걷다가 지나가는 초등학생이 말합니다!
"형아 이 골목에서 왼쪽으로 꺾으면 좀 더 빨라여 ㅇㅅㅇ"
그래서 A는 역 -> 뒷 골목 -> 친구 집에서 역 -> 뒷 골목 출입 -> 중간에 왼쪽 꺾기 -> 친구 집으로 바꿉니다.
이 과정들을 반복해서 더 짧은 경로가 있는지 모든 간선에 대해 확인하고 갱신하는 것입니다!
한 줄 요약 : 더 좋은 길 있으면 갈아탄다.
2. 모든 정점에서 모든 정점의 최단경로를 계산해야하는 문제
결론
1단계 : 플로이드 워셜
....앗!! 그런데 음수 가중치인지 확인하자...
2단계 : 음수 가중치야 - 플로이드 워셜
..,.앗!! 음수 가중치가 아니네? 간선과 정점의 개수를 확인하자..
3단계 : 간선의 개수가 작네? -> 다익스트라를 정점마다 시행하자 (백준 1238 (파티))
3-1단계 : 정점의 개수가 작네? -> 플로이드 워셜 (백준 11404 (플로이드)
1. 왜 이렇게 써야할까요??
일반적인 코딩테스트에서 모든 정점에서 모든 정점의 최단경로를 계산하는 알고리즘은 플로이드-워셜 뿐입니다.
플로이드 워셜의 시간 복잡도는 O(정점^3) 입니다. 3중 for문과 같은 매우 큰 시간복잡도입니다.
모든 정점에서 모든 정점까지의 경로를 계산하다보니 시간이 되게 오래걸리는 특징을 가지고 있습니다.
하지만 이 특징은 플로이드-워셜 문제의 강력한 힌트가 되기도합니다.
왜냐하면 시간 복잡도가 크다보니 정점의 개수가 많을 수록 매우 느려지므로, 플로이드-워셜 알고리즘을 활용하는 문제는 대부분 정점의 개수가 500개 이하 입니다. 그래서 정점의 개수만으로 어떤 알고리즘을 써야하는지 유추할 수 있습니다.
실전에서 이 문제는 모든 정점에서 모든 정점의 최단경로를 계산해야하는건가...? 아리송할 때 정점 개수가 500개 이하면 플로이드워셜을 쓰면됩니다
또한 앞서 플로이드 워셜의 특징을 살펴보았을 때 플로이드-워셜은 음수 가중치가 있는 경우에도 최단 경로를 계산할 수 있다고 하였습니다. 음수 가중치도 플로이드워셜 알고리즘 사용의 힌트가 될 수 있습니다.
하지만 아래에서 후술할 함정이 있습니다.
2. 모든 정점에서 모든 정점의 최단경로를 계산해야하는 문제의 함정
만약 문제에 음수 가중치가 없고 그래프의 간선이 적다면 다익스트라를 정점마다 실행하는 것이 더 효율적일 수 있습니다.
어떤 함정이냐면 모든 정점에서 모든 정점의 최단경로를 계산? -> 플로이드 워셜! 이라고 생각하는 부분에서 함정을 파놓습니다. 이 생각은 맞는 생각이지만 함정 문제를 플로이드 워셜로 풀면 시간초과가 납니다.
간선이 적으면 다익스트라를 정점마다 실행하는 것이 빠르고
정점이 적으면 플로이드워셜을 실행하는 것이 빠릅니다.
아래에 실험을 해보았습니다.
3. 정점과 간선의 개수에 따른 실험
음수 가중치가 아닐 때 다익스트라를 정점마다 시행하기 vs 플로이드 워셜의 효율 비교
1. 정점 1000개, 간선 50개 그래프
플로이드 워셜 - 1000*1000*1000 = 10억 번
다익스트라 - 1000×(50+50×10) = 55만 번
결론 : 그래프의 간선이 적으면 다익스트라를 정점마다 시행하기가 효율적
2. 정점 50개, 간선 1000개의 그래프
플로이드 워셜 - 50*50*50 = 12만 5천 번
다익스트라 - 50×(1000+1000×5.64) = 33만 2천 번
결론 : 그래프의 정점이 적으면 플로이드 워셜이 효율적
3. 모든 정점에서 한 정점으로 가는 최단 거리를 구하는 문제
지금까지는 한 정점에서 다른 정점들로 가는 길을 구했다면, 이번에는 반대로 여러 정점에서 한 정점으로 오는 길을 구하는 문제입니다.
결론
1단계 : BFS 씁니다
.... 앗!!! 그런데 가중치가 있네
2단계 : 다익스트라 씁니다.
.... 앗!! 그런데 가중치가 음수잖아
3단계 - 벨만포드 씁니다.
이 패턴.. 위에서 본 거 같지 않나요?
맞습니다 한 정점에서 다른 모든 정점까지의 최단경로를 찾는 문제와 알고리즘 선택 흐름이 같습니다
왜냐하면 바로 간선 뒤집기 트릭 때문입니다
그래프에서 모든 정점에서 한 정점까지의 최단경로를 계산하는 것은 모든 간선의 방향을 뒤집은 새로운 그래프에서 목적지 정점부터 모든 정점까지의 최단경로를 계산하는 것과 동일합니다.
예를 들어, A에서 B로 가는 비용이 5인 간선이 있다면, 간선을 뒤집으면 B에서 A로 가는 비용이 5인 간선이 생기는 거죠. 이렇게 간선을 뒤집은 그래프에서 목적지 정점을 시작점으로 삼아 다익스트라나 벨만포드 같은 단일 시작점 최단경로 알고리즘을 실행하면, 모든 정점에서 원래의 목적지까지 오는 최단경로를 구할 수 있습니다!
백준 1238번 파티 문제가 이 부분을 잘 나타내고 있습니다, 파티 장소로 가는 길(모든 정점에서 한 정점으로)과 파티 장소에서 집으로 돌아오는 길(한 정점에서 모든 정점으로)을 모두 계산해야 하는 경우에 이 개념이 활용됩니다.
4. 덩어리의 개수를 구하는 문제
결론
아래에서 유니온 파인드에 해당하는게 하나라도 있으면 유니온 파인드를 사용하면 됩니다!
1단계 BFS / DFS
2단계 집합의 합병과 특정 원소의 집합 소속 확인이 빈번하게 일어나! - 유니온파인드
2-1단계 집합의 합병과 특정 원소의 집합 소속 확인이 빈번하게 일어나지 않아! - BFS / DFS
3단계 그래프의 구조가 고정되어 있어 - BFS / DFS (백준 11724 (연결 요소의 개수))
3-1단계 문제 해결 과정 중에 새로운 연결이 계속 추가되잖아 - 유니온파인드 (백준 4195 (친구 네트워크))
1. 왜 이렇게 써야할까요?
이 문제는 그래프가 몇 개의 분리된 그룹으로 나눠져 있는지를 구하는 겁니다. 예를들어 어떤 아파트 단지에서 몇 개의 건물 군집이 있는지 세거나 섬의 개수를 세는 문제가 있습니다!
기본적으로는 BFS나 DFS를 사용합니다. 이 때 BFS, DFS 모두 사용이 가능하며 둘의 차이는 없습니다! 좀 더 손에 익은 유형으로 하면 됩니다! 방문하지 않은 정점에서 시작해 탐색을 돌리고, 탐색이 끝나면 새로운 덩어리 하나를 찾았다! 하고 카운트를 늘립니다.
하지만 문제 해결 과정 중에 새로운 연결이 계속 추가되는 문제라면? 백준 4195 (친구 네트워크)를 참고해보겠습니다.
문제를 보면 친구 관계가 입력될 때마다 두 사람은 친구 관계 인지, 네트워크 크기는 몇 명인지를 알아야합니다
이런 문제에서 BFS / DFS를 쓰면 시간 초과가 납니다. 친구 관계가 생길때마다 매번 그래프를 다시 탐색해야하기 때문입니다.
이때는 유니온 파인드를 사용해야합니다.
집합의 병합과 원소의 소속 확인이 빈번하게 일어날 때도 유니온파인드가 효율적입니다!
BFS / DFS의 시간 복잡도는 O(V+E)로 상당히 빠르지만 유니온-파인드의 시간복잡도는 거의 O(1)로 매우 빠릅니다!
2. 유니온 파인드가 빠른 이유
앞서 유니온 파인드의 특징을 알아볼 때 두가지의 최적화 기법을 소개했습니다.
경로 압축 : Find 연산을 할 때, 찾으려는 노드의 부모를 바로 그룹의 루트 노드로 연결해주는 최적화 기법입니다.
랭크 기반 합치기 : Union 연산을 할 때, 트리의 높이나 노드의 개수를 고려하여 더 작은 트리를 더 큰 트리에 붙여 트리의 높이가 급격히 커지는 것을 방지하는 최적화 기법입니다.
이 두 가지 최적화 기법 덕분에 유니온 파인드는 거의 상수 시간에 가까운 성능을 낼 수 있습니다 그래서 유니온 파인드는 위와 같은 문제에서 매번 같은 그룹인가? 라는 질문에 대한 답을 거의 즉시 알 수 있습니다.
5. 최소 신장 트리 문제
결론
유니온 파인드가 내부에 있는 크루스칼 알고리즘을 활용하자! (백준 1197 (최소 스패닝 트리))
1. 최소 신장 트리란?
1. 위의 왼쪽 그림은 사이클이 있는 연결 그래프라고 합니다. 사이클이란 말 그대로 정점들을 뱅글뱅글 돌 수 있게 선이 연결된 것을 말합니다.
2. 그래프의 모든 정점을 연결하되, 사이클을 없앤 트리를 신장트리라고 합니다.
3. 신장 트리 중에서 가장 가중치가 작은 선으로 신장 트리를 만든것이 최소 신장 트리입니다
4. 간선의 가중치를 모두 더하면 최소 신장 트리의 가중치가 됩니다. 위의 오른쪽 그림이 경우에는 15의 가중치를 가지고 있습니다.
일반적으로 최소 신장 트리 문제는 위 그림처럼 트리를 최소 신장 트리로 변환하는 문제가 나옵니다.
2. 최소 신장 트리문제를 푸는 알고리즘
이 문제를 푸는 방법은 크루스칼 알고리즘, 프림 알고리즘 두가지로 나뉩니다
잠깐!!!! 이게 그래프랑 무슨 상관이죠? 앞에서 소개한 알고리즘들이 쓰이지 않잖아요!
이 문제를 소개한 이유는 크루스칼 알고리즘의 내부적으로 유니온 파인드가 쓰이기 때문입니다
코딩테스트의 최소 신장 트리 문제의 대부분은 크루스칼 알고리즘으로 풉니다.
왜냐하면 크루스칼과 프림 알고리즘의 시간 복잡도는 비슷하며 모든 최소 신장 트리 문제는 두 알고리즘 중 어느것으로나 풀 수 있는데 구현이 더 간단한 건 크루스칼이기 때문입니다.
기업 채용 코딩테스트에서는 효율적으로 크루스칼 알고리즘만 알고있으면 모든 문제가 풀리며 그래서 크루스칼 알고리즘에 내부에 있는 유니온 파인드가 중요한 것입니다.
크루스칼 알고리즘은 간선을 오름차순 정렬한 후 가장 비용이 적은 간선부터 차례로 그래프에 추가해 나가는 방식입니다. 이때 사이클이 형성되지 않게 조심해야하는데 이 과정에서 유니온 파인드로 사이클의 형성을 검증합니다! 시간복잡도는 O(간선log간서) 또는 O(간선log정점)으로 간선을 정렬하는 과정이 주된 시간 복잡도를 차지합니다
프림 알고리즘은 한 정점에서 출발해서 가장 가까운 정점을 하나씩 선택합니다 다익스트라랑 비슷한 동작원리를 가지고 내부적으로 우선 순위 큐를 사용합니다 시간복잡도는 O(간선log정점)로 크루스칼이랑 같습니다
간선이 적으면 크루스칼을, 간선이 많으면 프림을 사용하는 것이 더 빠르기는 하지만 큰 차이는 나지 않습니다!
일반적인 코딩테스트 채용을 목표로 한다면 크루스칼만 알고 있어도 충분합니다.
3. 크루스칼 알고리즘에서의 유니온 파인드의 쓰임처
유니온 파인드의 특징에서도 말했지만 유니온 파인드는 두 가지의 함수로 구성됩니다
Find(x) : 어느 사람이 속한 집합의 최고 조상을 찾는 함수입니다 최고 조상은 그 집합을 유일하게 식별할 수 있는 사람이라고 생각하면 되고 이 함수를 통해 두 사람이 같은 집합에 속해 있는지 확인이 가능합니다.
Union(x, y) : x가 속한 집합과 y가 속한 집합을 하나로 합치는 함수입니다.
예시로 크루스칼 알고리즘을 진행해보겠습니다.
1. 모든 간선을 오름차순으로 정렬합니다.
2. 정렬된 간선리스트에서 가장 가중치가 작은 간선부터 확인해서 새로운 트리에 붙이려고 합니다.
3. 엇?! 그런데 여기서 사이클이 생기면 어쩌지?!! 간선에 연결된 두 정점을 확인해야겠다! Find(x) == Find(y)를 이용해야지!
4. 현재 간선에 연결된 두 정점이 다른 집합이라면 Union(x, y)를 이용해서 간선을 새로운 트리에 추가합니다.
5. 현재 간선에 연결된 두 정점이 같은 집합이라면 무시합니다. 이 간선을 추가하면 사이클이 생기게 됩니다!
한마디로 Find함수를 활용하여 크루스칼 알고리즘에서 사이클이 형성되는지 검증할 수 있습니다.
그리고 Union함수를 활용하여 간선을 추가할 수 있습니다.
이렇게 크루스칼 알고리즘에서 유니온 파인드가 쓰입니다