C 로 구현한 알고리즘 - 3부 알고리즘에 들어가기 전에...

'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문제를 해결하는데 사용한다.