Azza's Blog

스트래티지 패턴(strategy pattern)

: 객체의 Action 의 내용을 캡슐화 하여 교환해서 사용할 수 있도록 만든다.

책에서 처음 설명하는 Duck 클래스는,

quack() 메소드와 fly() 메소드를 별도의 인터페이스로 분리하고

이 인터페이스를 구현하는 클래스를 만들어 사용하는 것이다.

그리고 Duck 을 상속받은 클래스는,

생성자에서 해당 클래스에 맞는 quack() 와 fly() 인터페이스를 구현한 클래스를 

사용하도록 한다.

수많은 Sub class 가 몇 가지 중복된 행동에서 한 가지를 선택해야 하는 경우라면,

코드 재사용 및 유지 보수를 한꺼번에 해결 할 수 있는 좋은 패턴이다.

하지만 스트래티지 패턴의 더욱 큰 장점은

실행시간에 Action의 내용 (알고리즘, 즉 메소드의 내용)을 바꿀 수 있다는 것이다.

예를들면, 액션 게임의 케릭터가 무기가 바뀌었을 때,

스트래티지 패턴을 사용하였다면, 단순히 attack() interface 를 구현한 클래스만 교체해 주면 해결된다.

과연, 책의 1장에서 소개해 줄 만한 쉽고도 강력한 패턴이다.

예제코드 (원문: http://en.wikipedia.org/wiki/Strategy_pattern#Example)

'C로 구현한 알고리즘' (Algorithms with C) 의 간단한 리뷰를 남겨본다.

먼저 자료구조 부분은 괜찮았다.

실제로 동작하는 소스 코드도 제공하고,

어느 정도 기본을 익히기에는 충분하다고 생각한다.

알고리즘 부분에 대해선 내가 원하는 스타일은 아니었다.

내가 원했던 것은, 알고리즘 접근 방법에 따라 분류를 나누고

(Divide&Conquer, Dynamic Programming, Greedy Algorithm, Heuristic Algorithms 등...)

이 방법을 이용해 문제를 해결하는 것을 원하였는데,

이런 설명 보다는 적용 분야에 따라 주제를 나누고 설명한 것이 별로였다고 본다.

( 물론 기하 알고리즘과 같은 새로운 분야에 대한 이야기는 흥미로지만 )

특히, 강력하지만 익숙해지기 어려운 Dynamic Programming 에 대한 설명은

거의 전무했다는 점에 대해선 실망스럽다.

결론은,

컴퓨터 프로그래밍 공부를 위해 알고리즘 책을 선택해야 한다면, 추천하고 싶진 않다.

앞에도 이야기 했듯, 자료 구조 내용은 나쁘진 않았지만,

알고리즘 책으로써는 별로라고 생각한다.

1. 선분 교차 테스트

2. 컨벡스 헐

3. 구면 위의 호의 길이

를 다룬다.

이전 TSP 에서 선분교차에 대해서 자세한 방법에 대한 이해를 못하여,

대충 직사각형 교차 체크만 하고 넘어갔기에, 거기에 대해 좀 자세히 알아보고,

나머지는 개념만 이해하고 넘어가겠다.

1. 선분 교차 테스트

점 A, B, C, D 에 대하여

선분 AB 와 선분 CD 가 서로 교차하는지,

컴퓨터를 이용하여 확인하는 방법에 대한 것이다.

수학에서라면 간단히 두 선분의 직선의 방정식의 해를 구하여

그 해가 선분의 범위안에 들어가는지 체크하면 쉽지만,

일반적으로 정확한 실수 연산이 되지 않는 컴퓨터 언어로는

그렇게 간단히 되지 않는다.

그래서 다음과 같은 2 단계를 따른다.

i) 선분의 양 끝 점을 대각선으로 하는 직사각형을 그려 교차하는 부분이 있는지 체크 한다.

   교차하는 부분이 없다면 교차하지 않음. 교차하는 부분이 있다면 ii) 로.

ii) 삼각형 ABC와 삼각형 ABD의 Signed Area의 곱이 <= 0, (곱이 0 이라면 선분이 겹치는 경우)

   AND 삼각형 CDA와 삼각형 CDB의 Signed Area의 곱이 <= 0 인지 확인.

i) 조건을 패스하고 ii) 조건이 True 가 된다면 두 선분은 교차한다.

Signed Area 는 세 점으로 만들어지는 면적을 구하는 데,

세 점의 방향에 따라 '+' 나 '-' 값을 가진다.

Signed Area 를 구하는 방법은 다음과 같다.

점 A, B, C 의 (x, y) 좌표를 각각 (a[0], a[1]), (b[0], b[1]), (c[0], c[1]) 이라고 했을 때,

삼각형 ABC의 Signed Area = ( a[0]*b[1] - a[1]*b[0] + b[0]*c[1] - b[1]*c[0] + c[0]*a[1] - c[1]*a[0] ) / 2

공식으로 구할 수 있다.

2. 컨벡스 헐(Convex Hull)

어떤 점 집합의 컨벡스 헐은 그 집합의 모든 점들을 포함하는 가장 작은 볼록 다각형을 말한다.

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

위 그림에서 파란색으로 표시된 다각형이 바로 컨벡스 헐이다.

점 집합 P에 대한 컨벡스 헐을 만드는 한 방법은 Jarvis 행진(Jarvis's march)이라는 방법을 사용하는 것이다.

위와 같이 P0 에서 시작하여 각 점에 대하여 각도가 가장 작거나 큰 점들을 찾아서 계속 연결해 나가면 된다.

3. 구면 위의 호의 길이

구면 위의 두 점이 있을 때, 두 점의 거리(호의 길이를 말함)를 계산하는 방법에 대한 것이다.

자세한 수식은 생략하고 간단히 과정을 설명하겠다.

1. 두 점 A, B 의 좌표가 (x,y,z) 형태가 아닌,

   (구의 중심으로 부터의 거리, xz평면에서 y축 방향으로의 각도, yz평면에서 x축 방향으로의 각도) 형태로

   주어질 경우 (x,y,z) 형태의 좌표로 바꾼다.

2. 벡터의 내적을 이용하여 두 점 A, B의 각도(a)를 구한다.

3. 아래와 같이 원의 호를 구하는 공식을 이용하여, 호의 길이를 구한다.

결론

기하 문제들을 컴퓨터로 표현하고 해결하는 것은 흥미로운 과정이다.

특히, 게임 프로그래밍에 관심이 있다면 필수 과목이 아닐까?

이번엔 그래프 알고리즘 두 번째,

Dijkstra 알고리즘과 TSP 문제에 대해서 정리해 보자.

- Dijkstra 알고리즘

일반적으로 '다익스트라'라고 읽었던 것 같은데...

위키피디아에는 '데이크스트라'가 제대로 된 이름이라고 하는거 같다.

이 Dijkstra 알고리즘은 Edge의 Weight가 양수인 Graph가 있을 때,

두 Vertex간의 Shortest Path를 찾는 알고리즘이다.

(* Edge의 Weight가 음수도 있을 경우는 Bellman-Ford 알고리즘을 사용한다)

(2012.7.30 수정)

Dijkstra 알고리즘은 Greedy Algorithm이지만, Optimal Solution을 찾는 알고리즘이다!

Dijkstra 알고리즘은 Dynamic Programming + Greedy 방법으로 Optimal Solution 을 찾는 알고리즘이다.
위키피디아에 있는 Pseudocode를 보면서 알고리즘의 아이디어를 알아보자.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                               // 초기화
 3          dist[v] := infinity ;                                  // v 로부터의 거리를 아직 모름
 5          previous[v] := undefined ;                             // 최적의 경로 배열 초기화
 7      
 8      dist[source] := 0 ;                                        // 시작점 -> 시작점의 거리는 0
 9      Q := the set of all nodes in Graph ;                       // 최초에는 그래프의 모든 노드에 대하여
10                                                                 // 체크를 해야함.

11      while Q is not empty:                                    // 메인 루프
12          u := vertex in Q with smallest distance in dist[] ;    // 처음에는 시작점에서 시작
13          if dist[u] = infinity:
14              break ;                                           // 시작점에서 접근 가능한 모든 노드에
15                                                                 // 대하여 체크가 끝났음.
16          
17          remove u from Q ;
18          for each neighbor v of u:                            // 단, 'v' 는 Q 에 포함된 노드.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                 // Relax (u,v,a) - dist, previous 업데이트
22                  dist[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                          // dist[] 값이 변하므로, 필요시 Reorder Q.
25      return dist;

먼저 각 변수의 의미 및 설명인 필요한 라인에 대하여 알아보자.

- dist[v]: 시작 Vertex 에서 Vertex 'v' 까지의 거리. 알고리즘이 진행되면서 계속 업데이트 됨.

- previous[v]: 최적의 경로에서 Vertex 'v'의 이전 Vertex.

- Q : 최소 경로 확인이 끝나지 않는 Vertex 'v' 의 집함.

       Q 를 단순히 Linked List 나 Array 로 구성한다면, 복잡도가 O(V^2) 이 될 것이다. (그래도 구현이 쉽다)

       이 Q 의 v.key 값은 dist[v] 값이 되고, 이 key 값에 대해서 Binary Heap으로 Q를 구성한다면,

       복잡도는 O(E log V)가 된다. Fibonacci Heap 으로 Q를 구성한다면 O(E + V log V)가 된다.

                 반드시 확인해야 한다.

- 21번 라인: Relax (책에는 늦춘다) 라는 표현을 썼는데,

                 조금 설명을 해보자면 현재 dist[u] 는 최적의 경로이다.

                 여기에서 E(u,v) 를 더 했을 때 Weight 값(alt)이, 기존의 dist[v] 보다 작으면 alt 값을

                 dist[v] 의 새로운 최적의 경로로 설정하는 것이다.

- 24번 라인: Q 를 Min-Heap 등으로 구현하였을 경우,

                 Q 의 원소 'v' 의 key 값이 변경되므로 Q 를 재정렬할 필요가 있다.

위의 알고리즘이 끝난 뒤, Short Path 는 아래와 같은 Pseudocode 로 구할 수 있다.

1  S := empty sequence
2  u := target
3  while previous[u] is defined:
4      insert u at the beginning of S
5      u := previous[u]
6  end while ;

음..이건 따로 설명은 필요없어 보인다.

- TSP (Travelling Saleperson Problem, 외판원 여행 문제)

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

많은 알고리즘 책에서 설명하는 대표적인 NP-Hard 문제이다.

문제는 간단하다.

"여러 도시(Vertex)들이 있고 한 도시에서 다른 도시로 이동하는 비용(Edge weight)이 모두 주어졌을 때,

모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인가?"

그래프 이론의 용어로 설명하자면,

"Weighted Complete Graph^[각주:1](가중치가 있는 완전 그래프)에서

 가장 작은 가중치를 가지는 Hamiltonian cycle^[각주:2](해밀턴 사이클)을 구하라"

이다.

현재는 이런 문제를 다항시간에 풀 수 있는 알고리즘이 없으므로,

Heuristics(휴리스틱) 알고리즘이나 Approximation(근사) 알고리즘을 사용하여 빠르게 좋은 해를 찾는다.

(최근의 방법들은 높은 확률로 최적 해에서 2% ~ 3% 정도 오차가 있는 근사 해를 찾아낸다고 한다)

여기에는 여러가지 방법이 있을 수 있지만, 검색 좀 해보니 이런 방법들에 대한 연구는

거의 텀 프로젝트 수준이므로 패스하고,

Nearest Neighbor Algorithm 과 2-Opt Algorithm 에 대해서 설명하겠다.

- Nearest Neighbor Algorithm

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

이 방법은 단순하다. 일단 시작점이 주어지면, 시작점에서 가장 가까운 다음점을 찾아 연결한다.

그리고 그 다음점에서 다시 가장 가까운 점을 찾아 연결하는 과정으로 모든 점을 연결하고,

마지막 점과 시작점을 연결하는 것으로 완료된다.

- 2-Opt Algorithm

이 알고리즘은 처음부터 해를 찾는 알고리즘이 아니라,

NN Algorithm 등으로 찾은 해를 Improve 하는 알고리즘이다.

(더 이상 개선이 되지 않을 때 까지 반복을 하면, Local Optimal 이 되는 것이다)

(* 나의 경우엔, 두 선분의 Cross Check 가 귀찮아 대충 사각형을 그려서 겹치는 부분이 있으면,

    바꿔서 Length 를 구해보고 개선이 되면 바꾸는 방법을 사용하였기 때문에

    여러번 반복해야 했는지도 모르겠다)

간단하게 텍스트로 그려보면 아래와 같다.

 - V1   V2 -             - V1 - V3 -
      X         ==>     
 - V3   V4 -             - V2 - V4 -

V1-V4 와 V2-V3 가 Cross 하면, V1 - V2 - V3 - V4 순서를 V1 - V3 - V2 - V4 순서로 바꾸는 것이다.

요것도 그리 어렵진 않다.

하지만 TSP 문제가 아닌 Graph에서 사용하려면... Cross Check 하는 방법이 있긴 한지 잘 모르겠다.

2-Opt 의 좀 더 일반적인 방법인, Lin–Kernighan heuristic 을 사용한다면 방법이 있는거 같다.

(이것도 사실 잘 모르겠다)

어쨌거나 이렇게 근사해 구하고 개선하는 방법으로 풀면,

좋은 시간에 좋은 해를 구할 수 있는걸로~.

-- 각주 --

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

여기에 소개되는 알고리즘인 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문제를 해결하는데 사용한다.