1. 위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. [그림 1]을 보자. [그림 1]은 임의로 만든 마법사로 전직을 한후 배워야하는 스킬의 관계도다. 각 스킬에 대한 관계도를 정리하면 다음과 같다. 에너지 볼트는 맨 처음에 배우는 기본 마법이다. 매직클로를 배우려면 에너지볼트를 먼저 배워야한다. 메테오를 배우려면 먼저 매직클로, 텔레포트를 배워야한다. 마력 흡수를 배우려면 먼저 에너지 볼트를 배워야한다. 텔레포트를 배우려면 먼저 마력흡수, 매직클로를 배워야한다. 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 먼저 마법사로 전직하면 에너지 볼트를 찍고, 그 다음엔 마력 흡수 또는 매직클로를 찍는다. 그리고 텔레포트를 찍고 최종적으..

1. 플로이드 와샬 알고리즘 지난 번에 포스팅했던 다익스트라 알고리즘은 하나의 정점을 출발점으로해서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 그런데 이번에 포스팅할 플로이드 와샬 알고리즘은 모든 각각의 정점을 출발점으로해서 모든 정점까지의 최단경로를 구하는 알고리즘이다. 하나의 정점을 출발하는 것이 아니라, 그래프에 있는 모든 각각의 경로에 대한 최단경로를 구하기 때문에 시간복잡도는 O(N³)이다. 또한 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 이게 무슨 말인지 감이 안오더라도, 지금부터 하는 설명을 들으면 어떤 순서로 알고리즘이 수행되는지 알 수 있을 것이다. [그림 1]은 그래프의 각 정점에 대한 가중치를 순차자료구조로 변환한 것이다. 먼저 출발 정점을 A로 설..

1. 너비 우선 탐색 너비 우선 탐색은 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법이다. 깊이 우선 탐색과 반대의 움직임을 보인다고 생각하면 된다. 깊이 우선 탐색이 세로 본능이라면 너비 우선 탐색은 가로본능이라고 생각하면 된다. 정확히는 거리로 보면 된다. A에서 1떨어진 노드는 B, C 다. 고로 B와 C는 형제다. 하지만 B, C와 A는 부모-자식 관계다. 깊이 우선 탐색은 자식부터 탐색을 하는 구조다. 하지만 너비 우선 탐색은 주변 인접노드, 형제를 먼저 탐색하는 구조다. 너비 우선 탐색은 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입 선출의 구조를 갖는 큐 자료구조를 사용한다. 2..

1. 깊이 우선 탐색 깊이 우선 탐색(DFS, Depth First Search)은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해나가다가 더 이상 갈곳이 이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서, 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회 방법이다. 저번에 트리에 대해 포스팅했을 때 전위, 중위, 후위 순회 방법 세 가지를 언급한 적이 있었다. 이 세 가지 방법이 깊이 우선 탐색에 해당된다. 깊이 우선 탐색은 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 스택을 사용한다. 2. 탐색 과정 그림을 이용해서 알고리즘이 어떻게 돌아가는지 설명해보도록 하겠다. 밑에 [그림1]은 빈 스택과..

1. 그래프 그래프란 연결되어있는 원소 간의 관계를 표현하는 자료구조를 말한다. 버스 노선도, 전철 노선도, 인간관계를 나타내는 연결구조는 구조가 너무나도 다양하고 복잡하기 때문에 선형 자료구조나 트리로 표현할 수 없다. 그래프는 연결할 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)로 구성된다. 그래프 G를 G = (V, E)로 정의하는데, V는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선의 집합을 의미한다. 2. 그래프의 종류 (1) 무방향 그래프 무방향 그래프는 간선에 방향이 없는 그래프를 말한다. 무방향 그래프는 정점 V₁과 정점 V₂를 연결하는 간선을 (V₁, V₂) 로 표현한다. 아래 [그림 1]은 무방향 그래프를 나타낸 그림이다. 위 무방향 그래프 G를 정점의 ..