[백준/BOJ] 1992번 : 쿼드트리, 1780번 : 종이의 개수, 1629번 : 곱셈 (분할 정복)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1992번 : '쿼드트리', 1780번 : '종이의 개수', 1629번 : '곱셈' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 분할 정복(Divide and Conquer) 방법에 대한 이해가 필요합니다.

 

 

1992번 : 쿼드트리

 

영상 면적을 4분할하여 모두 같은 데이터면 압축해서 표현하고, 그렇지 않으면 다시 4등분하는 과정을 반복하여 쿼드 트리 구조로 입력을 표현하는 문제입니다.

재귀함수를 활용하여 함수를 4개로 분할하여 돌리는 과정을 반복해주면 쉽게 해결할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

char arr[64][64];

void Search(int x, int y, int Size) {
    for(int i=x; i<x+Size; i++)
        for(int j=y; j<y+Size; j++)
            if(arr[i][j] != arr[x][y]) {
                cout << "(";
                Search(x, y, Size/2);
                Search(x, y + Size/2, Size/2);
                Search(x + Size/2, y, Size/2);
                Search(x + Size/2, y + Size/2, Size/2);
                cout << ")";
                return;
            }
    cout << arr[x][y];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        cin.clear();
        for(int j=0; j<N; j++) cin >> arr[i][j];
    }

    Search(0, 0, N);
}

 

Search 함수를 구현하여 만약 하나의 Size * Size 면적에 해당하는 값들이 모두 일치하지 않으면 4개의 구간으로 분할하여 탐색을 해주는 과정을 반복하도록 재귀적으로 구현하였습니다.

단위 크기에 따라 괄호로 닫아서 출력해주어야 하므로 함수 호출 전과 후에 "("와 ")"를 출력해주도록 합니다.

 

 

 

 

1780번 : 종이의 개수

 

위의 문제와 비슷하지만 면적을 9개로 분할하여 탐색을 반복해주면 되는 문제입니다.

또한 종이의 종류에 따른 개수를 Count 해주어야하므로 함수의 변형이 필요합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int arr[2200][2200];
int cnt[3] = {};

void Search(int x, int y, int Size) {
    for(int i=x; i<x+Size; i++)
        for(int j=y; j<y+Size; j++)
            if(arr[i][j] != arr[x][y]) {
                Search(x, y, Size/3);
                Search(x, y + Size/3, Size/3);
                Search(x, y + Size*2/3, Size/3);
                Search(x + Size/3, y, Size/3);
                Search(x + Size/3, y + Size/3, Size/3);
                Search(x + Size/3, y + Size*2/3, Size/3);
                Search(x + Size*2/3, y, Size/3);
                Search(x + Size*2/3, y + Size/3, Size/3);
                Search(x + Size*2/3, y + Size*2/3, Size/3);
                return;
            }

    if(arr[x][y] == -1) cnt[0]++;
    else if(arr[x][y] == 0) cnt[1]++;
    else if(arr[x][y] == 1) cnt[2]++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) cin >> arr[i][j];

    Search(0, 0, N);
    cout << cnt[0] << "\n" << cnt[1] << "\n" << cnt[2];
}

 

N <= 3^7이고 이는 2200보다는 작으므로 arr 크기를 적당히 2200 x 2200으로 잡아주면 메모리 낭비를 최소화할 수 있습니다.

return이 더 이상 되지 않았다면 해당 블럭은 모두 같은 숫자라는 의미이므로 하나의 조각으로 볼 수 있기 때문에 cnt에 반영해주면 됩니다.

 

 

 

 

1629번 : 곱셈

 

빠른 거듭 제곱 문제입니다.

예를 들어 같은 수를 1억번 제곱한다고 하여 반복해서 곱하면 1억번의 연산이 필요하므로 많은 시간이 소요되게 됩니다.

그러나 a^8 = ((a^2)^2)^2와 같이 줄여서 연산할 수 있으므로, 이를 활용하여 log N 시간에 거듭제곱을 할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

long long fastPow(int A, int B, int C) {
    if(B == 0) return 1;
    if(B == 1) return A % C;

    if(B % 2 == 0) {
        long long ret = fastPow(A, B/2, C);
        return (ret*ret) % C;
    }
    else {
        long long ret = fastPow(A, B-1, C);
        return (ret*A) % C;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int A, B, C; cin >> A >> B >> C;
    cout << fastPow(A, B, C);
}

 

위의 fastPow 함수가 빠른 거듭제곱을 수행해주는 함수입니다.

예를 들어 A^9를 연산한다고 하면, 9는 이진수로 1001이므로 A * ((A^2)^2)^2와 같이 빠르게 연산해줄 수 있습니다.