분할 정복 알고리즘 Divide & Conquer

분할정복 (또는 분할 통치)

• 피지배민을 분열시켜 통치에 용이하게 하는 방법
• 군을 분열시켜 각개격파하는 방법

분할 정복 알고리즘 - 큰 문제를 나누어서 풀고, 그 결과를 조합해서 문제를 해결하는 알고리즘 기법

알고리즘 기법

• 분할(Divide) : 해결할 문제를 여러개의 작은 문제로 나눈다.
• 정복(Conquer) : 작은 단위의 문제를 해결한다.
• 조합(Merge or Combine) : 해결한 작은 단위 문제들을 합해 원래 문제의 답을 구한다.

일반적으로 각 하위 문제들이 독립적으로 풀이가 가능한 형태로서, 하위 문제의 결과가 상위 문제의 풀이 방식에 영향을 주지 않을 때 분할 정복 알고리즘이라 이야기합니다.

그 특성상 분할 정복 알고리즘은 재귀함수를 이용해 풀이하는 경우가 많습니다.

 

하노이의 탑 알고리즘 이동순서

세개의 기둥과, 기둥에 꽂을 수 있는 다양한 크기의 원반이 있고, 그 원반들이 밑에서부터 큰것부터 차례대로 쌓여있을때, 다른 기둥에 전체 원반들을 옮기는 문제입니다. 이때,

• 한번에 하나의 원반만 옮길 수 있습니다.
• 가장 위에 쌓인 원반만 옮길 수 있습니다.
• 큰 원반이 작은 원반 위에 올라가 있으면 안됩니다.

이때 N개의 원반이 기둥(1)에 있다고 가정하면, N개를 한쪽 기둥(3)으로 완전히 옮기는 문제는, N - 1 개를 일단 다른 기둥(2)에 옮긴 다음, N번째 제일 큰 원반을 목표 기둥(3)으로 옮긴 뒤 다른 기둥(2)에 있던 N - 1 개의 원반을 목표 기둥(3)으로 옮기면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private StringBuilder towerBuilder;
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    public void solution() throws IOException {
        int n = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
        towerBuilder = new StringBuilder();
        // 점화식을 이용해 풀이
        towerBuilder.append((int) (Math.pow(2, n) - 1)).append('\\n');
        hanoi(n, 1, 3, 2);
        System.out.println(towerBuilder);
    }

    public void hanoi(int height, int start, int end, int other) {
        if (height == 1) {
            towerBuilder.append(start + " " + end + "\\n");
        }
        else {
            hanoi(height - 1, start, other, end);
            towerBuilder.append(start + " " + end + "\\n");
            hanoi(height -1, other, end, start);
        }
    }
}

 

관련문제

11729번: 하노이 탑 이동 순서

 

1914번: 하노이 탑