그래프 이론

지금까지 코딩 테스트에서 출제 비중이 높은 알고리즘 유형들을 다루어 보았다. 이번에는 지금까지 다루지 않았던 그래프 알고리즘을 추가로 다룰 것이다. 이전에 'DFS/BFS'와 '최단 경로'에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 이외에도 그래프 알고리즘은 굉장히 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘이다.

 

여기서 다루는 개념들을 바르게 이해할 수 있다면 코딩 테스트에서 만나게 될 다양한 응용문제들도 해결할 수 있을 것이다.

 

크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료 혹은 스택 자료구조를 활용해야 구현할 수 있다. 따라서 배운 내용을 잘 이해하고 있다면, 이제 다룰 그래프 알고리즘의 내용을 이해하는 데 크게 어렵지 않을 것이다. 다른 알고리즘들에 비해 비중은 낮은 편이지만, 코딩 테스트를 꼼꼼히 준비하기 위해서 지금부터 배울 내용을 잘 숙지해야 한다.

 

내용을 다루기 전에, 앞서 공부했던 그래프에 대해 복습해보자. 먼저 그래프(Graph)란 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제를 접했을 때 '서로 다른 개체(혹은 객체, Object)가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 예를 들어 '여러 개의 도시가 연결되어 있다'와 같은 내용이 등장하면 그래프 알고리즘을 의심해봐야 하는 것이다.

 

더불어 그래프 자료구조 중에서 트리(Tree) 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억해야 한다. '다익스트라 최단 경로 알고리즘'에서는 우선순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙(Min Heap)이나 최대 힙(Max Heap)을 이용할 수 있다고 했다. 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다. 그래프와 트리 자료구조를 비교하면 다음 표의 내용과 같다. 참고로 트리는 전통적인 수학에서는 무방향 그래프로 간주되지만, 컴퓨터공학 분야에서는 보통 방향 그래프라고 간주된다.

 

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드 간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

 

또한 그래프의 구현 방법은 (DFS/BFS를 공부할 때 알아봤던 것처럼) 2가지 방식이 존재한다. 다시 한 번 간단히 요약하면 다음과 같다.

• 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식
• 인접 리스트(Adjacency List): 리스트를 사용하는 방식

2가지 모두 그래프 알고리즘에서 매우 많이 사용된다. 두 방식은 메모리와 속도 측면에서 구별되는 특징을 가진다는 점을 기억해야 한다.

 

노드의 개수가 V, 간선의 개수가 E인 그래프를 생각해보자. 인접 행렬을 이용하는 방식은 간선 정보를 저장하기 위해서 O(V^2)만큼의 메모리 공간이 필요하다. 반면에 인접 리스트를 이용할 때는 간선의 개수만큼인 O(E)만큼만 메모리 공간이 필요하다. 또한 인접 행렬은 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있으며, 반면에 인접 리스트를 이용할 때는 O(V)만큼의 시간이 소요된다.

 

우선순위 큐를 이용하는 다익스트라 최단 경로 알고리즘은 인접 리스트를 이용하는 방식이다. 노드의 개수가 V개일 때는 V개의 리스트를 만들어서 각 노드와 연결된 모든 간선에 대한 정보를 리스트에 저장했다.

 

플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다. 모든 노드에 대하여 다른 노드로 가는 최소 비용을 V^2 크기의 2차원 리스트에 저장한 뒤에 해당 비용을 갱신해서 최단 거리를 계산했다. 이처럼 인접 행렬과 인접 리스트는 다양한 그래프 알고리즘에서 사용되고 있다.

 

알아두어야 할 점은 어떤 문제를 만나든 메모리와 시간을 염두에 두고 알고리즘을 선택해서 구현해야 한다는 것이다. 예를 들어 최단 경로를 찾아야 하는 문제가 출제되었을 때, 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용할 수 있다. 반면에 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리하다.

 

 

 

 

 

[참고문헌]

나동빈, 2021, 「이것이 취업을 위한 코딩 테스트다 with 파이썬」, 한빛미디어.