[알고리즘 문제 해결 전략] 무식하게 풀기

알고리즘 문제 해결 전략

알고리즘을 공부하면서 문제에 대한 암기보다, 알고리즘 자체에 대한 개념을 학습하기 위해 읽기 시작한 책이다.

• 리뷰 이슈

6장 무식하게 풀기

알고리즘을 고안하는 것은 까다로운 작업이다.

복잡한 요구사항을 프로그램으로 작성해야 할 때 감도 오지 않은 채로 멍하니 모니터만 쳐다본 경험이 있거나 요구사항을 생각하지 않고 시작했다가 엉망으로 꼬인 코드를 만들어본 경험이 있을 것이다.

흔히 상상하는 것과 달리 알고리즘을 설계하는 작업은 한순간의 영감보다는 여러 전력적인 선택에 따라 좌우된다.

알고리즘을 고안하기 위해서는 해결할 문제의 특성을 이해하고, 동작 시간과 사용하는 공간 사이의 상충 관계를 이해해야 하며, 적절한 자료 구조를 선택할 줄 알아야 한다.

알고리즘 설계 패러다임이란, 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다.

어떤 알고리즘들은 문제를 해결하기 위한 가장 중요한 깨달음을 공유하는데, 이와 같은 깨달음들을 모아 보면 일종의 패턴을 확인할 수 있다.

이런 의미에서 이들은 같은 전략, 혹은 같은 설계 패러다임을 통해 문제를 해결했다고 말한다.

알고리즘 설계 패러다임들은 알고리즘 설계를 위한 좋은 틀이 되기 때문에, 이들에 대해 공부하는 것은 알고리즘 설계 능력을 키우는 좋은 방법이다.

도입

알고리즘을 푸는 사람들의 대부분의 실수가 쉬운 문제를 어렵게 푸는 것이다.

공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과한다.

꼭 알고리즘에만 해당하는 것은 아닌 것 같다.

이런 실수를 피하기 위해 문제를 마주하고 나면 가장 먼저 무식하게 풀 수 있는지 검증하는 것이 좋다.

전산학에서 다루는 brute-force(무식하게 푼다)는 말은 컴퓨터의 빠른 계산능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.

두 점 사이의 최단 경로를 찾는 문제라면 두 점 사이의 경로들을 하나 하나 전부 만들어서 그중 가장 짧은 것을 찾는 방법일 테고, 자원을 배분할 수 있는 경우의 수를 세는 문제라면 한 가지씩 분배 방법을 전부 만들어 보는 무식한 알고리즘이 좋은 예라고 할 수 있다.

이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부른다.

정말 간단한 방법이지만 사실 완전 탐색이야 말로 컴퓨터의 장점을 가장 잘 이용하는 방법이다.

컴퓨터의 최대 장점은 단순하게 속도가 빠르다는 것이기 때문이다.

재귀 호출과 완전 탐색

재귀 호출

컴퓨터가 수행하는 많은 작업들은 대개 작은 조각들로 나누어 볼 수 있다.

이런 작업들을 조각을 내면 낼수록 각 조각들의 형태가 유사해지는 작업들을 볼 수 있다.

완전히 같은 코드를 반복해 실행하는 for 같은 반복문이 좋은 예로 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 호출(recursive call) 혹은 재귀 함수(recursive function)이다.

재귀 함수란 자신이 수행할 작업을 유사한 형태의 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

모든 반복문은 재귀 호출로 구현할 수 있고, 모든 재귀 호출은 반복문으로 구현할 수 있다.

// 1부터 n까지의 합을 계산하는 반복 함수와 재귀 함수
int sum(int n) {
    int ret = 0;
    for (int i = 1; i <= n; ++i) 
        ret += i;
    return ret;
}

int recursiveSum(int n) {
    if (n == 1) return 1;
    return n + recursiveSum(n - 1);
}

n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 한다.

재귀 호출을 이용하기 위해선 조각 중 하나를 떼내어 자신이 해결하고, 나머지 조각들은 자기 자신을 호출해 해결해야 한다.

이 조각 중 n만 따로 빼내기로 하고 1부터 n - 1까지의 조각들이 남는데, 이들을 모두 처리한 결과는 다름아닌 1부터 n - 1까지의 합이다.

따라서 자기 자신을 호출해 n - 1까지의 합을 구한 뒤, 여기에 n을 더하면 우리가 원하는 답이 된다.

재귀 호출의 n == 1인 기저 사례(base case)를 잘 처리해야 한다.

n이 1이라면 조각이 하나뿐이기 때문에 ‘더이상 쪼개지지 않는’ 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다.

이때 쪼개지지 않는 가장 작은 작업을 가리켜 기저 사례(base case)라고 부른다.

기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경써야 한다.

만약 n이 2인 경우를 확인하는 경우라면 2이상이라면 문제가 없지만, 1이 입력으로 주어졌을 때는 기저 사례를 처리하지 않았기 때문에 재귀 호출이 무한히 반복될 것이다.

재귀 호출은 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공해준다.

이 함수에서는 기존 코드에 비해 재귀 호출을 통해 얻을 수 있는 별다른 이득이 없다.

문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해 줄 수 있는 강력한 무기가 된다.

예제: 중첩 반목문 대체하기

0번부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자.

예를 들어 n = 7인 경우 (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 2, 5), …, (3, 4, 5, 6)을 모두 출력해야 한다.

// 중첩 반복문으로 구현한 코드
for (int i1 = 0; i1 < n; ++i1)
    for (int i2 = i1 + 1; i2 < n; ++i2)
        for (int i3 = i2 + 1; i3 < n; ++i3)
            for (int i4 = i3 + 1; i4 < n; ++i4)
                printf("%d %d %d %d\n", i1, i2, i3, i4);

만약 다섯 개를 골라야 하는 경우라면 다섯 개의 반복문을 중첩해야 하고, 여섯 개를 골라야 하는 경우라면 여섯 개의 반복문을 중첩해야 한다.

재귀는 이런 작업을 더 간결하고 유연한 코드를 작성할 수 있게 해준다.

위 코드 조각이 하는 작업은 네 개의 조각으로 나눌 수 있다.

각 조각에서 하나의 원소를 고르고, 남은 원소들을 고르는 작업을 자기 자신을 호출하여 떠넘기는 재귀 호출을 수행한다.

이 때 남은 원소들을 고르는 작업을 다음과 같은 입력들로 정의할 수 있다.

• 남은 원소들의 총 개수
• 더 골라야 할 원소들의 개수
• 지금까지 고른 원소들의 번호

// 재귀 호출로 구현한 코드
void pick(int n, vector<int>& picked, int toPick) {
    // 기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
    if (toPick == 0) {
        printPicked(picked);
        return;
    }
    // 고를 수 있는 가장 작은 번호를 계산한다.
    int smallest = picked.empty() ? 0 : picked.back() + 1;
    // 이 단계에서 원소 하나를 고른다.
    for (int next = smallest; next < n; ++next) {
        picked.push_back(next);
        pick(n, picked, toPick - 1);
        picked.pop_back();
    }
}

이와 같이 재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있다.

때문에 재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구다.

예제: 보글 게임

보글 게임은 5x5 크기의 알파벳 격자를 가지고 하는 게임이다.

이 게임의 목적은 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것이다.

hasWord(y, x, word) = 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환한다.

이 문제를 풀 때 까다로운 점은 다음 글자가 될 수 있는 칸이 여러 개 있을 때 이 중 어느 글자를 선택해야 할지 미리 알 수 없다는 것이다.

가장 간단한 방법은 완전 탐색을 이용해 단어를 찾아낼 때까지 모든 인접한 칸을 하나씩 시도해 보는 것이다.

그중 한 칸에서라도 단어를 찾을 수 있다면 성공이고, 어느 칸을 선택하더라도 답이 없다면 실패가 된다.

문제의 분할

hasWord()가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다.

함수 호출시에 단어의 시작 위치를 정해 주기 때문에, 문제의 조각들 중 첫 번째 글자에 해당하는 조각을 간단하게 해결할 수 있다.

시작 위치에 쓰여 있는 글자가 단어의 첫 글자와 다르다면 곧장 false를 반환하고 종료하면 된다.

아니라면 원래 단어에서 첫 글자를 땐 단어 word[1..]에 대해 hasWord()를 재귀 호출한다. (8방향을 다 시도)

기저 사례의 선택

더 이상의 탐색 없이 간단히 답을 낼 수 있는 다음 경우들을 기저 사례로 선택한다.

• 위치(y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
• 위 사례에 해당하지 않을 경우 원하는 단어가 한 글자인 경우 항상 성공

두 조건간의 순서가 바뀌면 안 된다.

간결한 코드를 작성하는 유용한 팁은 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하는 것이다.

그러면 함수를 호출하는 시점에서 이런 오류를 검사할 필요가 없다.

재귀 함수는 항상 한군데 이상에서 호출되기 때문에 이 습관은 반복적인 코드를 제거하는 데 큰 도움이 된다.

따라서 위 두 가지 기저 사례외에도 현재 위치가 보글 게임 판을 벗어난 경우, 첫 글자가 일치하지 않는 경우도 기저 사례로 선택한다.

구현

• Algorithm: 보글 문제

해당 이슈에 바인딩된 PR참고

실제 알고스팟의 문제는 예제문제와 살짝 다르게 시작 위치가 아닌 단어로 주어져서 장 이름에 맞게 더 무식하게 풀어봤다.

오버로딩으로 두 가지 기능을 할 수 있도록 구현했다.

시간 복잡도 분석

완전 탐색 알고리즘의 시간 복잡도를 계산하는 것은 비교적 단순하다.

완전 탐색은 가능한 답 후보들을 모두 만들어 보기 때문에, 시간 복잡도를 계산하기 위해서는 가능한 후보의 수를 전부 세어 보기만 하면 된다.

즉, 후보의 최대 수를 계산하면 된다. (단순)

만약 단어가 없는 경우라면 모든 경우를 탐색해야 하기에 마지막 글자에 도달하기 전에는 주변의 모든 칸에 대해 재귀 호출을 하게 된다.

각 칸에는 최대 여덟 개의 이웃이 있고, 탐색은 단어의 길이 N에 대해 N-1단계가 진행된다.

\[8^{N-1} = O(8^N)\]

이 문제에서 후보의 수는 단어의 길이에 따라 지수적으로 증가하기에 단어의 길이가 짧은 경우에만 완전 탐색으로 해결할 수 있다.

단어의 길이가 조금이라도 길어질 경우 3부의 다른 설계 패러다임을 사용해야 한다.(동적 계획법)

완전 탐색 레시피

모든 문제에 항상 적용되는 것은 아니지만, 어떤 식으로 문제에 접근해야 하는지 대략적인 지침은 될 것이다.

• 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
  • 최대 크기의 입력을 가정했을 때 갑의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있는지 가늠한다. (적용할 수 없으면 동적 계획법을 사용한다.)
• 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
  • 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
• 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
• 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.

이론적 배경: 재귀 호출과 부분 문제

재귀 호출을 공부한다면 짚고 넘어가야 할 중요한 개념이 있다.

문제(problem)와 부분 문제(subproblem)의 정의가 있다.

이 정의는 3부에서 다룰 동적 계획법이나 분할 정복과 같은 디자인 패러다임을 설명하는 데 사용된다.

• 문제: 주어진 자연수 수열을 정렬하라.
• 문제: {16, 7, 9, 1, 31}을 정렬하라.

얼핏 보면 같은 문제라고 할 수 있지만 두 정의 사이에는 큰 차이가 있다.

전자는 특정한 입력을 지정하지 않는 반면, 후자는 특정한 입력을 지정하기 때문이다.

재귀 호출을 논의할 때 문제란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다.

예를 들어 {1, 2, 3}을 정렬하는 문제와 {3, 2, 1}을 정렬하는 문제는 서로 다른 문제다.

따라서 앞의 두 정의 중 엄밀하게는 후자만을 문제의 정의라고 할 수 있다.

보글 게임의 경우 ‘게임판에서의 현재 위치 (y, x) 그리고 단어 word가 주어질 때 해당 단어를 이 칸에서부터 시작해서 찾을 수 있는가?’로 정의된다.

그러면 해당 단어를 이 위치에서 찾을 수 있는지 알기 위해 최대 아홉 가지 정보를 알아야 한다.

• 현재 위치 (y, x)에 단어 첫 글자가 있는가?
• 윗 칸 (y - 1, x)에서 시작해서, 단어의 나머지 글자들을 찾을 수 있는가?
• 왼쪽 위 칸 (y - 1, x - 1)에서 시작해서 단어의 나머지 글자들을 찾을 수 있는가?
• … (반복)

이 중 2번 이후의 항목은 원래 문제에서 한 조각을 떼어냈을 뿐, 형식이 같은 또 다른 문제를 푼 결과다.

문제를 구성하는 조각들 중 하나를 뺐기 때문에, 이 문제들은 원래 문제의 일부라고 할 수 있다.

이런 문제들을 원래 문제의 부분 문제라고 한다.

예제: 소풍

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 간다.

원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 한다.

그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 한다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝 지을 수 있는 방법의 수를 계산하는 프로그램을 작성하시오.

짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 본다.

• (태연, 제시카)(써니, 티파니)(효연, 유리)
• (태연, 제시카)(써니, 유리)(효연, 티파니)

시간 및 메모리 제한

프로그램은 1초 내에 실행되어야 하고, 64MB 이하의 메모리만을 사용해야 한다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C가 주어진다.

각 테스트 케이스의 첫 줄에는 학생의 수 n(2 <= n <= 10)과 친구 쌍의 수 m이 주어진다.

\(n : (2 \le n \le 10 )\) \(m : (0 \le m \le \frac{n(n-1)}{2})\)

그 다음 줄에 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어진다.

번호는 모두 0부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않는다.

학생들의 수는 짝수다.

출력

각 테스트 케이스마다 한 출에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력한다.

예제 입력

3
2 1
0 1
4 6
0 1 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

예제 출력

1
3
4

입출력 설명

가장 먼저 테스트 케이스의 수가 주어진다.

첫 번째 입력은 (2 1)로 학생의 수와 친구 쌍의 수로 n과 m에 해당된다.

m이 1이기 때문에 다음 줄에 오는 쌍은 하나뿐이다.

따라서 0번 학생과 1번 학생이 서로 친구인 상태이다.

두 번째 입력은 (4 6)으로 그 아래줄에 6개의 쌍이 주어진다.

이 경우 4명의 학생 모두 서로 친구인 상태이다.

따라서 4명의 학생을 짝지어 주는 방법은 3가지가 된다.

완전 탐색

이렇게 가능한 조합의 수를 계산하는 문제를 푸는 가장 간단한 방법은 완전 탐색을 이용하여 조합을 모두 만들어보는 것이다.

재귀 호출을 이용해 풀이하기 위해 각 답을 만드는 과정을 여러 조각으로 나눠보자.

여기서는 전체 문제를 n/2개의 조각으로 나누어 한 조각마다 두 학생을 짝지어 주는 것으로 정의한다.

이때 문제의 형태는 ‘아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라’가 된다.

명단에서 서로 친구인 두 학생을 찾아 이들을 짝지어 주고 나면 남는 학생들을 짝지어 주는 문제도 원래 문제와 같은 형태가 된다.

중복으로 세는 문제

위 아이디어를 코드로 그대로 옮기면 전혀 다른 답이 나오는 것을 알 수 있다. (2, 24, 192)

int n;
bool areFriends[10][10];
// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
   // 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
   bool finished = true;
    for (int i = 0; i < n; ++i)
         if (!taken[i])
              finished = false;
    if (finished) return 1;
    int ret = 0;
    // 서로 친구인 두 학생을 찾아 짝을 지어 준다.
    for (int i = 0; i < n; ++i)
         for (int j = 0; j < n; ++j)
              if (!taken[i] && !taken[j] && areFriends[i][j]) {
                   taken[i] = taken[j] = true;
                   ret += countPairings(taken);
                   taken[i] = taken[j] = false;
              }
    return ret;
}

이 코드에서 두 가지 문제점이 있다.

• 같은 학생을 두 번 짝지어 준다. (0,1) 과 (1,0)은 같은 경우로 센다.
• 다른 순서로 학생들을 짝지어 주는 것과 (2,3) 후에 (0,1)을 짝지어주는 것은 완전히 같은 방법인데 다른 경우로 세고 있다.

실질적으로 같은 답을 중복으로 세는 이런 상황은 경우의 수를 다룰 때 굉장히 흔하게 마주치게 된다.

이 상황을 해결하기 위해 선택할 수 있는 좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것이다.

흔히 사용하는 방법으로는 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이 있다.

예를 들어 (2,3),(0,1)이나 (1,0)(2,3)은 세지 않지만 (0,1), (2,3)은 세는 것이다.

이 속성을 강제하기 위해서는 각 단계에서 남아 있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아 주면 된다.

이렇게 하면 앞의 두가지 문제를 해결할 수 있다.

가장 번호가 빠른 학생의 짝은 그보다 번호가 뒤일 수밖에 없기 때문에 (1,0)은 나올 수 없다.

또한 항상 번호가 빠른 학생부터 짝을 짓기 때문에 (2,3),(0,1)의 순서로 짝을 지어줄 일도 없다.

int n;
bool areFriends[10][10];
// taken[i] = i번째 학생이 짝을 이미 찾았으면 true, 아니면 false
int countPairings(bool taken[10]) {
   // 남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
   int firstFree = -1;
    for (int i = 0; i < n; ++i)
         if (!taken[i]) {
              firstFree = i;
              break;
         }
    // 기저 사례: 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
    if (firstFree == -1) return 1;
    int ret = 0;
    // 이 학생과 짝지을 학생을 결정한다.
    for (int pairWith = firstFree + 1; pairWith < n; ++pairWith)
         if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
              taken[firstFree] = taken[pairWith] = true;
              ret += countPairings(taken);
              taken[firstFree] = taken[pairWith] = false;
         }
    return ret;
}

답의 수의 상한

모든 답을 생성해 가며 답의 수를 세는 알고리즘은 답의 수에 정비례하는 시간이 걸린다.

따라서 실제로 프로그램을 짜기 전에 답의 수가 얼마나 될지 예측해 보고 모든 답을 만드는 데 시간이 얼마나 걸리는지 확인해야 한다.

이 문제에서 가장 많은 답을 가질 수 있는 입력은 열 명의 학생이 모두 서로 친구인 경우다.

이때 가장 번호가 빠른 학생이 선택할 수 있는 짝은 아홉 명이고, 그 다음 학생이 선택할 수 있는 짝은 일곱 명이다.

이런 식으로 계속 진행하면 답의 수는 9 x 7 x 5 x 3 x 1 = 945가 된다.

구현

• Algorithm: 피크닉 문제

예제: 게임판 덮기

H x W 크기의 게임판이 있다.

게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮으려고 한다.

이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안된다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성해라

• 시간 및 메모리 제한
  • 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야만 한다.
• 입력
  • 첫 줄에는 테스트 케이스의 수가 주어진다.
  • 각 테스트 케이스의 첫 줄에는 두 개의 정수 H, W가 주어진다.
  • 다음 H 줄에 각 W 글자로 게임판의 모양이 주어진다.
  • #은 검은 칸, .은 흰 칸을 나타낸다.
  • 입력에 주어지는 게임판에 있는 흰 칸의 수는 50을 넘지 않는다.
• 출력
  • 한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력한다.

(자세한 내용은 문제 링크 참고)

이 문제도 경우의 수를 세는 것이니만큼, 게임판을 덮을 수 있는 모든 경우를 생성하는 완전 탐색을 이용해 문제를 해결할 수 있다.

우선 입력으로 주어진 판에서 흰 칸의 수가 3의 배수가 아닐 경우에는 무조건 답이 없다.

이 외의 경우에는 흰 칸의 수를 3으로 나눠서 내려놓을 블록의 수를 N을 얻은 뒤, 문제의 답을 생성하는 과정을 N조각으로 나눠 한 조각에서 한 블록을 내려놓도록 한다.

재귀 함수는 주어진 게임판에 블록을 한 개 내려놓고 남은 흰 칸들을 재귀 호출을 이용해 덮도록 하면 된다.

중복으로 세는 문제

그러나 이런 식으로 덮을 수 있는 방법의 수를 셀 수 없다는 것을 알 수 있다.

블록을 놓는 순서는 이 문제에서 중요하지 않지만 같은 배치도 블록을 놓는 순서에 따라서 여러 번 세기 때문에 특정한 순서대로 답을 생성하도록 강제할 필요가 있다.

가장 간편한 방법으론 재귀 호출의 각 단계마다 아직 빈 칸 중에서 가장 윗 줄, 그 중에서도 가장 왼쪽에 있는 칸을 덮도록 하는 것이다.

이렇게 하면 한 답을 한 가지 방법으로밖에 생성할 수 없으므로 중복으로 세는 문제를 해결할 수 있다.

항상 가장 위, 그 중에서도 가장 왼쪽에 있는 칸을 처음 채운다고 가정하기 때문에 그 왼쪽과 위에 있는 칸은 항상 채워져 있다고 가정할 수 있다.

L블록이기 때문에 총 4가지의 경우로 정리된다.

이 방법으로 달라질 때마다 서로 다른 배치가 되므로 남은 게임판에 대해서 재귀호출로 넘겨서 얻은 경우의 수를 구할 수 있다.

답의 수의 상한

이 문제의 답의 최대는 한 블록당 4가지의 선택지와 최대 블록의 개수가 50개이기 때문에 가능한 답의 상한은 다음과 같다.

\[\frac{50}{3} = 16\] \[4^{16} = 2^{32}\]

이것만 봐서는 도저히 시간 내에 모두 생성할 수 없을 것 같지만, 실제 입력을 손으로 풀어본다면 각 단계에서 선택할 수 있는 블록의 배치가 제한됨을 알 수 있다.

전 배치가 다음 배치의 영향을 주기 때문에

구현

• BOARDCOVER 구현

최적화 문제

지금까지 다뤘던 문제와는 달리 문제의 답이 하나가 아닌 여러개이고, 그 중에서 어떤 기준에 따라 가장 좋은 답을 찾아 내는 문제들을 통칭 최적화 문제라고 한다.

• n개의 원소 중에서 r개를 순서 없이 골라내는 방법의 수를 계산하는 것은 최적화 문제가 아니다.
• n개의 사과 중에서 r개를 골라서 무게의 합을 최대화하는 문제는 최적화 문제에 해당한다.

사과를 골라내는 방법은 중 특정 기준에 의해 가장 좋은 답을 고르는 문제이기 때문이다.

최적화 문제를 해결하는 방법을 여러 가지 다루고 있는데, 그 중 가장 기초적인 것이 완전 탐색이다.

완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법으로 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문이다.

예제: 여행하는 외판원

가장 유명한 최적화 문제로 여행하는 외판원 문제가 있다.

어떤 나라에 n(2 <= n <= 10)개의 큰 도시가 있다.

한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다.

문제를 간단하게 하기 위해 모든 도로는 직선으로 연결되어 있다고 가정한다.

이때 영업 사원이 여행해야 할 거리는 어느 순서로 각 도시들을 방문하느냐에 따라 달라진다.

무식하게 풀 수 있을까?

완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 있을지 확인하는 것이다.

시작한 도시로 돌아오는 경로를 찾기 때문에, 경로의 시작점은 신경 쓰지 않고 무조건 0번 도시에서 출발한다고 가정해도 길이는 다르지 않다.

n - 1개의 도시를 나열하는 방법은 모두 (n - 1)!가지가 있다.

도시가 열개라면 총 경로의 수는 9! = 362,880개가 된다.

사람이 보기엔 큰 수이지만, 여전히 컴퓨터는 1초 안에 가볍게 처리가 가능하다.

예제: 시계 맞추기

그림과 같이 4x4개의 격자 형태로 배치된 열여섯 개의 시계가 있다.

이 시계는 모두 12시, 3시, 6시 혹은 9시를 가리키는데, 이 시계들을 모두 12시를 가리키도록 하고 싶다.

시계의 시간을 조작하는 유일한 방법은 열개의 스위치를 조작하는 것으로, 각 스위치들을은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결되어 있다.

한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다.

번호와 연결된 시계에 따라 최소 몇번의 스위치 조작을 통해 모든 시계를 12시로 돌릴 수 있는지 작성하라

• 시간 및 메모리 제한
  • 10초안에 실행되어야 하며 64MB 이하의 메모리를 사용해야 한다.
• 입력
  • 첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9중 하나로 표현한다.
• 출력
  • 각 테스트 케이스당 정수 하나를 한 줄에 출력한다.
  • 이 정수는 시계들을 모두 12시로 돌려놓기 위해 스위치를 눌러야 할 최소 횟수이며, 만약 불가능하다면 -1을 출력해야 한다.

문제 변형하기

이 문제는 있는 그대로 풀면 꽤나 복잡하다.

그러나 문제의 특성을 이용해 적절히 단순화하면 완전 탐색으로 해결할 수 있다.

이 문제의 중요한 점은 예제 입출력 설명이 유도하는 방향과는 달리 스위치를 누르는 순서는 전혀 중요하지 않다는 것이다.

두 스위치를 누르는 순서를 바꾼다고 해서 그 결과가 바뀌지 않기 때문이다.

따라서 우리가 계산해야 할 것은 스위츠를 몇 번이나 누를 것이냐 뿐이다.

문제를 바꾼다고 해서 완전 탐색을 바로 적용할 수는 없고 사용하려면 누르는 횟수의 조합을 하나하나 열거할 수 있어야 하는데, 그 조합의 수는 무한하다.

하지만 시계는 12시간이 지나면 제자리로 돌아온다는 점을 이용하면 유한하게 바꿀 수 있다.

어떤 시계든 4번 누른 경우에 누르지 않은 것과 같기 때문에 어떤 스위치던 3번 이상 누를 일이 없어진다.

따라서 스위치를 누르는 경우의 수는 0~3으로 나오고 이를 계산하면 4^10 = 1,048,576개가 된다.

구현

• CLOCKSYNC 구현

많이 등장하는 완전 탐색 유형

주어진 원소로 만들 수 있는 모든 순열 만들기, 주어진 원소 중 R개를 골라낼 수 있는 방법 만들기 등은 다른 문제의 부분 문제로도 빈번히 출제된다.