Azza's Blog

그래프로 모델링 되는 문제들을 해결하기 위한 알고리즘들이 나온다.

여기에 소개되는 알고리즘인 Prim, Kruskal, Dijkstra 알고리즘은

Greedy Algorithm의 대표적인 예이다.

특히, 이 알고리즘들은 일반적으로 최적의 해를 구하지 못하는

Greedy Algorithm에서 최적의 해를 구하는 알고리즘이다.

1. 최소(비용) 신장 트리(Minimum Spanning Tree)

먼저 신장트리의 의미를 알아보자.

신장(伸張)이라는 단어의 의미를 네이버 국어사전에서 찾아보면,

"세력이나 권리 따위가 늘어남. 또는 늘어나게 함."

그래도 역시 감이 안 온다. 위키피디아에 있는 정의를 찾아보자.

Undirected Graph에서 그 Graph의 부분Graph이면서 모든 꼭지점을 연결하는 트리이다..

즉 Cycle 이 없는, 모든 Vertex를 포함하는 부분 Graph를 말한다.

하나의 Graph에는 많은 Spanning Tree가 있을 수 있다.

Edge에 Weight가 있을 때, Spanning Tree 중 Weight가 최소인 것을 바로

"Minimum Spanning Tree"(이하 MST) 라고 하는 것이다.

그래서, 이 MST를 찾는 알고리즘에는 Prim Algorithm과 Kruskal Algorithm이 있다.

두 Algorithm 모두 Greedy Algorithm 이지만, 모두 정확한 MST를 찾아낸다.

(실제 C 언어로 밑바닥부터 구현해 보니 설명처럼 쉽진 않았다.)

- Prim Algorithm

( http://en.wikipedia.org/wiki/Prim%27s_algorithm )

(위키피디아에 있는 구현 아이디어)

Graph G(V,E)가 있을 때,

최초에 V' = { x }, (x 는 V 에 있는 임의의 Vertex). E' = { } 로 둔다.

V = V' 가 될 때까지 다음을 수행한다.

1. E 로 부터 최소의 가중치를 갖는 간선 (u,v)를 고른다.

   (단, u 는 V' 에 포함되고 v 는 V' 에 포함되지 않아야 한다.)

2. v 를 V'에 추가한다. (u,v) 를 E' 에 추가한다.

위의 과정을 반복이 끝나면, G(V', E')가 MST가 된다.

위의 방법은 위키피디아에 되어 있는 아이디어이다.

실제 책에는 좀 다른 방법으로 구현하는데,

아래 적은 내용은 책과 완전 동일한 것은 아니다.(하지만 거의 비슷하다)

(책에 있는 구현 아이디어)

Graph G(V,E)가 있을 때,

Vertex2 는 원래 Vertex 정보에 key(가중치정보), color(방문정보) 값, parent 값이 추가된 정보다.

모든 Vertex 에 대하여 Vertex2를 만든다. Vertex2 의 집합을 V2 라고 한다.

이 때, Vertex2 들의 기본값은 key = 무한대, color = 미방문, parent = NULL 이다.

최초에 V' = { x }, (x 는 V2 에 있는 임의의 Vertex). E' = { } 로 둔다.

시작점 x 의 key = 0, color = In_Heap 로 설정하고, x 를 key 값에 대한 Min-Heap, 'H' 에 넣는다.

H 가 Empty 가 될 때까지 아래를 반복한다.

1. H 의 Root 값 r 을 가져오고, r 을 V2 에서 제거한다.

2. r 의 color 를 방문함으로 설정하고, V' 에 추가한다.

3. r 과 r's parent 를 연결하는 Edge 를 E' 에 추가한다.

4. r 의 인접 Vertex 들 각각에 대하여 Vertex 'v'의 color 가 미방문이라면,

   key값과 Edge 'e'의 weight 를 비교하여,

   'e' 의  weight 값이 작다면, 'v' 의 key 값을 'e' 의 weight 값으로 설정하고,

   'v' 에 대하여 V2 를 Reheapfy 한다.

   그리고 'v' 의 parent 를 r 로 설정한 뒤,

   'v' 의 color 가 '미방문' 이라면 'v' 의 color = In_Heap 으로 설정하고 'H' 에 Insert 한다.

아래에 있는게 좀 더 복잡해 보이지만, 내가 직접 구현했던 방법이라

오히려 자세하게 설명하느로 길어진 것으로 판단된다.

Graph를 어떻게 구현하는냐에 따라 Time Complexity가 다른데,

이와 같다.

- Kruskal Algorithm

( http://en.wikipedia.org/wiki/Kruskal%27s_algorithm )

Minimum Spanning Tree를 찾는 다른 Greedy Algorithm이다.

이 알고리즘의 구현에 대해선 따로 설명하지 않겠다. 위키피디아 참고.

단, Prim 과 차이점을 잠깐 살펴보겠다.

Kruskal 의 Time Complexity 는 O(E log E) 인데,

E <= V^2 이므로 O(E log V^2) = O(2E log V) = O(E log V)가 된다.

Prim 의 피보나치힙을 사용한 구현과 비교했을 때,

V, E 가 큰 경우,

E 의 값의 크기에 따라 Prim 의 피보나치힙 / Prim 의 바이너리힙 or Kruskal 알고리즘

을 택하면 될 것으로 보인다.

Prim 과 Kruskal 어떤 것을 구현해 볼까 고민하다가,

Kruskal 은 쉬워 보이긴 하지만,

Cycle 체크가 필요한 코드가 있기에 패스.

(힙도 구현해야 되고 Cycle 체크까지 해야 되기에...)

일단 이 글은 여기까지.

그 이름도 유명한 Dijkstra 알고리즘과 TSP 문제는 다음 글에...

p.s

계속 느끼는 거지만, 이미 잘 만들어진 Library 가 있는데,

C 로 맨땅에서 만드는 건 어렵네.

(앞에서 만들어 둔 자료구조들을 대충 아무렇게나 던줘놨더니... 찾질 못하겠음...)

역시나 뭔가 좀 애매한 장이다.

알고리즘 접근 측면에서 설명을 하는 것은 아니고,

단순히 압축 방법과 암호화에 대한 설명이라 좀 실망.

물론 이런 원리는 중요하긴 하다만,

역시나 특수한 상황이 아니면, 직접 이런걸 공부해야 할 일이 있을까?

더욱이 이런걸 공부하더라도 직접 코딩을 하는건 시간 낭비.

Commercial Software 에서도 사용 가능한

zlib 라이브러리와 openssl 라이브러리가 있는데,

뭐하러 라는 생각이 절로 든다.

알고리즘 설명이라기 보다는 그냥 압축, 암호화에 대한 설명에

알고리즘은 곁다리로 끼워넣은 느낌?

압축, 암호화에 대한 기본적인 설명은 읽어볼 만 한듯?

하지만 현재 나의 관심사는 아니므로 패스.

수치 메쏘드는 수치 해석의 알고리즘이다.

책에서는 명시적으로 밝히고 있진 않지만,

근사 알고리즘을 사용하는 대표적인 예로 볼 수 있겠다.

다만, 많은 연산을 필요로 하므로 컴퓨터를 이용한다.

이 분야는 사실 관심분야가 아니라서 간단하게,

어떤 것이 있는가만 보고 패스.

책에서는 방대한 범위의 수치 해석 분야 중, 3가지 수치 메쏘드를 소개하고 있다.

- 다항 보간법(polynornial interpolation): n+1 개의 점에서 차수가 n보다 작거나 같은 보간 다항식 Pn(z)를 만드는 것.

- 최소 제곱 추정(least-squares estimation): y(x)가 n개의 점들의 최적직선(best-file line)이 되도록

                                                             y(x) = ax + b의 추정값 a와 b를 구한다.

                                                             그러니깐 실험결과로 나온 점들이 주욱 있을 때, 거기에서 제일 가까운

                                                             직선을 구하는거...

머 이런 것들에 수치 메쏘드를 사용한다고 한다.

수학/과학 연구하는 사람들한테는 유용할 듯..

12장에서는 Divide-and-Conquer 의 대표적인 예인,

퀵소트(Quicksort)와 머지소트(Mergesort)를 알아보겠다.

이진 탐색은 굳이 설명할 필요성도 못 느끼겠다.

학교 다닐 때, 교수님이 소트를 가르키다가 소트를 왜 하나요? 라는 질문을 한 적이 있었다.

그 땐, 그런거 생각할 정신이 없었던거 같다. 조금만 생각해보면 쉬운걸...

당연히 자료를 찾기 쉽도록(탐색) 하기 위해서다...

머, 여기까지만 하고, 이번에는 대표적인 D&C 방법의 소트인

퀵소트와 머지소트를 알아보고, 부가적으로 소트에 대한 이야기를 조금 하겠다.

먼저, 소트에 대한 이야기

Sorting(정렬)

( http://en.wikipedia.org/wiki/Sorting_algorithm )

- "in place"(인플레이스) : 어떤 Sorting Algorithm이 "in place" 라는 말은, 원본 데이터 공간에서 Sorting을 한다는 말이다.

                                    즉, Sorting을 위한 추가 저장공간이 필요하지 않다는 말이다.

                                    (물론 Swap 을 위한 상수크기의 공간정도는 필요하다.)

- Stability(안정성) : Sorting 되지 않은 데이터들 중, 같은 Key값을 가지고 있는 A, B가 있다고 가정하자.

                           Sorting 후에도 이 A, B의 Order가  바뀌지 않는다면 이 Sorting Algorithm은 Stability를 가진다고 한다.

Quicksort(퀵소트)

( http://en.wikipedia.org/wiki/Quicksort )

퀵소트는 대표적인 Divide and Conquer 알고리즘이다.

퀵소트는 주어진 리스트를 임의의 값(Pivot)을 기준으로 큰 리스트와 작은 리스트로 나누고,

두 리스트에 대해서 Recusive하게 퀵소트를 실행하는 과정으로 리스트를 정렬한다.

그리고 퀵소트는 in place sorting 이다.

int 형에 대해서 퀵소트를 하는 C 함수는 다음과 같다.

Mergesort(머지소트, 합병정렬)

Divide and Conquer 알고리즘의 또 다른 예이다.

머지소트는 주어진 리스트를 반으로 나누고,

두 리스트에 대해서 Recusive하게 머지소트를 수행한다.

정렬된 두 리스트에 대해서 정렬된 하나의 리스트로 합병한다.

1. 정렬할 자료의 크기만큼의 추가 저장공간이 필요하다는 점.

2. 최악의 경우에도 시간복잡도는 O(n log n) 이라는 점.

3. Stable 한 정렬이라는 점. (같은 key 의 자료에 대해서 order 가 유지된다는 말)

4. 전체 자료 집합 모두를 동시에 메모리에 유지하지 않으면서도 수행가능 하다는 점.

   (아주 큰 자료일 경우 유용하다)

정도랄까?

시각적으로 표시하면 아래와 같다.

(출처: http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg )

int형에 대해서 머지소트를 수행하는 C함수는 다음과 같다.

(메모리 할당 관련 오류 처리코드는 빠져있다. 실사용을 위해서는 추가 저장공간에 대하여 적절히 고려되어야 하겠다)

결론

Divide and Conquer 은 참 좋은 알고리즘이다. 쉽고, 병렬처리에도 좋고...

하지만 Dynamic Programming을 사용해야 하는 곳에 사용하게 되면 끔찍해 진다는거..

분명, 학교에서 배운거 같은데 기억이 안나네.

다시 한 번 정리하는 차원에서...

먼저 Turing Machine(튜링 머신, 이하 TM)에 대해서 알아야겠다.

Turing Machine(튜링 머신)

TM은 Alan Turning에 의해 소개된 가상의 기계이다. (무한한 메모리와 저장장치-테이프-를 가진...)

간단하게 생각하면, 오늘날의 컴퓨터와 같다고 생각하면 된다.

(단, 오늘날의 컴퓨터는 메모리/저장장치의 제약이 있다.)

여기에서 Non-deterministic Turing Machine(비결정적 튜링 머신, 이하 NTM 혹은 NDTM)이라는 것을 생각해 내었는데,

이것 또한 가상의 기계이다. (아니, 상상의 기계에 가깝다고 해야 하나...)

원래 TM에서는 Current State와 Tape Symbol에 따른 Action이 최대 1개이다.

NTM은 같은 상황에서 Action이 1개 이상도 될 수 있다.

NTM에서 어떤 Action을 선택할 것인가 결정하는가?

http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine#Resolution_of_multiple_rules

위키피디아의 설명에 따르면, Branches 수 만큼, Computation Tree를 가지게 되는 것이다.

(TM은 하나의 Computation Path를 가진다.)

이러한 기계를 Non-deterministic Turing Machine라고 하고,

원래의 Turing Machine을 NTM과 구분하기 위해 Deteministic Turing Machine이라고 한다.

DTM -> NTM 으로 쉽게 변환이 가능하다. DTM은 NTM의 Special case 중 한 가지일 뿐이니깐,

그럼 NTM -> DTM 으로 변환이 가능한가? 가능하다... 가능하긴 한데...

변환된 DTM의 Accepting computation의 길이는 NTM의 Shortest accepting computation 길이의

Exponential 한 만큼 길어진다고 한다.

P, NP

Decision Problem(결정 문제)라는 것이 있다.

( http://en.wikipedia.org/wiki/Decision_problem )

어떤 유한한 입력에 대해서 Yes/No로 대답할 수 있는 문제를 말한다.

이런 문제들은 단순히 Yes/No를 대답하는 것보다 복잡하다.

문제에 대한 최적의 해를 알아야 하기 때문이다.

P, NP 라는 것은 Decision Problem의 Complexity class(복잡도 종류)를 말한다.

P는 DTM에서 다항시간^[각주:1]에 풀 수 있는 문제의 복잡도이다. (즉, 현재의 컴퓨터에서 다항시간에 풀 수 있다는 것이다)

NP는 NTM에서 다항시간에 풀 수 있는 문제의 복잡도이다.

P 문제는 NP 문제에 포함되므로, 따로 P 문제라고 구분해서 부르지 않는듯 하다.

단지 NP 문제 중, 컴퓨터로 문제를 푸는 알고리즘이 비싼(O(n!) or O(k^n) 정도) NP Problem 을

NP-Complete Problem이라고 구분해서 부른다.

P = NP 인가?에 대한 질문은 아직까지 컴퓨터 과학계에서 해결하지 못한 문제이다.

NP-Complete, NP-Hard

이 두 가지는 정의가 좀 어렵다. 공식정인 정의는 알고리즘 책을 찾아보는게 좋겠다.

좀 쉽게(비공식적인 정의?) 적어보자면...

NP-Hard는 NP에서 가장 어려운 문제만큼 어려운 문제를 말한다.

하지만 이름과는 다르게 꼭 NP일 필요는 없다.(Decision Problem일 필요는 없다는 말)

NP-Complete는 NP에서 가장 어려운 문제를 말한다.

일반적으로 NP-Complete 문제들은 다항시간에 푸는 알고리즘이 없다고 추측한다.

하지만 이것은 증명된 것은 아니다.(존재하는지도 존재하는 않는지도 모른다는 말)

NP-Complete 정의에 따르면 모든 NP Problem 은 NP-Complete problem 으로 환원 될 수 있다고 되어있다.

다시 말해, 하나의 NP-Complete 문제에 대해 다항시간에 푸는 알고리즘을 찾아내거나

혹은 반대로 하나의 NP-Complete 문제에 해서 다항시간에 푸는 알고리즘이 없음을 증명한다면,

P = NP? 질문에 대한 답을 찾아낸 것이다. (그리고 추가로 100만달러 보너스까지!!!)

결론

NP-Complete 문제, NP-Hard 문제는 컴퓨터로 최적의 해를 구하시에는 어마어마한 시간이 걸리는 문제다.

따라서 이런 문제의 최적의 해를 찾기 위해 삽질하지 말고,

Approximation Algorithm이나 Heuristic Algorithm을 택하자.

(사실 이런 문제는 ACM 이나 Google Codejam 에는 안 나올꺼 같지만...)

P.S

이 글에선 P, NP, NP-Complete, NP-Hard를 용어를 형용사와 ~~ 문제를 의미하는 명사로

혼용하여 사용하였는데, 문맥에 맞추어 해석하면 됩니다.

P.S 2

이 글을 관심있게 읽을 사람이 있을까 싶지만은,

혹시나 오류가 있다면 리플을 부탁합니다.

각주.

'C 로 구현한 알고리즘' 의 3부 알고리즘 장을 보면,

- 12장 정렬과 탐색

- 13장 수치 메쏘드

- 14장 자료 압축

- 15장 자료 암호화

- 16장 그래프 알고리즘

- 17장 기하 알고리즘

으로 구성되어 있다.

개인적으로 이런 접근법은 좋아보이진 않는다.

문제를 풀기위한 접근방법에 대한 설명이 먼저 필요하다고 본다.

문제를 해결하기 위한 접근 방법에는 다음과 같은 것들이 있다.

- Divide and Conquer

- Dynamic Programming

- Greedy Algorithm

- Approximation Algorithm

각각에 대해 간략히 알아보자

Divide and Conquer (분할 정복 알고리즘)

( http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm )

이름 그대로 작은 문제로 나눠서 풀고, 그 결과를 합쳐서 해답을 구하는 것이다.

예를 들면 Quick Sort 나 Merge Sort 가 있겠다.

단, 문제를 Recursive하게 풀기 때문에, Call Stack 이 너무 깊어지면 안된다.

Merge Sort 처럼 최대 Call Stack이 log(n)보다 더 크지 않다는 보장이 있어야 하겠다.

그 외 자세한 사항은 위키피디아 참고.

Dynamic Programming (동적 프로그래밍)

( http://en.wikipedia.org/wiki/Dynamic_programming )

이 방법은 문제를 더 단순한 문제로 쪼개서 푸는 방법이다.

D&C와 비슷한거 같지만 큰 차이점은 Subproblem이 겹치는 경우 Dynamic Programming 을 선택한다.

( Merge Sort의 경우 나누어진 Subproblem이 독립적이다. )

이 접근방법의 아주 아주 아주 쉬운 예는 피보나치 수열이다.

F(n) = F(n-1) + F(n-2). (F(0)=0, F(1)=1)

이 문제를 D&C로 풀게되면, 어마어마한 양의 중복연산이 필요하다.

이런 경우에는 중복연산을 피하기 위해 Subproblem의 결과를 저장하는 공간을 따로 두고,

이 결과를 이용하는 방법을 사용해야 할 것이다.

피보나치 수열은 아주 아주 아주 쉬운 예.. 이다.

( 기억을 더듬어 보면 Dynamic Programming 을 이해하는 것은 그리 쉬운게 아니었던거 같다..; )

Greedy Algorithm (욕심장이 알고리즘)

( http://en.wikipedia.org/wiki/Greedy_algorithm )

이 방법은 매 순간 가장 좋아 보이는 것을 선택한다.

하지만 이 방법이 항상 최적의 답을 구하는 것은 아니다.

그럼에도 불구하고, NP-Complete한 문제에 대해서

최적의 해에 근접한 답을 빠른 시간에 선택할 수 있어서 유용하다.

만약 Greedy Algorithm으로 최적의 해를 찾아낼 수 있는 문제라면,

다른 접근 방법보다 좋다.(Faster)

이런 문제의 예에는 Minium Spanning Trees나 Dijkstra's Algorithm나 Huffman Trees가 있다.

Approximation Algorithm (근사 알고리즘)

( http://en.wikipedia.org/wiki/Approximation_algorithm )

이름 그대로 최적의 해에 근사한 답을 구하는 알고리즘이다.

NP-Hard한 문제나 비싼 NP-Complete문제를 해결하는데 사용한다.

AVL 트리와 RB 트리 공부하다가 진이 빠져서, 몇 일 책을 못봤다.

결국 RB 트리를 구현하긴 했지만, 왜 했나 싶기도 하고...

이번엔 자료구조의 마지막 장, Graph 이다.

시작

(출처: http://en.wikipedia.org/wiki/File:6n-graf.svg )

위 그림이 컴퓨터 사이언스에서 이야기 하는 Graph 자료구조를 그림으로 표현한 것이다.

그림에는 따로 방향성이 없는데, 방향성을 가지는 (즉, 가운데 선이 화살표 모양으로 표시될 수 있는)

Graph 도 있다.

Graph는 객체들 사이의 관계나 연결에 따라 정의되는 문제들을 모델링하는 데 주로 사용된다.

객체는 정점(Vertex)으로 표시되고 객체들 사이의 관계나 연결은 정점들  정점들 사이의 에지(Edge)로 표현된다.

그래프의 탐색방법은 Vertex 를 특성 순서로 방문하는 기법이다.

여기에는 Breadth-First Search(BFS)와 Depth-First Search(DFS)가 있다.

이 글에서는 Graph 와 Graph traversal(그래프 탐색방법)에 대해서 알아 볼 것이다.

그래프는 다음과 같은 어플리케이션에서 사용된다.

- 그래프 알고리즘

- 위상 정렬: 예를들면, 와우의 스킬트리를 Linear List 로 만드는 것이랄까...

- 그래프 색칠하기: 각 Edge로 연결된 Vertex는 서로 다른 색을 칠하는 문제. 이 기준을 만족시키는 최소의 색 수를

                          Chromatic number라 한다.

- 해밀턴 사이클 문제: 한 Vertex에서 출발하여 모든 Vertex들을 한 번씩만 방문하여 시작 Vertex로 돌아오는 사이클을

                              해밀턴 사이클 이라고 한다.

                              TSP(Traveling Salesman Problem, 외판원 여행 문제)가 해밀턴 사이클 문제의 특수한 경우.

- 클릭 문제: Clique(클릭)이란, Undirected Graph 'G' 의 Vertex들로 이루어진 집합이 있을 때, 이 집합의 임의의

                 두 Vertex가 모두 Edge로 연결되어 있다면 이 집합을 Clique이라 한다.

                 예를들면, 오각형 안에 별이 그려져 있는 그래프를 생각해 보라.

- 충돌 직렬화: (설명이 좀 힘들어 패스. 사실 나도 어렴풋이 감이 오는 정도이기도 하고..;;)

그래프(Graph)

Graph는 두 가지 요소, Vertex와 Edge로 이루어진다.

Vertex는 객체를 의미하고 Edge는 객체들 사이의 관계나 연결을 말한다.

또한 Graph는 Directed(방향성)/Undirected(무방향성)이 있다.

Directed Graph는 Edge를 화살표로 표시한다. 때로는 이 Edge를 Arc라고 부르기도 한다.

Directed Graph에서 Cycle이 없는 Graph를 Directed Acyclic Graph(DAG)라고 한다.

Edge는 라벨이나 숫자값과 같은 Edge value를 가질 수도 있다.

Graph의 기본 인터페이스는 다음 링크에서 확인 할 수 있다.

http://en.wikipedia.org/wiki/Graph_%28data_structure%29#Operations

(Vertex 추가/삭제 인터페이스도 필요하다면 추가를 해야 할 것이다)

Graph는 두 개의 다른 자료구조료 표현할 수 있다.

List 와 Matrix 이다.

두 개의 큰 차이는 Adjacent vertex들를 List로 표현하는가 Matrix로 표현하는가의 차이이다.

List로 표현하는 방법은 쉽게 머리속에 상상할 수 있다. (Adjacency List)

Matrix로 표현하는 방법은 아래 그림과 같다. (Adjacency Matrix)

(출처: http://en.wikipedia.org/wiki/Adjacency_matrix#Examples )

그림과 같은 Row 1 은 Vertex 1 와 연결된 Adjacent vertex들을 나타낸다.

Undirected Graph는 Matrix가 대칭적으로 나타난다.

Directed Graph에서 1 --> 2 라면, (Row 1, Col 2)는 1 이고,  (Row 2, Col 1)은 0 이 될 것이다.

이 두가지는 어떤 차이점이 있을까?

(V는 Vertex들의 갯수, E는 Edge들의 갯수)

그래프 탐색(Graph traversal)

Graph의 Vertex들을 특정 순서대로 한 번씩 방문하는 것을 말한다.

여기에는 두 가지 방법이 있는 데, 너비 우선(Breadth-first) 탐색과 깊이 우선(Depth-first) 탐색이 있다.

- Breadth-First Search(BFS)

Graph 를 더 탐험하기 전에 한 정점에 인접한 정점들을 먼저 방문하는 것이다.

(Author: Alexander Drichel, 출처 : http://en.wikipedia.org/wiki/File:Breadth-first-tree.svg )

위 Graph의 Vertex에 적힌 숫자가 방문 순서이다.

BSF는 최소 신장 트리(minimum spanning trees)와 최단 경로(shortest paths) 등, 많은 어플리케이션에 유용하다.

그 외에도 http://en.wikipedia.org/wiki/Breadth-first_search#Applications 여기에서 여러가지 적용의 예를 볼수 있다.

BSF의 구현을 Pseudocode 로 작성해 보면 다음과 같다.

- Depth-First Search(DFS)

Graph를 탐색할 때, 한 브랜치를 따라 가능한 멀리까지 먼저 방문하는 것이다.

(Author: Alexander Drichel, 출처:http://en.wikipedia.org/wiki/File:Depth-first-tree.svg )

DFS는 사이틀 탐지(cycle detection)와 위상 정렬(topological sorting)을 포함한 많은 어플리케이션에 유용하다.

그 외에도 http://en.wikipedia.org/wiki/Depth-first_search#Applications 여기에서 다른 적용 예를 볼 수 있다.

특히 DFS를 이용하여 미로를 만드는 것은 비디오로 감상해 볼 수 있다.

DFS의 구현을 Pseudocode 로 작성해 보면 다음과 같다.

결론

Graph 자체는 별로 어렵지 않은 듯 한데...

책에도 적혀 있듯이, 아주 유연한 자료구조이다.

그래서인지 Java API 에도 STL 에도 Graph 자료구조는 없다.

이 후의 Graph 알고리즘에서 좀 더 사용해보면 익숙해 지겠지..

힙과 우선순위 큐도 별로 어렵진 않다.

물론 깊이 들어가면 어려운건 매 한가지지만.

어쨌거나 기본적인 개념은 어려운것이 아니니...

힙(Heap)

위키피디아의 정의에 따르면,

힙이란 힙 속성(heap property)를 만족하는 특별한 트리 기반의 자료 구조란다.

힙 속성(heap property)란?

만약 B 가 A 의 자식 노드라면, key(A) >= key(B)를 만족하는 것이다.

좀 더 쉽게 말하면 가장 큰 값을 가지는 노트가 항상 Root 가 되는 것이다.

( Author:  Ermishin, http://en.wikipedia.org/wiki/File:Max-Heap.svg )

위 그림과 같은 예가 힙이다.

힙은 모든 항목들이 정렬되는 것이 목표가 아니라, 가장 크거나 작은 항목만 빨리 찾을 때 좋은 자료 구조이다.

힙은 왼쪽 평형을 이루기 때문에 노드가 추가 될 때, 트리는 단계별로 왼쪽부터 채워진다.

그리고 이런 힙을 표현하는 좋은 방법은 배열에 저장하는 것이다.

왼쪽 평형을 이루는 트리를 배열에 저장할 때의 장점은

힙의 마지막 노드의 위치를 빨리 알 수 있게 되는것이다.

( 힙에서 데이터를 삽입 할 때, 삽입 위치는 마지막 노드의 다음 노드에 삽입한 후,

연산을 시작하기 때문에 이것은 중요하다. )

또한 i 번째 노드의 부모의 위치는 floor((i-1)/2),

자식의 위치는 2i+1, 2i+2 로 찾기 쉬운 장점도 있다.

힙의 인터페이스는 insert 와 extract 정도...

임의의 data 를 delete 하는 인터페이스는 없다.

우선순위 큐(Priority Queue)

우선순위 큐는 힙과 동일하다. 그리고 힙의 인터페이스를 그대로 사용하면 된다.

거기에 peek 인터페이스만 추가하면 된다.

힙의 변종들(Variants)

위키피디아에는 여러 힙의 변종들이 있는데...

역시나 그 힙들의 각각이 특징을 다 외우지는 못하겠다.

http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants

위 링크에 보면 여러 힙들의 Time Complexities 가 표로 작성되어 있는데,

큰 데이터를 다뤄야 하는 경우라면, 상황에 따라서 가장 중요한 연산의 복잡도를 고려하여

여러 힙 중에서 적절한 것을 고르면 되겠다.

기타

자료 집합을 힙으로 만들 때,

모든 원소에 대해서 heap_insert() 를 하게 되면 O(n lg n) 의 복잡도를 가지게 된다.

이것을 O(n) 의 복잡도로 실행할 수 있다.

루트의 위치가 floor(n/2)-1 에서 0까지인 트리를 힙으로 계속 만들어 가면 된다고 한다.

( 사실 무슨 말인지 모르겠다. 실제 예제를 가지고 확인해 보면 좋겠다 )

이렇게 되면 O(lg n)시간에 실행되는 floor(n/2)-1 개의 연산이 있지만,

힙 만드는 과정의 절반만이 두 단계 이상의 자료 비교를 필요로 하므로 전체적인 실행시간은

O(n) 이 된다고 한다.

(2012.7.4 추가)

자료 집합을 힙으로 만들 때, O(n) 시간에 해결하는 방법은...

마지막 노드를 가지고 있는 부모 노드로 부터 - Root 의 인덱스가 0 일 때, floor(n/2)-1 번 위치부터

Root 로 가면서 Heapfy 하는 것이다.

처음에는 원소가 2개 혹은 3개를 가진 트리 형태를 전부 Heapfy 하고,

그 윗 단계로 가게 되면, extract 이후에 Reheapfy 하는 과정..

즉, Root 와 그 자식들을 비교해서 Heapfy 하는 과정을 계속 반복하는 것이다.

결론

기본 힙은 쉬운거 같다.

근데 힙의 Variants 들도 참 많다.

각 Variants 들의 특징도 한번씩 살펴보면 좋겠지만.. 시간이 될까?

트리에 대한 자료를 찾으면서 우선 위키피디아를 한 번 쭉 읽어 봤다.
그 중 바이너리 트리의 마지막 부분(http://en.wikipedia.org/wiki/Binary_tree#External_links)을 보면

'Trees in computer science' 를 보면 엄청난 종류의 트리들이 나온다.

이걸 보면서 느낀 건, "아, 정말 사람들이 치열하게 고민을 했구나...' 하는 것이다.

약간의 성능 향상이라도 얻기 위해 이 부분, 저 부분 고민을 한 흔적이 느껴졌다.

( 이 수많은 트리들이 그냥 나온건 아니니깐... )

마음 같아선 저 모든 트리들의 특징을 정리해 보고 싶지만... 그건 힘들것 같고,

일반적으로 트리를 사용하는 이유(효율적인 탐색!!!)에 집중해서 정리해 본다.

트리(Tree)

먼저 아래 그림을 보자.

( http://en.wikipedia.org/wiki/File:Binary_tree.svg )

이미지로 표현을 하자면 위와 같은 모양으로 자료가 저장되는 자료구조가 트리(Tree)다.

트리에서 사용하는 용어들은 다음과 같다.

- 노드(Node): 위 그림에서 데이터 및 다른 데이터를 가리키는 포인터를 포함해서 노드(Node)라고 한다.

- 루트(Root): 트리에서 제일 상위에 있는 노드를 루트라고 한다.

- 자식(Child): 한 노드의 바로 아래(포인터를 가지고 있는) 노드를 말한다.

- 부모(Parent): 한 노드의 바로 상위 노드를 말한다.

- 분기 계수(branching factor): 한 노드가 가질 수 있는 자식의 최대 수를 말한다.

- 형제(sibling): 부모의 다른 자식 노드들이다.

- 자손(descendant): 한 노드에서 뻗어나간 하위의 모든 노드들을 말한다.

- 조상(ancestor): 한 노드와 루트 간의 경로에 있는 모든 노드들이다.

- 높이(height): 노드들이 존재하는 단계의 수. 트리의 높이. 예를 들면 위 그림의 높이는 4 이다.

- 리프 노드(Left Node): 자식이 없는 노드.

기본적인 용어들은 머 이 정도?

트리는 다음과 같은 곳에서 사용된다.

- 허프만 코딩: 자료 집합을 압축하는데 사용하는데 허프만 트리를 사용하는 자료 압축 방법

- 프로그램 메뉴

- 데이터베이스 시스템

- 식 처리: 컴파일러나 휴대용 계산기에서 자주 수행되는 작업이다.

- 우선순위 큐

이 글의 이후 내용은 다음과 같은 내용을 다루겠다.

- 바이너리 트리(Binary Tree, 이진트리)

- 순회 방법(Travesal)

- 트리 평형,

- 바이너리 서치 트리(BST, Binary Serarch Tree, 이진탐색트리)

- 그 외 주제에 대해서

바이너리 트리(Binary Tree, 이진 트리)

자식을 2개까지 가질 수 있는 노드들로 이루어진 트리다.

광범위하게 사용되며, 더 복잡한 트리 구조체의 토대도 된다.

순회 방법들(Traversal)

트리의 노드들을 방문하는 순서에 대한 내용이다.

- preorder (전위 순회) : Parent -> Left -> Right

- inorder (중위 순회) : Left -> Parent -> Right

- postorder (후위 순회) : Left -> Right -> Parent

앞에 접두사가 현재 노드의 방문 순서를 가리킨다고 생각하면 된다.

그리고 노드의 방문은 Recursive 하게 방문한다.

바이너리 서치 트리(Binary Search Tree, BST, 이진 탐색 트리)

탐색을 위해 특별히 구조화된 이진 트리이다.

부모보다 작은 노드는 왼쪽 자손에 부모보다 큰 노드는 오른쪽 자손에 위치한다.

( http://en.wikipedia.org/wiki/File:Binary_search_tree.svg )

예를 들면, 위 그림과 같이 트리를 구성하게 된다.

BST 의 탐색 속도는 트리가 평형을 유지한다면 O(lg n)이 된다.

(트리 평형을 이룬다는 말은 트리의 주어진 노드의 갯수에 대해 트리의 높이를 짧게 유지한다는 것이다)

트리가 균형을 이루지 못한다면 최악의 경우 O(n)이 된다.

이 차이는 매우 큰 데, 2^16 개의 데이터를 검색할 때

O(lg n)는 최대 16번, O(n)은 최대 65,536번의 탐색이 필요하다.

여기까지는 솔직히 별로 어렵지 않다.

하지만 트리의 평형을 어떻게 유지하는 가에 대한 문제로 들어가면 쉽지 않다.

트리 평형(Tree Balancing)

위에서 잠깐 언급했듯이,

트리 평형이란 주어진 노드들의 개수에 대해 트리의 높이를 가능한 짧게 유지하는 것이다.

트리의 평형은 데이터 서치의 성능에 영향을 미친다.

바이너리 트리에 노드를 Insert, Delete 할 때, Balancing 을 유지하는 트리에는 여러 방법이 있다.

이러한 트리들을 Self-balancing binary search tree 라고 한다.

( http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree )

• AA tree
• AVL tree
• Red-black tree
• Scapegoat tree
• Splay tree
• Treap

위키피디아에는 위와 같은 트리들에 대해서 언급하고 있다.

Selft-balancing binary search tree 들 중 하나 정도는 외우고 싶은데,

머가 제일 쉬운지 모르겠다.

그 외 트리에 대해...

- 수식의 표현

바이너리 트리는 탐색에 특화된 것으로 보이지만,

다른 곳에도 응용이 가능하다.

예를 들면 수식을 표현하는 데, 좋은 방법이 된다.

- 트라이(Trie)

가변 길이 문자열 집합을 탐색하는 데 주로 사용된다.

( http://en.wikipedia.org/wiki/File:Trie_example.svg )

- B-Tree

( B-Tree 는 Binary Tree 가 아니다. 혼동하지 말자. )

보조 기억장치에 저장된 자료에 접근하는 성능을 향상시키기 위해서

대체로 데이터베이스 시스템에서 사용하는 탐색 트리다.

결론

글의 처음에 이야기 했듯이 많은 종류의 트리들이 있다.

그리고 각각의 트리들은 저마다 특징이 있다.

많은 종류덕에 이 특징들을 모두 기억하기도 쉽지 않다.

내가 생각하는 트리의 핵심은 이거다.

1. 데이터의 크기를 비교할 수 있는 데이터를 검색하는 데는 바이너리 서치 트리가 좋다.

2. 바이너리 서치 트리라면 가능하면 기본적으로 Self-balancing 이 되도록 해야 한다.

3. 다뤄야 하는 데이터의 갯수가 많다면, 그 때의 상황에 맞는 특화된 트리를 찾아본다.

4. 탐색과 관계없는 자료도 트리로 표현하는 게 좋을 때가 있다. (수식이나 디렉토리, 메뉴 처럼...)

이게 정답은 아닐수도 있겠지만, 내가 트리를 써야 할 일이 있다면...

위와 같이 고민을 하다가, 라이브러리를 찾겠지. -_-;

( 내가 특별한 상황에 있지 않는 이상 Reinvention 할 필요는 없겠지 )

마지막으로 인터넷을 검색하다가, 트리에 대한 좋은 글들이 있는 블로그를 발견했다.

http://sweeper.egloos.com/category/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/page/3

나는 머 내 맘대로 날림 수준으로 복습해 놓은거지만,

이 분은 상당히 자세히 적어 두었다.

하나 더, http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html 에 가면

Self-Balancing Binary Search Tree 과정을 시각적으로 볼 수 있다.

(2012.7.4 추가)

self-balancing search tree 의 대표적인 두 가지 방법

AVL Tree 와 RB(red-black) Tree 중 어느 것이 좋은가?

실제 나의 기억으로도 자료 구조 시간에 저 두 개의 트리에 대해서 집중적으로 배운거 같긴 하다.

결론부터 말하면 RB Tree 를 더 선호하는 것 같다.

실제로 Java 의 TreeMap 과 C++ STL std::map 에서 self-balancing search tree 의 구현은 모두

RB Tree 로 되어 있다고 한다.

http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-red-black-tree

위 글의 답변을 인용해 보면,

AVL Tree 는 최대 1.44 lg(n) 이지만 RB Tree 는 최대 2 lg(n) 이라고 한다.

그럼에도 불구하고, RB Tree 를 쓰는 이유는

삽입/삭제 후의 Re-balancing 에 드는 코스트 때문이란다.

AVL Tree 의 경우 O(lg n) 이지만, RB Tree 는 O(1) 이다.

그래서 빈번한 RB Tree 가 search 에 조금 약 할지라도,

삽입/삭제에서 훨씬 강하니... RB Tree 를 선택한게 아닐까?

(2012.7.5 추가)

둘 다 구현하다가 시간 문제로 포기.

아.. 학교다닐 때 열심히 할 껄... 이라는 생각도 해 봤지만,

어짜피 기억 안나는건 같았을껄?

AVL 은 Balacing-Factor 를 가지고 Re-balancing 을 하고,

RB Tree 는 red-black properties 에 따라 Re-balancing 을 한단다.

후.. 나중에 필요하면 다시 공부하자.

* RB-Tree 는 http://en.wikipedia.org/wiki/Red%E2%80%93black_tree 에

  상세하게 설명되어 있다. 약간만 더 손보면 되는 코드와 함께!

8장 해쉬 테이블이다.

(책에는 해시 테이블이라고 적혀 있지만, 난 해쉬가 어감이 더 좋아서...)

바로 고고싱...

해쉬 테이블(hash table)

해쉬 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성되는 자료구조 이다.

해쉬 테이블의 해쉬 함수는 키 값을 받아 그 키의 해쉬값(hash coding 또는 hash value)을 리턴한다.

간단한 해쉬테이블을 시각적으로 표시했을 때, 아래와 같은 그림으로 표시할 수 있다.

(Author: Jorge Stolfi, 원본: http://en.wikipedia.org/wiki/File:Hash_table_3_1_1_0_1_0_0_SP.svg)

해쉬 테이블의 장점은 상수 시간에 탐색이 가능한 것이다.

대신 다른 특징(혹은 단점?)은 순차적인 접근을 지원하지 않는 것이다.

따라서 이러한 특징에 맞는 상황에서 사용되어야 할 것이다.

추가적으로 해쉬 테이블의 특징을 좀 더 알아보자.

- 사용할 키와 해쉬 함수를 잘 선택하여 테이블에 균등하게 항목이 배분되도록 해야 한다.

- 다른 키값에 대해 같은 해쉬값(같은 테이블로 매핑되는 경우)을 가지는 경우 충돌(collision)이라고 한다.

- 충돌 해결 방법에는 여러가지가 있으며 대표적인 방법(책에 설명된)은

  연쇄 해쉬 테이블(chained hash table)과 개방 주소지정 해쉬 테이블(open-addressed hash table)이 있다.

위키피디아에 따르면 해쉬 테이블은 탐색 트리(search tree)나 다른 lookup 구조의 테이블보다 효율적이라고 한다.

이런 이유로 아래와 같은 곳에서 사용이 된다. (참조: http://en.wikipedia.org/wiki/Hash_table#Uses )

- Associative arrays (프로그래밍 랭귀지의 데이터 타입 같은 것. 예를 들면 Python 의 Dictionary 타입?)

- Database indexing

- Caches

- Sets

- Object representation

- Unique data representation

위키피디아에 상세한 설명이 되어 있으니, 해쉬 테이블에 대한 더 많은 정보를 원한다면 방문해 보기 바란다.

http://en.wikipedia.org/wiki/Hash_table

앞으로 나올 용어에 대해서 간단히 설명하면 다음과 같이 사용할 것이다.

n : 테이블의 항목 갯수

m : 버킷의 갯수

a : 부하 계수(load factor). a = n / m

해쉬 테이블 인터페이스

해쉬 테이블에 필요한 인터페이스는 간단한 편이다.

Data Insert, Remove, Lookup 정도?

중요한 건 키 값을 같이 넘겨주는 것이다.

해쉬 함수(hash function)

해쉬 함수 h 는 키값 k 를 받아 테이블 위치 x 에 매핑하는 함수이다.

k 의 값은 보통 정수임을 가정한다.

k 가 정수가 아니더라도 어렵지 않게 정수로 바꿀 수 있다.

(물론 k 가 같은 값이 나오지 않게 잘 바꿔야 하겠다)

책에서는 간단한 방법 2가지를 제시한다.

- 나눗셈 방법(devision method)

으로 표현할 수 있다. 일반적으로 m 의 값으로는 2의 제곱수는 피해서

2의 제곱수에 가깝지 않은 소수를 m 으로 선택한다.

- 곱셈 방법(multiplication method)

k*A 한 다음 여기에서 소수 부분만 택하여 m 을 곱한값에서 정수 부분만 택한값을 사용한다.

( A 값은 저렇게 하면 효율적이라고 Donald Knuth 란 분이 이야기 했나 보다. )

이것들은 간단한 방법들이니 좀 더 효율적인 해쉬 함수를 원한다면,

좀 더 공부가 필요하겠다.

충돌 해결(Collision resolution)

출동 해결 방법에는 여러가지가 있다.

좀 더 자세한 건 역시 위키피디아! ( http://en.wikipedia.org/wiki/Hash_table#Collision_resolution )

- 연쇄 해쉬 테이블(Sererate Chaining)

(Author: Jorge Stolfi, http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_LL.svg )

위 그림과 같이 한 버킷을 링크트 리스트로 구성하는 방법이다.

- 개방 주소지정 해쉬 테이블(Open addressing)

(Author: Jorge Stolfi,http://en.wikipedia.org/wiki/File:Hash_table_5_0_1_1_1_1_0_SP.svg )
그림이 좀 헷갈려 보이긴 하지만, 위와 같은 충돌 발생시 다른 버킷에 저장하는 방식이다.

여기서 잠깐, 다른 버킷은 어떻게 선택하는가?

잘 알려진 방법으로는 다음과 같은 3가지 방법이 있다.

1. 선형 조사(Linear probing) : 다음 버킷을 조사. 주클러스터링 현상으로 과다한 조사 발생 가능성 있음.

2. 2중 조사(Quadratic probing) : i^2 번째의 버킷을 조사. 부클러스터링 현상으로 과다한 조사 발생 가능성 있음.

   (i 는 현재까지 조사한 위치의 갯수)

3. 2중 해싱(Double hashing): 해쉬 함수와 보조 해쉬 함수의 결과를 더하는 것이다.

2중 조사와 다른 점은, 키 값에 따라 다음 조사위치가 고정된 것이 아니라 달라진다는 것이다.

수식으로 표현하지면 위와 같다. 그러나 어떤 위치가 두 번 조사되기 전에 모든 위치들이

조사됨을 보장하기 위해 다음의 두 절차 중 하나를 따라야 한다.

a. m이 2의 제곱수이고 h2 가 항상 홀수를 리턴한다.

b. m이 소수이고 h2는 항상 m보다 작은 양수를 리턴해야 한다.

결론

여기에 적은 것은 해쉬 테이블의 일부분일 뿐이다.

이 글에서는 해쉬 테이블의 핵심만 기억하도록 하자.

해쉬 테이블의 정의, 좋은 해쉬 함수가 필요하다는 거, 그리고 충돌 해결이 필요하다는 거 정도?

역시 중요한 것은 실제로 적절한 곳에 사용하는 것이겠지...

해쉬 테이블에 대한 깊이 있는 이해를 위해서는 좀 더 공부가 필요하겠다.

(2012.7.2 추가)

Double Hashing이 항상 좋은 것은 아니다.

예를 들면 Double Hashing 함수에서 i 값이 증가 할 때, 그 interval 이 커서

cache 문제가 발생할 수 있다고 한다.

(참고: http://en.wikipedia.org/wiki/Double_hashing )

찾지를 못하겠다. 나중에 꼭 쓸일이 있게되면 연구해 봐야겠다.

(2012.7.3)

굳이 인터넷을 검색하지 않아도,

책에 적절한 Double Hashing 의 적절한 샘플이 있었다.

(어젠 책이 없는 관계로...)

이 식에서 아래와 같은 방법의 해쉬 함수를 사용할 수 있다.