[Algorithm Tech] Divide and Conquer(분할 정복)

* 분할 정복(Divide and Conquer)

분할 정복이란 문제를 소문제로 변경하여 소문제를 해결하여 큰 문제를 해결하는 방식이다.

1. 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다.

2. 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.

3. 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을 구한다.

* 분할 정복의 특징

장점 : 큰 문제를 비교적 작은 문제로 변환하고, 재귀로 구현하기 때문에 코드가 비교적 간단한다.

단점 : 재귀를 사용하기 때문에 StackOverflow가 발생할 수 있다.

* 예시

public static long DivideConquer(int a, int b, int c) {
    if (b == 0) return 1;       //종료 조건
    if (b % 2 == 1) {           //지수가 홀수인 경우
        return DivideConquer(a, b - 1, c) * a % c;
    } else {                    //지수가 홀수인 경우
        long v = DivideConquer(a, b / 2, c) % c;
        return v * v % c;
    }
}

백준 1629 :: 곱셈 풀이