알고리즘 문제 풀이5

알고리즘 문제 풀이 5

최근에 푼 재미있는 문제들을 포스팅 해보겠습니다.

BOJ 1185 숫자 놀이

이 문제는 $2N - 1$ 개의 숫자가 주어질 때, 그 중에서 $N$ 개의 숫자를 골라서 합이 N의 배수가 되도록 만드는 문제입니다.(단, $N = 2^n$ 꼴의 수 입니다)

우선 “합이 $N$ 의 배수가 되는 $N$ 개의 숫자를 골라내는 것이 언제나 가능할 것인가?” 라는 의문이 생깁니다.

수학적 귀납법을 사용하면 이러한 의문과 이 문제에 대한 답을 동시에 제시해주는 풀이를 얻을 수 있습니다. 지금부터 알아보도록 합시다.

우리는 $N = 2^n$ 꼴이라는 조건에서 $n$ 이라는 값에 대해 수학적 귀납법을 진행할 것입니다.

명제: $2N - 1$ 개의 숫자가 주어지면, 그 중 적절히 $N$ 개를 뽑아서 합이 $N$ 의 배수가 되게 할 수 있다.

$n = 1$ 일때, 3개의 숫자가 주어지고 그 중 2개를 뽑아서 2의 배수가 되도록 만들어야 합니다. 비둘기집의 원리에 의해 홀짝성이 같은 두 수가 존재하고, 이 둘을 뽑으면 가능하므로 명제가 성립합니다.
$n = k$ 일때, 명제가 성립 한다고 가정합시다.
$n = k + 1$ 일때, $2^{k+2} - 1$ 개의 숫자들이 있을 것입니다.

귀납 가정에 의해 이 중에 아무렇게나 $2^{k + 1} - 1$ 개를 뽑으면 그 중에 $2^k$ 개를 뽑아서 $2^k$ 의 배수를 만들 수 있습니다.

지금 뽑은 $2^k$ 개의 숫자들을 목록에서 제외하면, $2^{k+1} + 2^k - 1$ 개의 숫자가 남게 됩니다. 이 중에서 다시 아무렇게나 $2^{k+1} - 1$ 개를 뽑으면 마찬가지로 이 중에서 $2^k$ 의 배수가 되는 $2^k$ 개를 뽑을 수 있습니다.

지금 뽑은 $2^k$ 개의 숫자들을 마찬가지로 목록에서 제외하면, $2^{k+1} - 1$ 개의 숫자가 남게 됩니다. 다시 한번 위와 같은 행위를 반복합니다.

그러면 우리는 최종적으로 $2^k$ 의 배수를 만들수 있는 $2^k$개의 disjoint한 숫자 구성을 3세트 얻게 됩니다.

한편, n=1 일때와 같은 원리로 $2^k$ 의 배수 3개가 있으면 그 중 2개를 골라서 합이 $2^{k+1}$ 의 배수가 되도록 만들 수 있으므로 $2^{k+1}$ 의 배수가 되는 $2^{k+1}$ 개의 숫자들을 얻을 수 있습니다.

위의 증명에서 사용한 답을 구성하는 방식을 적용한 코드입니다.

편하게 코딩하기 위해서 solve(l, r) 을 A배열의 [l, r]에 있는 원소들에 대한 문제를 해결하는 함수로 정의하였고 반환 값은 문제의 답이되는 구성들의 합이며, 동시에 A 배열의 [l, r] 의 앞에 해당 문제의 답이 되는 구성들을 위치시켰습니다.

시간 복잡도 분석을 해보도록 하겠습니다. 가장 비중이 큰 solve(l, r) 의 시간 복잡도를 분석하면 되겠습니다.

$T(n) = 3 * T(n / 2) + O(n)$

이므로 master theorem 에 의해 $O(n^{log_23})$ 의 시간 복잡도로 평가할 수 있습니다.

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

const int maxn = 1 << 10;

int N;
int A[maxn << 1];

int solve(int l, int r) {
    int n = (r - l + 2) / 2;
    if(n == 1) return A[l];

    vector<int> V;
    for(int i = 0; i < 3; i++) {
        int t = solve(l + i * n / 2, l + i * n / 2 + n - 2);
        V.push_back(t / (n / 2));
    }
    if(V[0] % 2 == V[1] % 2) return (V[0] + V[1]) * n / 2;
    if(V[0] % 2 == V[2] % 2) {
        for(int i = 0; i < n / 2; i++) swap(A[l + n / 2 + i], A[l + n + i]);
        return (V[0] + V[2]) * n / 2;
    }
    else {
        for(int i = 0; i < n / 2; i++) swap(A[l + i], A[l + n + i]);
        return (V[1] + V[2]) * n / 2;
    }
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < 2 * N - 1; i++) {
        scanf("%d", &A[i]);
    }
    solve(0, 2 * N - 2);

    for(int i = 0; i < N; i++) {
        printf("%d ", A[i]);
    }
}

BOJ 3645 토너먼트 조작

이 문제는 N개의 팀이 토너먼트 경기를 할 때, 1번 팀이 우승할 수 있도록 경기 순서를 정하는 문제 입니다. (단, $N = 2^n$ 꼴의 수 입니다.)

모든 쌍의 팀에 대해서 두 팀이 경기를 한다면 누가 이길지는 고정되서 우리에게 주어집니다. 우리는 이를 바탕으로 순서를 정해야 합니다.

또한, 1번팀이 적어도 절반 이상의 팀을 이길수 있다는 것이 보장되며, 1번팀을 이기는 팀이 있다면 그 팀을 이기고 1번팀한테는 지는 팀이 존재한다는 것도 보장됩니다.

편의상, 1번팀을 이기는 팀을 나쁜팀, 1번 팀에게 지는 팀을 착한 팀이라고 명명합시다.

우선, 당연한 사실은 1번 팀은 무조건 착한 팀이랑만 경기를 하면서 올라가야 합니다. 따라서 나쁜 팀들을 1번팀과 붙기 전에 치워버려야 합니다. 나쁜 팀들을 어떻게 1번팀과 붙기 전에 치워버릴수 있을까요?

다행히도 우리에게는 나쁜 팀들을 이기는 착한 팀의 존재가 보장되어 있습니다.

모든 나쁜 팀들에 대해서 자신을 이기는 착한 팀이 있습니다. 이러한 착한 팀을 해당 나쁜 팀의 처리반이라고 합시다. 처리반이 여러개라면 적절히 하나만 골라서 처리반을 유일하게 만듭시다.

그러면 모든 착한 팀들은 자신이 처리해야할 나쁜팀들의 목록을 갖게 됩니다. 처리할 목록이 없는 무능력한 착한 팀들은 아무 곳에나 들어가도 상관 없으니 따로 모아뒀다가 나중에 토너먼트의 빈칸을 채우는 데에 사용합시다.

이제 1번이 우승할 수 있도록 토너먼트를 구성하여 봅시다.

모든 (처리반, 처리 목록) 쌍에 대하여 이들만으로 토너먼트를 만듭시다. 맨 왼쪽의 리프노드에 착한 팀을 놓고 그 뒤로 쭉 그 팀의 처리 목록들을 배치하는 식으로 말입니다. 물론 토너먼트는 이진트리 형태로 유지시키고 싶기 때문에 모자라는 인원은 아까 따로 모아두었던, 무능력한 착한 팀들을 대충 채워 넣읍시다.

잘 생각해보면 이 토너먼트의 꼭대기에는 절대 나쁜 팀이 올 수가 없습니다. 왜냐하면, 꼭대기의 왼쪽 자식에는 무조건 현재 담당인 착한 팀이 올 것이기 때문에 맨 꼭대기에 나쁜팀이 있다는 것은 자신의 담당을 이기고 올라갔다는 말이 되어 모순이기 때문입니다.

그렇다면 이제 우리는 모든 (처리반, 처리 목록) 쌍마다 만든 이 토너먼트를 우리가 구성하고자 하는 토너먼트에 순서대로 붙여 넣으면 됩니다. 그리고 마지막에 아직도 남은 무능력한 착한 팀과 1번 팀을 추가하면 우리가 원하는 구성을 얻을 수 있습니다.

다만, 의문을 가져야 하는 것이 이진트리를 만들기 위해 채워 넣었던 무능력한 착한팀이 모자라지 않을 까하는 사실인데, 이는 모든 (처리반, 처리 목록) 쌍에 대해서 만들어야하는 최소의 이진트리의 리프노드 크기의 합이 $N - 1$보다 작다는 것을 보이면 됩니다.

각 (처리반, 처리 목록) 쌍에 대해서 필요한 이진트리의 상한은 (처리목록의 크기) * 2 가 될 것입니다. 당연히, 처리 목록에는 나쁜 팀밖에 없고 따라서 모든 쌍에 대한 이진트리의 리프노드의 총합의 상한은 (나쁜팀의 개수) * 2 입니다. 한편, 처음의 조건에 따라 나쁜팀의 총 인원이 $N / 2 - 1$ 명이하임이 보장되므로 (나쁜팀의 개수) * 2 는 $N - 2$ 보다 작거나 같습니다. 이는 $N-1$ 보다 작고, 따라서 우리의 구성 방법은 항상 유효하다는 것을 증명하였습니다.

아래는 위와 같은 방식으로 문제를 해결하는 코드입니다. 위와 같은 방식으로 구성하는 데에는 $O(N)$ 의 시간이 소요됩니다. 문제에서는 토너먼트의 모든 경기를 출력하라고 하였으므로 출력하는 데에는 총 경기 수인 $O(NlogN)$ 의 시간이 소요될 것입니다.

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

const int maxn = 1 << 11;

int N;
char S[maxn][maxn];
vector<int> V[maxn], R, T;

bool main2() {
    if(scanf("%d", &N) == EOF) return false;

    for(int i = 0; i < N; i++) {
        scanf("\n");
        for(int j = 0; j < N; j++) {
            scanf("%c", &S[i][j]);
        }
    }
    for(int i = 0; i < N; i++) V[i].clear();
    for(int i = 1; i < N; i++) if(S[0][i] == '0') {
        for(int j = 1; j < N; j++) if(i != j && S[i][j] == '0' && S[0][j] == '1') {
            V[j].push_back(i);
            break;
        }
    }
    R.clear();
    for(int i = 1; i < N; i++) if(S[0][i] == '1' && V[i].size() == 0) R.push_back(i);

    T.clear();
    for(int i = 0; i < N; i++) if(V[i].size()) {
        int n = 1;
        while(n < V[i].size() + 1) n <<= 1;

        T.push_back(i);
        for(int j = 0; j < V[i].size(); j++) T.push_back(V[i][j]);
        for(int j = V[i].size() + 1; j < n; j++) {
            T.push_back(R.back());
            R.pop_back();
        }
    }
    while(R.size()) {
        T.push_back(R.back());
        R.pop_back();
    }
    T.push_back(0);

    while(T.size() > 1) {
        vector<int> tmp;
        for(int i = 0; i < T.size() / 2; i++) {
            printf("%d %d\n", T[2 * i] + 1, T[2 * i + 1] + 1);

            if(S[ T[2 * i] ][ T[2 * i + 1] ] == '1') tmp.push_back(T[2 * i]);
            else tmp.push_back(T[2 * i + 1]);
        }
        T = tmp;
    }
    return true;
}

int main() {
    while(main2());
}

알고리즘 문제 풀이5