분할 정복이란? #

• 분할 정복(Divide and Conquer)은 하나의 엄청나게 큰 문제를 나누고 다시 합치면서 해결하는 알고리즘의 기본이 되는 문제 해결 방법이다. 대표적인 정렬인 퀵 정렬에서도 분할 정복 알고리즘을 사용한다.

장점 #

• 분할 정복의 장점은 어려운 문제를 간단하게 해결할 수 있다는 점이다. 문제 해결을 위해 작은 단위로 쪼개서 함수를 만들면 그것을 재귀적으로 호출하는 것을 통해 문제 해결이 가능하다.

단점 #

• 분할 정복의 단점으로는 재귀적으로 무수히 많은 함수호출이 이루어지면 스택 포인터가 스택의 경계를 넘어가게 되어 스택 오버플로가 발생할 수 있고 문제를 쪼개는 방법 자체가 상당히 어려울 수 있으며 상당히 많은 함수호출에 따라 많은 오버헤드가 발생할 수 있다는 점이다.

하노이 탑 #

분할정복을 적용한 대표적인 사례는 하노이 탑이다. 하노이 탑은 3개의 기둥과 서로 다른 크기의 여러 개의 원반으로 구성되어 있고 작은 원반 위에 큰 원반을 놓을 수 없고 하나에 한 개의 원반만 이동할 수 있다. 이런 조건으로 첫 번째 기둥에 꽂혀있는 N개의 원반을 3번째 기둥에 옮기는 문제이다.

먼저 이 문제를 해결하기 위해서는 작은 문제로 쪼개야 한다. 하나의 원반을 3번째 기둥으로 옮기기 위해서는 나머지 n-1개의 원반을 3번째 기둥을 이용해서 2번째 기둥으로 옮기고 맨 아래의 원반을 3번째 기둥으로 옮긴 다음 n-1개의 원반을 첫 번째 기둥을 이용해서 3번째 기둥으로 옮기면 된다.

위와 같이 하노이 탑 문제를 작은 3개로 쪼개면 다음과 같다.

1. N-1개의 원반을 3번째 기둥을 통해서 2번째 기둥으로 옮긴다.
2. 1개의 원반을 3번째 기둥으로 옮긴다.
3. N-1개의 원반을 1번째 기둥을 통해서 3번째 기둥으로 옮긴다.

하노이 탑 - 파이썬 #

이를 파이썬 코드로 구현하면 다음과 같다.

def hanoi(n, from, by, to):
    if n == 1:
        print(f“{n}을 {from}에서 {to}로”)
        return
    hanoi(n-1, from, to ,by)
    print(f“{n}을 {from}에서 {to}로”)
    hanoi(n-1, by, from, to)

N개의 원반을 1번 기둥에서 2번 기둥을 통해 3번 기둥으로 옮긴다고 했을 때 함수는 다음과 같다.

hanoi(N, 1, 2, 3)