요즘 알고리즘 공부하면서 느끼는 가장 어려운점은 해결해야할 문제에 적용할 알고리즘을 선택하는 과정이다. 사실 적용할 알고리즘을 찾았어도 해당문제에 맞게 변형하여 적용하는것이 진짜 어려운데 난 머리가 나빠서 그런지 먼저 적용할 알고리즘을 선택하는 과정에서도 골치를 섞는다. 그래서 나름 요령을 정리해보기로 했다.

사실 ‘알고리즘 문제 해결 전략’ 책을 보면 다양한 알고리즘들의 원리와 적용 대상이 상세히 나오긴 하는데 매번 수페이지나 되는 내용들을 들춰보기도 힘들고 해서 나름 한두줄 정도로 정리한 요약 판을 만들어 보면 어떨까 하는 생각이 들었다.

뭐 얼마나 쓸모있을지는 알 수 없지만, 안하는것보다 나을거 같으니 일단 분할정복부터 시작해본다.

분할정복(divide and conquer)

개요

문제의 범위를 더 작은 단위로 쪼개어 해결한 뒤 각각의 중간 결과를 합하여 최종 결과를 도출하는 문제풀이 기법이다. 대표적인 사례는 머지소트와 퀵소트이다. 문제를 해결하는 함수 f(n)를

 { f(1) = c , f(n) = C + 2f(n/2) }

의 형태로 변형할 수 있을 때 적용할 수 있다. 그냥 말로는 쉬운데 실제로 적용 포인트를 찾는게 생각보다 어렵다.

설명

보통 O(n²)의 시간이 걸리는 계산(함수)를 O(nLog(n))시간대로 최적화 할때 분할정복을 사용할 수 있다. O(n²)의 시간이 걸리는 함수의 계산 과정을 다음을 만족하는 계산과정으로 변형하면 분할정복이 가능하다.(사실은 가능할거 같다 -.-; 그냥 깔짝깔작 공부하나 얻은 요령이다보니 수학적 근거는 없다.)

1. 함수내에 중간 결과를 처리하는 과정(A라 하자)가 있다.
2. A가 한번 수행되면 현재의 데이터는 두개로 나뉘어지고 각각 나누어진 데이터들은 상호 완전히 독립되어(배타적이라고 해야하나?) 다시 A에 적용된다.

분할정복의 대표적인 예인 퀵소트를 살펴보면 pivot 값을 기준으로 정렬할 데이터를 나누는 과정 A가 있고 이 A가 수행될 때마다 데이터는 pivot을 기준으로 자연스럽게 좌,우로 나뉘어져 2를 만족한다. 다음 계산에서 pivot을 기준으로 좌우로 나뉜 데이터는 각각 독립적으로 다시 A가 적용되며 정렬이 반복된다. 이런 방식으로 A과정이 N번 반복될때마다 2ⁿ개의 정렬된 원소들을 얻으며 최종적으로 O(nLog(n))의 시간을 얻을 수 있다.

셀렉트 소트와 비교를 하며 생각해 보면 이해가 쉽다.

셀렉트 소트

1. 전체배열을 한번 비교하여 가장 작은 원소를 찾는 select 과정을 A라고 하면 n번째 수행에서 (배열크기-n)의 시간을 소요하여 결과적으로 O(n) 시간 소요한다.
2. A가 n번 반복될때마다 1개의 정렬된 원소를 얻으므로 이것을 n-1번 반복하여 정렬된 결과를 얻는다. 최종 결과로 O(n²)시간을 소요한다.

퀵소트

1. pivot기준으로 원소를 좌우로 나누는 계산을 A라고 하면 A는 n번째 반복마다 n개로 쪼개진 영역별로 수행 되어 평균 (배열크가-전체pivot갯수) 시간 소요한다. 결과적으로 O(n) 시간을 소요한다.
2. A가 n번 반복될때마다 데이터가 2ⁿ개의 구역으로 나뉘며 다음계산에서 나뉘어진 구역마다 A를 수행하여 2ⁿ개의 정렬된 원소(pivot)를 얻는다. 총 수행 시간은 2ⁿ을 역산한 log(n)으로 최종 결과로 O(nLog(n))의 시간을 소요한다.

맺음

개인적인 생각으로 분할정복으로 문제를 풀때 가장 중요한건 A를 잘 만드는것 같다. 사실 A가 제대로 만들어지면 2는 자연스레 해결된다. 반면 2의 데이터를 나누는 기준을 아무리 잘 잡아도 A가 똥망이면 O(n²)이 되는 처참한 결과를 얻을 수도 있다.

한번은 문제 풀면서 정말 생각없이 A를 만들었더니 대충 O(n³)의 결과가 나왔었다. 털썩….