[Algorithm] 분할 정복

분할 정복

분할 정복(Divide ans Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 이 전략을 활용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀 함수를 이용하여 계산한다. 그 후 부분 문제의 답을 이용하여 전체 문제의 답을 계산해낸다.

분할정복 전략이 일반적인 재귀함수와 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다는 것이다.

 

일반 재귀호출

 

분할정복

 

그렇다면 분할정복이 필요한 이유는 무엇일까?

분할 정복을 활용하면, 선형적인 방법보다 빠르게 문제를 해결할수도 있기 때문이다.

다음 예제를 보자.

어떤 수 N과 P가 주어졌을 때, N의 P승을 구하는 알고리즘을 작성하라.

 

일반적인 경우 이 문제를 접하면 다음과 같이 알고리즘을 작성하게 될 것이다.

int Pow(int n, int p)
{
    int ret = 1;
    for (int i = 0; i < p; ++i)
    {
        ret *= n;
    }
    return ret;
}

 

하지만 이 알고리즘은 O(P) 시간에 동작한다.

이보다 더 빠르게 할 방법은 없을까??

분할정복을 이용하면 O(logP) 시간에 가능하다.

int Pow(int n, int p)
{
    if (p == 0)
        return 1;

    if (p == 1)
        return n;

    if (p % 2 == 0)
    {
        int val = Pow(n, p / 2);
        return val * val;
    }
    else
    {
        int val = Pow(n, p / 2);
        return val * val * n;
    }
}

 

분할 정복 설계 방법

일반적으로 분할 정복 문제를 설계하기 위해서 다음과 같은 구성 요소들을 고려해야 한다.

1. 해결해야하는 문제를 더 작은 부분문제로 분할

2. 부분문제들을 통해 얻은 답들을 이용하여 현재 문제에 대한 답으로 병합

3. 더 이상 분할할 수 없는 작은 문제 정의

 

위와 같은 방법들을 통해 문제를 해결하도록 설계할 수 있다.

그런데 사실 1번과 2번을 통해 문제를 부분문제로 재정의 하는 부분은 생각보다 어려울 수 있다.

이 부분을 잘 하기 위해서는 문제를 정확하게 정의하는것과, 부분분제가 이미 해결되었다고 가정을 하는 것이다.

 

구체적인 방법을 알아보기 위해 병합정렬을 예로 들어보자.

병합정렬의 목표는 어떤 수열을 인풋으로 받았을 경우, 정렬된 수열을 반환하는 것이다.

즉, MergeSort(array)는 array를 정렬시킨다.

여기서 적절하게 문제를 분할할 수 있도록 하기 위해 구간에 대한 정보를 추가해주면 다음과 같이 정의할 수 있다.

MergeSort(array, from, to)는 from부터 to 구간의 수열을 정렬시킨다.

여기서 MergeSort(array, from, to)를 부분문제로 나누고, 각 부분문제가 해결되었다고 가정해보자.

MergeSort(array, from, to):
	int mid = from + (to - from) / 2;
    
	// [from, mid]는 정렬되었다.
	MergeSort(array, from, mid);
    
	// [mid + 1, to]는 정렬되었다.
	MergeSort(array, mid + 1, to);

이렇게 왼쪽 절반 부분수열과, 오른쪽 절반 부분수열이 이미 정렬되었다고 가정한다면,

전체 수열을 정렬하는것은 훨씬 수월해진다.

이제 부분문제들의 도움을 받아 전체 문제를 해결해보자.

정렬된 두 수열을 합쳐서 정렬하는것은 O(N) 시간에 가능하다.

왼쪽 수열과 오른쪽 수열의 원소를 두 개의 인덱스로 하나씩 참조하면서 더 작은 값을 참조해나가면 된다.

// left
1 4 5 9 10

// right
2 3 6 7

1 < 2 => 1 선택, left 증가
2 < 4 => 2 선택, right 증가
3 < 4 => 3 선택, right 증가
4 < 6 => 4 선택, left 증가
5 < 6 => 5 선택, left 증가
6 < 9 => 6 선택, right 증가
7 < 9 => 7 선택, right 증가
right가 끝났으므로 9 선택, left 증가
right가 끝났으므로 10 선택, left 증가

// sorted
1 2 3 4 5 6 7 9 10

정렬 작업은 단순하게 해결하려면 O(N ^ 2)이나 걸리는 어려운 작업이지만,

분할된 부분문제들이 각자의 역할을 잘 수행하여, 두 부분수열들이 정렬되었다고 가정하면 O(N) 시간으로 가능하다.

또한 위 알고리즘이 작성되고 나면, 가정으로 시작한 것이 재귀적 특성으로 통해 부분문제에 대해서도 실제가 된다.

그럼 이제 마지막으로 더 이상 분할할 수 없는 작은 문제에 대한 처리를 해주어야 한다.

MergeSort의 경우 from과 to를 계속 절반으로 분리하다보면, 결국 from과 to가 같아지는 순간이 오게된다.

from과 to가 같은 경우는 수열의 원소가 한 개인 경우이므로, 특별한 작업을 해주지 않는다 하더라도 하나의 원소에 대해서는 이미 정렬되었다고 간주할 수 있기 때문에 문제 없다. 물론 기저조건이기도 하기 때문에 return을 빠뜨려서는 안될 것이다.

결론적으로 일반적인 분할정복 문제들은 다음과 같은 형태를 띄게 된다.

Problem(전체 문제 범위)
	if 기저 조건:
		return 매우 작은 문제 해답
	
	부분 해답 = Problem(부분 문제 범위)
	부분 해답 = Problem(부분 문제 범위)
	...
	부분 해답 = Problem(부분 문제 범위)
    
	부분 해답들을 이용한 전체 해답 생성

 

분할 정복 문제

수학

A(N의 P승)

https://www.acmicpc.net/problem/13171

13171번: A

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/A.cpp

insooneelife/AlgorithmTutorial

 

 

행렬 제곱

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/%ED%96%89%EB%A0%AC%20%EC%A0%9C%EA%B3%B1.cpp

insooneelife/AlgorithmTutorial

 

 

카라츠바 알고리즘(빠른 곱셈)

 

 

슈트라센 알고리즘(빠른 행렬곱셈)

 

 

일반

하노이의 탑

https://programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91.cpp

insooneelife/AlgorithmTutorial

 

부분배열 고르기

https://www.acmicpc.net/problem/2104

2104번: 부분배열 고르기

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/%EB%B6%80%EB%B6%84%EB%B0%B0%EC%97%B4%20%EA%B3%A0%EB%A5%B4%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial

 

히스토그램 (최대 직사각형)

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/%ED%9E%88%EC%8A%A4%ED%86%A0%EA%B7%B8%EB%9E%A8%EC%97%90%EC%84%9C%20%EA%B0%80%EC%9E%A5%20%ED%81%B0%20%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95.cpp

 

 

최근접점쌍

https://www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/%EA%B0%80%EC%9E%A5%20%EA%B0%80%EA%B9%8C%EC%9A%B4%20%EB%91%90%20%EC%A0%90.cpp

insooneelife/AlgorithmTutorial

 

 

다차원공간

쿼드압축 후 개수 세기

https://programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%EC%BF%BC%EB%93%9C%EC%95%95%EC%B6%95%20%ED%9B%84%20%EA%B0%9C%EC%88%98%20%EC%84%B8%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial

 

 

샤워실 바닥 깔기(트로미노 타일링)

https://www.acmicpc.net/problem/14601

14601번: 샤워실 바닥 깔기 (Large)

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/%EC%83%A4%EC%9B%8C%EC%8B%A4%20%EB%B0%94%EB%8B%A5%20%EA%B9%94%EA%B8%B0%20(Large).cpp 

insooneelife/AlgorithmTutorial

 

 

종이의 개수

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Baekjoon/%EC%A2%85%EC%9D%B4%EC%9D%98%20%EA%B0%9C%EC%88%98.cpp

insooneelife/AlgorithmTutorial

 

이분 탐색

분할정복을 활용한 또 다른 알고리즘 문제 유형으로는 이분 탐색이 있다.

일반적인 이분 탐색은 정렬된 배열에서 원하는 원소를 찾는데 사용되는 알고리즘을 의미한다.

하지만 알고리즘 문제에서 이분탐색으로 자주 등장하는 유형들은 그렇게 간단한 형태는 아니다.

다음 문제를 보자.

 

징검다리 건너기

https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

이 문제를 보면 어떤 t명이 징검다리를 건너면 징검다리의 높이가 t만큼 낮아지게 되는것을 알 수 있다.

하지만 이 문제에서의 징검다리의 개수는 무려 20만개나 되고, t의 가능한 값의 범위도 엄청 크다.

이러한 문제를 풀기 위해서 탐색 대상을 값 그 자체에 잡는 전략을 활용할 수 있다.

즉 징검다리를 건너는 t명을 탐색 대상으로 잡는 것이다.

그렇게 하려면 먼저 t값의 가능한 범위부터 산출해야한다.

t의 최소값이 0명인 것은 쉽게 알 수 있다.

t의 최대값은 모든 징검다리가 물에 잠기게 되는 200000000으로 잡으면 될 것이다. 그 위로는 의미가 없다.

그 후 t의 최소, 최대 값의 중간값을 기준으로 잡고, 그 값에 대해 모든 징검다리를 건널 수 있는지 검사한다.

만약 건너는것이 가능하다면 t의 값을 더 축소시키고,

건너는것이 불가능하다면 t의 값을 다시 조금 더 늘려본다.

다음과 같은 형태의 코드가 작성될 것이다.

int Search(from, to):
	if from >= to:
    	return start
        
    mid = (from + to) / 2
    success = (mid 값을 기준으로 시도 해보기)
    
    if success:
    	return Search(mid + 1, end)
    else:
    	return Search(start, mid)
    
    

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial

 

입국 심사

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DivideConquer/Solutions/Programmers/%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.cpp

insooneelife/AlgorithmTutorial