알고리즘을 재미있게..

# 알고리즘은 글쎄요 구지 몰라도 프로그래밍을 못하는것은 아니겠지만 어떤 문제를 해결할때 보다 생각할 시간을 줄일 수 

있는 수단이 될 수도 있겠지요 또는 효율적인 알고리즘을 보다 명분있게 구현해 나아가는데 도움도 될 수 있겠구요 .

이왕이면 공부해 두는 것이 여러모로 도움이 많이 된다고는 생각되어 지네요. 

1. 분할 정복(Divide and Conquer)

문제를 부분부분 나눠서 해결하고, 해결한 문제들을 합쳐나가면서 전체적인 문제를 해결해나가는 과정입니다. 대표적인 정렬(Sorting) 알고리즘으로 퀵소트(quick-sort)가 존재합니다.

대표적인 예 : 퀵소트 알고리즘, 하노이의 탑

2. 다이나믹 프로그래밍(Dynamic Programming)

프로그램이 알아서 문제를 해결해나가도록 만들어서 이전 결과값을 계속 활용하도록 알고리즘을 작성하는 것입니다. 재귀적인(Recursive) 문제 해결 방식이 이에 포함됩니다. 이전 상황에 대한 값을 저장하고 있어서 다시 연산을 하지 않기 때문에 무척 빠릅니다. 그렇지만 모든 상태를 저장하는 방식이라 공간 복잡도가 커집니다.

대표적인 예 : 피보나치수열 알고리즘

3. 그리디 알고리즘(Greedy Algorithm)

그리디는 욕심, 탐욕이란 의미입니다. 당장 눈 앞에 보이는 이익을 쫓아가는 문제해결방식을 보여서 이런 이름을 붙인 것 같습니다. 빠른 시간에 답에 가장 가까운 값을 계산하지만 그 값은 언제나 근사값입니다. 예외로 다익스트라 알고리즘처럼 항상 답을 줄 때도 있습니다.

대표적인 예 : 다익스트라(Dijkstra) 알고리즘, 프림(Prim)알고리즘

4. 백트래킹 알고리즘(Back-tracking Algorithm)

일단 특징부터 말씀드리면 시간이 엄청 오래 걸립니다. 모든 경우를 검사하기 때문에 대부분의 문제에서 최적의 답을 찾아냅니다. 꼭 필요한 경우에만 사용되고 '벽장문 옮기기 문제'에 사용됩니다. 알고리즘 해결책 중에서 가장 느린 방법입니다. 입력될 데이터 수가 적고, 최적의 해가 필요하다면 상당히 좋은 방법입니다.
알고리즘을 작성하는 사람이 코딩 상에서 매우 많은 경우의 수를 고려해주어야하기 때문에 실수할 수도 있는 기법입니다.

대표적인 예 : 벽장문 옮기기 (다이나믹 프로그래밍으로도 해결 가능), 미로 탈출 알고리즘

5. 국소 탐색법

정리중...


6. 시뮬레이티드 어닐링(Simulated Annealing)

어닐링(Annealing)이란 단어가 생소하실 텐데, 담금질입니다. 담금질은 금속을 녹을 때까지 가열하고 그것을 다시 고체가 되도록 굳히는 과정을 반복하는 것입니다. 그 과정에서 단련된 검이 나오듯, 문제를 해결할 때까지 입력할 데이터들을 '담금질'을 하는 것입니다. 순회판매원이 여러 나라를 돌면서 제품을 팔고자할 때 가장 적게 비행기를 타고 가야할 모든 나라를 돌면서 제품을 팔고 오는 문제 등을 해결할 때 쓰인답니다...(학부시절에 써본 적 없는 알고리즘기법이군요.)
 시뮬레이티드 어닐링은 응용 분야도 넓고 최상에 가까운 해답을 얻을 수 있습니다. 그렇지만 백트래킹과 마찬가지로 계산 시간이 엄청나게 길다는 것이 문제입니다. 대규모 병렬처리(Massively Parallel Execution)을 기반으로 계산 시간을 줄일 수 있습니다. 볼츠만 머신(Bolzmann Machine)을 참고하세요.

대표적인 예 : 순회판매원(TSP) 알고리즘()

7. 균형법

앞에서 설명한 분할정복(Divide and Conquer)의 방법을 사용하되 문제를 나눌 때 골고루 퍼뜨리는 것입니다.

대표적인 예 : 머지 소트-합병 알고리즘(Merge Sort)

8. 근사 해법

문제를 정확히 풀 수 없다는 것을 밝히고, 그나마 '이게 괜찮은 답입니다' 라고 제시하는 해결 방식입니다. 튜링이 컴퓨터모델을 설계하면서 튜링모델로 해결할 수 없는 문제들이 있다고 밝혔는데 NP-Complete한 문제는 전혀 해결이 불가능하고, NP-Hard는 아직 해결이 될지 안될지 잘 모르는 문제들에 해당합니다. 이런 부분의 문제들에 대해서 알고리즘을 설계하려고 하는 시도는 매우 소모적이고 우스꽝스러운 일입니다. 그래서 해당 문제를 해결하는 최적값을 제시하진 못하지만 이렇게 해결할 수는 있습니다라고 우회적인 알고리즘 해결방식입니다.

<출처 : http://www.aistudy.com/algorithm/design_park.htm >