알고리즘 작성 방법

분할 정복(Divide and Conquer)

---

분할 정복(divide and conquer)이란 해결해야 될 문제를 작은 단위로 나누어 더 이상 나눌 수 없어지는 단계가 되면 그 단계에서 문제를 해결하고 이를 통해 본래 문제로 거슬러 올라가는 방식의 문제해결 방법이다. 때로는 가장 작은 단계의 해답이 본래 문제의 해답이 되기도 한다. 분할 정복의 사용 예시로는 합병 정렬(merge sort)가 있다.

 

합병 정렬 알고리즘

 

 

동적 계획법(Dynamic Programming)

---

 동적 계획법(Dynamic Programming)은 문제를 분할한다는 점에서는 분할 정복과 같지만 이전 문제의 해답을 이용하여 다음 문제를 푼다는 점에서 분할 정복과의 차이점을 보인다. 팩토리얼을 예로 들어 설명하도록 하겠다. 우리가 10!의 해답을 구하면 이 해답을 어떠한 저장 공간에 저장시킨다. 다음에 11!을 구하면 분할 정복의 경우 처음부터 다시 계산을 시작하지만 동적 계획법의 경우 이전에 저장해둔 10!에 11을 곱하는 방식으로 작동한다.

 

 동적 계획법은 최단 경로 문제와 같이 동일한 하위 계산을 여러 번 해야하는 문제에서 계산 횟수를 줄여줌으로써 더 효율적인 계산을 할 수 있도록 도와준다.

 

 

 

탐욕적인 방법(Greedy Approach)

---

 탐욕적인 방법(greedy approach)는 각 문제에서 가장 최적이라고 생각되는 해를 선택하여 최종 문제의 최적의 해답을 도출해내는 방법을 말한다. 예를 들어 설명하자면 우리가 물건을 계산한 후 거스름돈 2500원을 줘야한다고 해보자. 우리는 먼저 1000원 두 장을 준 다음 500원을 줌으로써 2500원을 거스름돈으로 줄 수 있다. 이는 500원을 5개 주는 것보다 훨씬 좋은 방법이다. 하지만 항상 탐욕적인 방법이 최적의 해를 가져다 주는 것은 아니다. 이번에는 2200원짜리 지폐가 있다고 가정하고 2500원을 계산해보자. 그러면 2200원짜리 1장과 백 원짜리 3개를 주면 2500원을 맞출 수 있다. 하지만 앞서 2500원은 1000원짜리 2장과 500원 짜리 1개로 맞출 수 있으며 이는 더 적은 개수로 2500원을 맞출 수 있다. 

 

탐욕적인 방법은 2가지 조건을 만족할 때 사용하면 좋은 결과를 낼 수 있다.

1. 탐욕적인 선택 조건(Greedy-choice property) : 하위 문제의 결과와 상관없이 부분 문제에서 최적의 해를 선택하면 전체의 최적의 해에 도달할 수 있다.
2. 최적 부분 구조(Optimal substructure) : 부분 문제에서의 최적의 해는 전체 문제에서의 최적의 해와 같다.