c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q52 같은 숫자로 협공하기 (비트마스크 및 메모화 활용)

[문제]

1 ~ n 숫자가 적힌 카드가 각각 2장씩, 총 2n 장이 있다.

1이 적힌 카드 사이에는 카드 1장이, 2가 적힌 카드 사이에는 카드 2장이, n이 적힌 카드 사이에는 카드 n장이 놓이도록 카드를 배치하고자 한다.

예를 들어, n = 4이면 2가지 방법이 가능하다.

n = 11일 때 가짓수는?

 

[알고리즘]

2n장의 카드가 있으므로 크기가 2n인 배열을 정의하여 카드를 저장한다.

1) 1번 카드, 2번 카드, 3번 카드... 순으로 카드를 배치한다.

2) 각 카드는 2장씩 있고, 첫 번째 카드의 위치가 정해지면 두 번째 카드의 위치는 자동으로 정해진다.

예를 들어 m번 카드 중 첫 번째 카드를 pos 위치에 배치하면 두 번째 카드는 자동으로 pos + m + 1에 위치하게 된다.

3) pos + m + 1은 최대 2n - 1까지만 가능하므로 pos의 범위는 0부터 2n - 2 - m까지 가능하다.

4) pos 또는 pos + m + 1 위치에 다른 카드가 이미 배치되어 있으면 skip한다.

위 내용을 반영하면 다음과 같다.

 

#include <stdio.h>
#define N 11
void solve(int* arr, int* cnt, int num);
void printArr(int* arr, int sz);
int main() {
    int arr[2 * N] = { 0 };
    int cnt = 0;
    solve(arr, &cnt, 1);
    printf("cnt = %d\n", cnt);
}
void solve(int* arr, int* cnt, int num) {
    if (num == N + 1) {
        (*cnt)++;
        //printArr(arr, 2 * N);
        return;
    }
    // num = 1이면 0부터 2N - 3까지
    // num = N이면 0부터 N -2 까지
    for (int pos = 0; pos <= 2 * N - 2 - num; pos++) {
        if (arr[pos])            // arr[pos]가 0이 아니면
            continue;
        if (arr[pos + num + 1])  // arr[pos + num + 1]가 0이 아니면
            continue;	
        arr[pos] = num;
        arr[pos + num + 1] = num;
        solve(arr, cnt, num + 1);
        arr[pos] = 0;
        arr[pos + num + 1] = 0;
    }
}
void printArr(int* arr, int sz) {
    for (int i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

정답은 다음과 같다.

 

정답을 구하는 것은 크게 어렵지 않은데 문제는 속도이다.

n = 11까지는 그럭저럭 빠른데 n = 12만 되어도 급격히 느려진다.

 

교재에서는 2가지 방법을 소개했는데,

1) 탐색을 1, 2, 3, 순으로 하지 말고, n, n-1, n-2, ... 1 과 같이 역순으로 진행할 것

아무래도 11번 카드의 위치를 먼저 정하는 것이 1번 카드를 먼저 정하는 것보다 탐색 횟수를 줄이는데 도움이 될 것 같다.

그리고 실제로 확인해보면 속도가 더 빨라진다.

 

2) 배열을 쓰지 말고 비트 마스크를 활용할 것

위 코드에서 배열에 num을 저장하지 말고, 단순히 1을 저장해도 전혀 문제가 되지 않는다.

    for (int pos = 0; pos <= 2 * N - 2 - num; pos++) {
        if (arr[pos])            	// arr[pos]가 0이 아니면
            continue;
        if (arr[pos + num + 1])  	// arr[pos + num + 1]가 0이 아니면
            continue;	
        arr[pos] = 1;			// num 대신 1을 사용해도 무방함
        arr[pos + num + 1] = 1;		// num 대신 1을 사용해도 무방함
        solve(arr, cnt, num + 1);
        arr[pos] = 0;
        arr[pos + num + 1] = 0;
    }

 

즉, arr을 배열이 아닌, 0과 1로 이루어진 2진수 정수로 표현이 가능하다.

예를 들어 11번 카드가 0과 12번 위치에 놓였고, 10번 카드가 16번 위치와 5번 위치에 놓였다면 다음과 같이 나타낼 수 있다.

arr = 2 ^ 16 + 2 ^ 12 + 2 ^ 5 + 1 = 69665 (10진수)

 

이제 놓고자 하는 카드 숫자가 num일 때 마스크를 생성한다.

예를 들어, 놓고자 하는 카드 숫자가 3이라면 다음과 같은 마스크를 생성한다.

만약 놓고자 하는 카드 숫자가 7이라면 다음과 같이 마스크를 생성한다.

 

각 마스크들에 대해서  arr & mask != 0 이라면 arr과 마스크에 겹치는 1이 존재한다는 의미이므로 num 카드를 배치할 수 없다. 그러므로 패스!

만약 arr & mask == 0이라면 카드를 배치할 수 있고 arr -> arr | mask 가 된다.

아래 예시는 11, 10, 9번 카드가 놓인 후 8번 카드를 놓는 예시이다. (편의상 0은 생략한다.)

[예시1]

arr & mask가 0이 아니다. 그러므로 스킵.

[예시2]

arr & mask == 0이므로 카드를 배치할 수 있다.. 카드를 배치한 후에는 arr ❘ mask 가 된다.

 

아래는 위 내용을 반영한 코드이다.

#include <stdio.h>
#include <stdlib.h>
#define N 11
unsigned long long* memo = NULL;
unsigned long long solve(unsigned long long arr, int num);
int main() {
    unsigned long long sz = 1ULL << (2 * N);
    memo = (unsigned long long*)malloc(sizeof(unsigned long long) * sz);
    for (unsigned long long i = 0; i < sz; i++)
        memo[i] = -1;		// 0도 의미있는 값을 가지므로 -1로 초기화한다.

    unsigned long long arr = 0;
    printf("count = %llu\n", solve(arr, N));

    free(memo);
}
unsigned long long solve(unsigned long long arr, int num) {
    if (memo[arr] != -1)	// -1이 아니라면 메모 값을 리턴한다.
        return memo[arr];
	
    if (num == 0) {
        return 1;
    }

    unsigned long long mask = (1ULL << (num + 1)) + 1;
    unsigned long long cnt = 0;
    for (int i = 0; i < 2 * N - 1 - num; i++) {
        unsigned long long temp = arr & (mask << i);
        if (temp != 0)
            continue;
        temp = arr | (mask << i);
        cnt += solve(temp, num - 1);
    }
    memo[arr] = cnt;
    return cnt;
}

 

n = 12일 때도 상당히 빠르게 정답이 나온다.

n = 12일 때

 

위 코드에서 메모를 활용한 이유는 아래와 같다.

카드를 11, 10, 9, 8, ... 를 배치할 때, 11, 10, 9, 8의 위치 등이 서로 다르더라도 arr 값은 동일할 수 있다.

무슨 말이냐면 아래와 같이 arr 값은 동일하더라도 카드의 배치는 서로 다를 수 있다.

 

 

만약 case#1을 탐색할 때 memo[arr] 값을 기록해두었다면

case#2를 탐색할 때는 8번 ~1번 카드에 대해서 더 이상 진행할 필요 없이 memo[arr] 값을 활용하면 되는 것이다.

탐색 수가 상당히 크게 감소한다.