1. 가중치 그래프 가중치 그래프는 간선에 가중치를 할당한 그래프를 말한다. 가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다. 크루스칼(Kruskal) 알고리즘은 비용, 거리, 시간을 최소화하는 신장트리를 만들기 위해 나온 알고리즘이다. 즉, 모든 가중치의 합이 최소 값이 되어야 한다는 것이다. 최소 값이 나오게 하려면, 가중치를 오름차순으로 n-1만큼 더하면 된다. 그런데 앞에서 크루스칼 알고리즘에 대해 설명할 때 신장트리라는 말을 한 적이 있다. 신장 트리란, n 개의 정점을 가진 그래프 G에서 모든 정점이 n-1개의 간선으로 이루어진 트리를 말한다. 2. 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘은 두 가지 방법이 있다. 첫 번째 방법은 가중치가 높..

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를 정점의 ..

1. 셸 정렬 셸 정렬은 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다. 전체 원소에 데헤 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하면 전체 연산 횟수를 줄일 수 있다. 셸 정렬에서 부분집합을 만드는 기준이 되는 간격을 매개변수 h에 저장한다. h에 대해 h가 1이 될 때까지 1/2씩 감소시키고, 각 단계마다 셸 정렬을 순환 호출한다. 처음에 h는 입력 배열의 길이에 1/2한 자연수를 초기화 값으로 받는다. 셸 정렬의 전체 연산 횟수는 간격 h에 의해 영향을 받기 때문에 알고리즘의 성능을 분석하기가 쉽지 않다. 일반적으로 셸 정렬의 시간 복잡도를 $$ O(n^{1.25}) ..

1. 기수 정렬 기수 정렬은 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하는 배열이다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키 값의 길이만큼 기수 정렬을 반복한다. 숫자는 기본적으로 10진수로 표현되기 때문에, 키 값을 가진 원소들을 정렬할 때는 0부터 9까지 총 10 개의 버킷을 사용한다. 정렬의 반복 횟수는 입력 배열의 원소 중 최대 값의 길이 만큼이다. 예를 들어 [103, 3, 22]를 기수정렬을 이용하여 반복해야 할 때, 입력 배열 중에서는 103이 최댓값이므로, 기수 정렬의 반복횟수는 103의 길이인 3이 된다. 2. 동작 순서 길이가 5인 입력배열 [3, 55, 7, 17, 1]..