분할정복 divide & conquer (알고리즘) +(백준 1780)

알고리즘 문제에서 분할정복 문제를 만나면 어떻게 접근해야 하는지 정리하는 글이다.

 

이 문제를 찾는 인사이트는 문제를 보고 이 문제를 작은 문제로 쪼갤 수 있을까?를 보는 것이다.

그리고 고민거리가 몇가지 있다.

 

1. 어떻게 나눌 것인가?

2. 어디까지 나눌 것인가? degenerate case의 크기?

3. 대칭적으로 나눌 것인가? 합병 VS 쾌속 정렬

4. combine 단계가 필요한가? ( 대부분 쪼개긴 해야 하는데 합병 단계는 크게 필요 없는 경우가 많다.)

 

수시적으로 살펴보자 아래의 사진은 분할 정복을 표현하는 식이다.

 

이를 점화식으로 표현하면 아래와 같다.

점화식의 해법은 아래와 같다.

 

1. 특성 방정식

2. 텔레스코핑

3. 마스터 정리

 

1번 2번은 머리 아프니 3번만 알아도 크게 상관 없다고 생각한다.

https://park-hama.tistory.com/38

알고리즘 시간 복잡도, 마스터 정리

마스터 정리가 궁굼하면 위 링크를 보자.

아참 마스터 정리는 사용하려면

1. 같은 형식으로 반복

2. degenerate case가 존재하는가

3. 문제의 크기가 주어지는가

이렇게 3개가 필요하다.

 

먼저 분할 정복 알고리즘은 크게 세가지 파트로 구성이 된다.

 

 

int *arr이라는 배열에 접근 할거다.

s부터 e까지 접근 할거다.

 

1. degeneratate case

더 이상 분할하지 않아도 풀 수 있는 크기의 문제.

2. divide

문제를 작은 소문제로 나눈다.

3. combine or conquer

소문제의 해로 부터 상위 문제의 해를 찾는다.

 

이런 일련의 과정이 들어가게 된다.

 

즉, 분할정복 문제를 풀려면

1. 어떻게 해야 더이상 분할하지 않아도 문제를 풀 수 있을까? 

2. 어떻게 문제를 분할해야 할까?

3. 어떻게 문제를 다시 합칠까?

 

이런 과정을 머리에 담고 문제를 풀어야 한다.

 

 

1780번: 종이의 개수 (acmicpc.net)

 

이 문제를 한 번 봐보자

 

 

degerate case는 뭘까?

0, 1 -1만 있으면 degenerate case이다. 아래의 그림을 참고해서 보면

n == 1 or (xs ~ xe, ys ~ye)가 모두 같은 값이면 해당이 된다.

 

 

 

 

분할의 과정은 그림과 같다.

 

합치는 과정은 크게 필요가 없다.

 

위의 과정을 생각하면서 풀어보자. 

 

 

#include <iostream>
using namespace std;

int arr[2200][2200]; // 최대 3^7까지 배열 선언
int paper[3] = { 0, }; // -1, 0, 1 순으로 개수를 저장

void dp(int stx, int sty, int jump) {
    int first = arr[stx][sty]; // 첫 번째 값을 기준으로 한다.
    bool same = true;

    // 범위 내에서 모든 값이 같은지 확인
    for (int i = stx; i < stx + jump; i++) {
        for (int k = sty; k < sty + jump; k++) {
            if (arr[i][k] != first) { // 다르다면 분할 진행
                same = false;
                break;
            }
        }
        if (!same) break;
    }

    if (same) {
        // 모든 값이 동일할 경우 해당 값의 종이 개수를 증가
        if (first == -1) paper[0]++;
        else if (first == 0) paper[1]++;
        else paper[2]++;
    }
    else {
        // 값이 다르면 9등분하여 재귀적으로 처리
        int nextJump = jump / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                dp(stx + i * nextJump, sty + j * nextJump, nextJump);
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    // 배열 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    // 분할 정복 시작
    dp(0, 0, n);

    // 결과 출력 (-1, 0, 1 순)
    cout << paper[0] << '\n' << paper[1] << '\n' << paper[2] << '\n';

    return 0;
}

 

공부하는게 어렵고. 힘들다. 난 솔직히 코딩하는게 막 그렇게 재밌고, 새로운 기술을 보면 흥분해 미칠 거 같은 그런 사람은 아니다. 그래도 계속 할 수 있어서 하는 것 같다. 뭐 인생은 마라톤이라는 말이 있다. 하기 싫고, 힘들고, 남들보다 조금 쳐지는 감이 있어도 포기만 하지 않는다면 나도 잘할 수 있겠지란 생각이 든다. 뭐 아무튼 모두들 힘내길 바란다.