이번 장에서 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있다.
그래프에 대해 다시 복습해보자. 먼저 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제를 접했을 때 ‘서로 다른 개체(객체)가 연결되어 있다’는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 예를 들어 ‘여러 개의 도시가 연결되어 있다’와 같은 내용이 등장하면 그래프 알고리즘을 의심해보자.
더불어 그래프 자료구조 중에서 트리(Tree) 자료구조는 다양한 알고리즘에서 사용되기 때문에 꼭 기억하자.
| 그래프 | 트리 | |
|---|---|---|
| 방향성 | 방향 그래프 혹은 무방향 그래프 | 방향 그래프 |
| 순환성 | 순환 및 비순환 | 비순환 |
| 루트 노드 존재 여부 | 루트 노드가 없음 | 루트 노드가 존재 |
| 노드 간 관계성 | 부모와 자식 관계가 없음 | 부모와 자식 관계 |
| 모델의 종류 | 네트워크 모델 | 계층 모델 |
그래프의 구현 방법은 5장에서 알아보았던 것처럼 2가지 방식이 존재한다.
2가지 모두 그래프 알고리즘에서 많이 사용되는 방식이지만, 메모리와 속도 측면에서 구별되는 특징을 기억하자.
… 정리하기
서로소 집합(Disjoint Sets): 공통 원소가 없는 두 집합
서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로 union과 find 이 2가지 연산으로 조작할 수 있다.
union: 합집합으로 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
find: 찾기로 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.
스택과 큐가 각각 push와 pop 연산으로 이루어졌던 것처럼, 서로소 집합 자료구조는 union과 find로 이루어진다.
서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 저보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.