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 라이브러리가 있는데,

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

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

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

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

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

D-Link DNS-323 은 상당히 흥미로운 아이템이다.

기본 펌웨어선 NAS 기능 외에 FTP 서버와 iTunes 서버정도의 역할밖에 하지 못한다.

하지만 fun_plug 라는 스크립트 파일을 통해 custom boot script 를 실행시킬 수 있는 기능이 있다.

이걸 이용하여, DNS-323 에 여러가지 기능을 추가할 수 있다.

Transmission 이라는 Torrent 도 돌릴 수 있는 것이다.

fun_plug 에 대한 더 자세한 내용은 http://dns323.kood.org/howto:fun_plug 에서...

fun_plug 중 가장 유명한 것이 ffp 라 불리는 Fonz fun_plug이다.

일단 ffp 설치법은,

http://forum.dsmg600.info/viewtopic.php?pid=45488#p45488

이 글대로 하면 되겟다. 영어가 약하다면 한국 블로거 중에도 설치 방법을 적어둔 분들이 있으니 참고.

(하지만 최신버전인 0.7 에 대해서 적어놓은 것은 못 본거 같다.)

그리고 Transmission 설치는

http://forum.dsmg600.info/t2719-%5BREL%5D-Transmission.html 참고.

마지막으로 중요한 것.

ffp 설치하고 나서, DNS-323 의 웹 인터페이스나 버튼을 통해 종료하게 되면,

ffp 에서 mount 한 파일시스템이 정상적으로 unmount 되지 않기 때문에,

cleanboot 라는 것을 설치하여, ssh 나 telnet 을 통해 reboot / shutdown / halt 를 해야 한다.

하지만 문제는 0.7 버전에서는 설치가 안된다는거.

http://dns323.kood.org/howto:cleanboot

위 링크에 보면 설치법이 있는데,

파일이름을 cleanboot-2.1-ffp05.tgz 를 cleanboot-2.1-arm-1.txz 로 바꾸어 주면

설치가 된다. 잠깐 테스트 해 본 결과 잘 동작하는 듯 하다.

(저 위키의 파일 이름 바꾸라는 이야기는 내가 추가해 둔거다.)

p.s

혹시나 해서 위의 웹페이지는 개인적으로 저장해 두었다.

그러나 저작권이 걱정되어 따로 파일 링크를 걸지는 않겠다.