알고리즘 레포트 - 분할 정복 알고리즘의 특징에 대해 정리하고, 분할 정복의 적용이 부적절한 경우와 적용 시 주의할

I. 서론

알고리즘 수업에서 병합 정렬을 처음 구현했을 때 이상하게 느껴졌던 점은 큰 배열을 직접 정렬하는 코드보다 배열을 계속 반으로 나누는 코드가 더 핵심처럼 보였다는 것이었다. 문제를 잘게 만들면 쉬워진다는 말은 일상에서도 자주 쓰지만 컴퓨터에서는 나누는 비용, 재귀 호출, 다시 합치는 비용까지 계산해야 한다. 분할 정복은 큰 문제를 작은 문제로 나누고 각 부분을 해결한 뒤 결과를 결합하는 강력한 설계 방식이지만, 어떤 문제든 반으로 자른다고 빨라지는 만능 기법은 아니다. 부분문제가 서로 독립적인지, 크기가 충분히 줄어드는지, 결합 비용이 얼마나 드는지, 재귀가 실제 메모리에서 어떤 부담을 만드는지 함께 봐야 한다.

II. 본론

1) 큰 입력을 재귀 구조로 바꾸는 분할 정복의 성격

분할 정복의 기본 생각은 입력 크기가 큰 문제를 같은 형태의 더 작은 부분문제로 나누는 데 있다. 부분문제를 재귀적으로 해결한 다음 얻은 답들을 결합해 원래 문제의 답을 만든다. 병합 정렬은 배열을 두 구간으로 나누고 각각을 정렬한 뒤 두 정렬 결과를 합친다. 이진 탐색은 정렬된 배열의 가운데 값을 확인하고 답이 있을 수 있는 절반만 남긴다. 퀵 정렬은 기준값을 정해 작은 값과 큰 값이 있는 구역으로 나눈 뒤 각 구역을 다시 정렬한다. 문제마다 결합 방식은 다르지만 입력 크기를 낮추는 재귀 구조를 만든다는 공통점이 있다.

분할 정복의 장점은 복잡한 문제를 구조적으로 생각하게 해 준다는 데 있다. 전체 입력을 한꺼번에 다루면 비교해야 할 경우가 많아지지만, 작은 문제의 해법을 이미 알고 있다고 보고 전체 문제를 설계하면 코드와 증명을 나누기 쉬워진다. 병합 정렬에서는 두 부분배열이 각각 정렬되어 있다는 조건을 믿고 병합 함수에 집중할 수 있다. 알고리즘의 정확성도 재귀적 가정과 결합 단계의 성질을 이용해 설명하기 좋다. 기저조건에서 답이 맞고, 작은 문제의 답이 맞으며, 그 답을 바르게 결합하면 전체 답도 맞는다는 흐름이다.

시간복잡도는 재귀식으로 표현되는 경우가 많다. 크기 n인 문제를 a개의 부분문제로 나누고 각 부분 크기가 대략 n/b이며, 나누기와 결합에 f(n)의 추가 작업이 든다면 T(n)=aT(n/b)+f(n) 꼴의 재귀식이 나온다. 병합 정렬은 대략 T(n)=2T(n/2)+Θ(n)이고 결과는 Θ(n log n)이다. 이진 탐색은 T(n)=T(n/2)+Θ(1)이어서 Θ(log n)이 된다. MIT의 알고리즘 강의에서도 분할 정복을 부분문제 생성, 재귀 해결, 결합이라는 틀로 설명하고 재귀식을 이용해 수행시간을 분석한다. 코드를 쓰기 전에 재귀식을 세워 보면 나누는 행위가 실제 이득을 만드는지 미리 볼 수 있다.

부분문제의 독립성은 분할 정복이 잘 작동하는 핵심 조건이다. 병합 정렬의 왼쪽 절반과 오른쪽 절반은 각각 따로 정렬해도 된다. 한쪽 정렬 과정이 다른 쪽의 중간 결과를 계속 필요로 하지 않는다. 이런 구조에서는 같은 계산을 여러 번 반복할 가능성이 낮고, 두 부분을 동시에 처리하는 병렬화도 생각하기 쉽다. 실제 병렬 알고리즘에서 분할 정복이 자주 사용되는 이유도 재귀 트리의 서로 다른 가지가 독립적으로 계산될 여지가 크기 때문이다.