본문으로 바로가기
반응형

수많은 알고리즘 문제들이 동적계획법으로 변형하여 해결이 가능한 것으로 알고있다. 하지만, 이를 위해서는 수학적인 직관과 알고리즘 문제에 대한 상당한 숙련이 필요하다. 사실 알고리즘 선수 수준의 숙련도가 아닌 이상 알고리즘 문제를 해결할 때에는 문제를 잘 파악한 뒤 이 문제에 어떤 알고리즘 기법을 사용해야 할지를 결정하는 것이 문제 해결의 80%는 결정한다고 본다. 사실 그래프는 알고리즘 기법이라기 보다는 여러 가지 효율적인 알고리즘을 적용하기 위한 자료구조이다. 알고리즘 문제를 접할 때에도 그래프(Graph)를 사용한 알고리즘 문제 풀이는 동적계획법에 비해 상대적으로 의도를 파악하기 쉬운 자료구조이기 때문에 잘 알아두면 분명 도움이 될 것이다.


그래프의 기초 용어 정리


그래프는 정점과 간선으로 구성하는 자료구조를 뜻한다. 상당히 많은 상황을 그래프로 표현할 수 있으며, 많은 알고리즘 문제 역시 그래프로 표현하여 문제를 해결할 수 있다.

알고리즘 문제를 푸는 것에 용어가 무슨 쓸모가 있을까 싶었다. 사실 그래서 별로 알아보고 공부해볼 생각도 하지 않았었다. 하지만 문제를 풀고 그에 대한 해설이나 다른 사람의 조언을 통해 해결 방안을 얻기 위해서는 해당 기법에 대한 기본적인 용어는 알아야 한다. 기본적인 용어조차 모른다면, 문제를 풀다 해답을 찾기 위해 구글링을 했는데 "Graph가 Dag라면 각 vertex에서 연결된 edge의 가중치를 더하시면 됩니다." 라고 쓰여 있다면 멘붕에 빠질 것이다. 그래프에서 쓰이는 간단하지만 꼭 알아야 도움이 되는 용어들에 대해 공부해 보았다.


- 정점(Vertex , Node) : Vertex라고도 표현하고 Node라는 용어를 사용하기도 한다. 같은 것이라고 생각하면 되겠다. 정점은 위 그래프에서 동그라미 친 1,2,3,4,5,6 과 같은 각각의 지점을 의미한다.


- 간선(Edge, Link) : 역시 Edge와 Link 두가지 용어를 사용한다. 그래프에서 각 정점들을 연결하는 선이다. 화살표 표시가 된 것도 있고 그냥 직선으로 표시된 것도 있는데, 둘 다 '간선' 이라고 사용한다.


- 가중치 : 간선 위에 표시된 숫자이다. 가중치가 있는 그래프가 있고 없는 그래프가 있는데, 가중치가 없다면 모두 동일한 가중치를 가진다고 보면 된다. 해당 간선을 타고 이동할 때 필요한 비용 등을 표현하는 것에 사용된다.


- Directed Graph : 말 그대로 방향성이 있는 그래프이다. 위 두개의 그래프 중 왼쪽 그래프가 Directed Graph이다. 간선의 방향에 따른 이동만이 가능한 경우에 사용한다.


- undirected Graph : 오른쪽 그래프 처럼 간선이 방향성이 없는 일반 실선으로 표시된 그래프이다. 방향성이 없다고 이동을 못하는 것이 아니라, 모든 간선들은 양방향 이동이 가능함을 의미한다.



- Self-loops : 정점에서 자기 자신으로 돌아오는 간선을 뜻한다. 오른쪽 그래프에서 6번 정점에 연결된 가중치 2의 간선이 이에 해당한다.


- Adjacency : 방향성이 있는 directed graph에서의 간선으로 연결된 인접 정점을 뜻한다. 하지만 이는 쌍방향 모두에 적용되는 것이 아니다. 예를들어 위 Directed Graph에서 정점4가 정점1에 Adjacency하다고 한다면, 정점1은 정점4에 Adjacency하다고 표현할 수 없다.


- Degree : 각 정점에 연결되어 있는 Edge들의 수이다. 이 중 out-degree는 해당 정점에서 나가는 간선을, in-degree는 해당 정점으로 들어오는 간선이다. 따라서 특정 정점에서의 모든 out-degree와 in-degree를 더하면 그 정점의 Degree가 된다.


- Path : 정점 A에서 정점 B로 이동할 수 있는 경로를 의미한다. 그래프 내에서 정점 끼리의 path는 하나만 존재할 수 있는 것이 아니라, 여러 종류의 길이 존재할 수 있다. 또한 두 개의 정점이 이동할 수 없기도 한다. 여기서 정점A 에서 정점 B로 가는 Path가 존재한다면 정점 B는 정점 A로부터 reachable하다고 표현한다.




- Simple Path : 경로 상의 모든 정점들이 중복되지 않는다면 이 경로를 simple path라고 한다. 예를 들어 위의 그래프에서 경로 <1,4,2,3,5> 는 simple path 라고 할 수 있지만 <1,4,2,1>은 simple path가 아니다.


- Cycle : 그래프가 path를 따라 동일한 정점으로 돌아올 수 있는 경우를 의미한다. 위 그래프의 왼쪽 컴포넌트는 <1,4,2> path가 cycle을 이룬다. 이 중, 돌아오는 경로 안에서 중복된 노드가 시작점(끝점) 이외에는 발생하지 않는 경우를 Simple Cycle이라고 표현한다.


- An acyclic graph : 그래프에 싸이클이 없는 경우 그 그래프를 acyclic graph라고 부른다.


- Connected Graph : 기본적으로 connected graph는 방향성이 없는 그래프이다. 모든 쌍의 정점들이 path로 연결이 가능한 그래프를 connected graph라고 칭한다.


- Connected Component : 위 그래프 전체도 하나의 그래프이다. 이 중 방향이없는 그래프의 정점 하위 집합을 최대로 연결한 것을 Connected Component라고 한다.


- Forest : 그래프 중 Acyclic하고 Undirected하면 Forest라고 부른다.


- Tree : Forest에서 하나 하나의 Component들은 Tree가 된다. 따라서 Connected, Acyclic, Undirected 모두를 만족하는 graph가 Tree라고 볼 수 있다.


- Dag : Tree가 방향성이 없고 싸이클이 존재하지 않는 그래프라면, Dag는 방향성이 있는 그래프 중 싸이클이 나오지 않는 그래프를 의미한다.



그래프 기본 알고리즘


그래프 형태의 자료구조로 표현한 문제를 해결하는 것에는 매우 다양한 알고리즘이 존재한다. 이 중 가장 대표적인 것이 그래프 탐색 기법 중 Breadth-first search(BFS)와 Depth-first search(DFS)이다. 그래프 내의 최단 경로를 구하는 것은 다익스트라, 벨만-포드, 플로이드 등의 알고리즘이 있다. 사실 지금 언급한 알고리즘 기법들은 상당히 자주 사용되는 것이기 때문에 하나 하나 공부하고 문제를 풀어보는 과정을 거쳐야 한다.

반응형

 Other Contents