[중급 알고리즘] 분할 정복(연습)

💚 1780 종이의 개수

solve(x, y, n)

(x, y)부터 가로로 n개, 세로로 n개의 종이 개수를 확인하는 함수

m = n / 3이라고 했을 때 부분 문제로 나눠보면 

0: solve(x, y, m)

1: solve(x, y + m, m)

2: solve(x, y + 2 * m, m)

3: sovle(x + m, y, m)

...

cnt[x] = x - 1의 개수

x는 -1, 0, 1이 가능하기 때문

#include <iostream>

using namespace std;
int a[3000][3000];
int cnt[3] = {0, };
// n * n 종이 내의 색이 모두 동일한지 확인
bool same(int x, int y, int n) {
    for(int i = x;i < x + n;i++) {
        for(int j = y;j < y + n;j++) {
            if(a[x][y] != a[i][j]) {
                return false;
            }
        }
    }
    return true;
}
// (x, y)부터 가로로 n개, 세로로 n개의 종이 개수를 확인하는 함수
void solve(int x,int y, int n) {
    if(same(x, y, n)) {
        cnt[a[x][y] + 1] += 1;
        return;
    }
    int m = n / 3;
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < 3;j++) {
            solve(x + i * m, y + j * m, m);
        }
    }
}
int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
        }
    }

    solve(0, 0, n);

    for(int i = 0;i < 3;i++) {
        cout << cnt[i] << '\n';
    }
    return 0;
}

💚 2263 트리의 순회

- N개의 정점을 갖는 이진 트리의 정점에 1부터 N까지 번호가 중복없이 매겨져 있다.

- 이 이진 트리의 인오더와 포스트 오더가 주어졌을 때 프리오더를 구하는 문제

 

포스트 오더의 마지막 수를 통해 루트를 알 수 있다.

인오더 정보를 통해 가장 왼쪽 수를 알 수 있다.

 

#include <iostream>

using namespace std;
int inorder[100000];
int postorder[100000];
// position[i]: i번 정점이 인오더에서 몇 번째에 있는지 저장, 이건 정점의 숫자로 인덱싱하기 때문에 100001의 크기가 필요
int position[100001];

void solve(int in_start, int in_end, int post_start, int post_end) {
    if(in_start > in_end || post_start > post_end) return;

    int root = postorder[post_end];
    cout << root << ' ';

    // p = 루트의 인오더 배열에서의 위치
    int p = position[root];

    // inorder: in_start p in_end
    // postorder: post_start post_end
    // left: p - in_start = 왼쪽 자식의 수
    // right: in_end - p = 오른쪽 자식의 수
    int left = p - in_start;
    solve(in_start, p - 1, post_start, post_start + left - 1);
    solve(p + 1, in_end, post_start + left, post_end - 1);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> inorder[i];
    }

    for(int i = 0;i < n;i++) {
        cin >> postorder[i];
    }


    for(int i = 0;i < n;i++) {
        position[inorder[i]] = i;
    }

    solve(0, n - 1, 0, n -1);
    return 0;
}

 

💚 1571 버블 소트

N개로 이루어진 수열 A가 있을 때 

Swap이 총 몇 번 발생하는지 

실제로 Swap을 하지 않아도 카운트 가능하다. 머지 소트를 이용한다.

왼쪽에 있으면서(i < j) 더 큰 값(A[i] > A[j]) 찾기

 

오른쪽 절반이 이동할 때 왼쪽 절반에서 아직 이동하지 않은 것의 개수가 inversion의 개수다.

#include <iostream>

using namespace std;
int a[500000];
int b[500000];
long long solve(int start, int end) {
    if(start == end) {
        return 0;
    }

    int mid = (start + end) / 2;
    // 재귀 호출
    long long ans = solve(start, mid) + solve(mid + 1, end);
    int i = start;
    int j = mid + 1;
    int k = 0;
    // 왼쪽, 오른쪽 모두 탐색 끝나야 while문 종료
    while(i <= mid || j <= end) {
        if(i <= mid && (j > end || a[i] <= a[j])) {
            b[k++] = a[i++];
        }
        else {
            ans += (long long)(mid - i + 1);
            b[k++] = a[j++];
        }
    }

    for(int i = start;i <= end;i++) {
        a[i] = b[i - start];
    }

    return ans;
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n;i++) {
        cin >> a[i];
    }

    long long ans = solve(0, n - 1);
    cout << ans << '\n';
    return 0;
}