구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.
📕 목차

1. 도입
2. 재귀 호출과 완전 탐색
3. 소풍 (문제 ID: PICNIC, 난이도: 하) 
4. 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)
5. 최적화 문제(Optimization problem)
6. 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)
7. 많이 등장하는 완전 탐색 유형

1. 도입

 

공부를 할 수록 우아한 답안을 만들고 싶은 욕구가 커지고, 그로 인해 쉽고 간단하며 틀릴 가능성이 낮은 답안을 놓치는 경우가 있다.

문제를 가장 처음 봤을 때는 "무식하게 풀 수 있을까?"라고 스스로에게 먼저 물어봐야 한다.

 

무식하게 푸는(brute-force) 알고리즘을 완전 탐색(exhaustive search)이라고 부른다.

  • 시간, 공간 제한이 없다면 완전 탐색 알고리즘은 모든 문제를 해결할 수 있다.
  • 컴퓨터의 최대 장점인 빠른 연산 속도를 이용한다면, 충분히 해결 가능한 문제도 더러 있다.

설령 완전 탐색으로 해결되지 않는다 하더라도, 적어도 더 빠른 알고리즘의 기반이 되기도 하기 때문에 잘 익혀둘 필요가 있다.

 

완전 탐색은 논리적으로 딱히 어려운 내용은 없기 때문에 설명을 좀 대충 적어놨다..

코드를 읽어보고 이해하는 게 중요하니까 ㅎㅎ

 

2. 재귀 호출과 완전 탐색

 

• 재귀 호출(recursion)
• 예제: 중첩 반복문 대체하기
• 예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)
• 시간 복잡도 분석
• 완전 탐색 레시피
• 이론적 배경: 재귀 호출과 부분 문제

 

📌 재귀 호출(recursion)
// 코드 6.1 1부터 n까지의 합을 계산하는 반복 함수와 재귀 함수

// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int sum(int n) {
    int ret = 0;
    for (int i=1; i<=n; i++)
        ret += i;
    return ret;
}

// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int recursiveSum(int n) {
    if (n == 1) return 1; // 기저 사례: n = 1일 때
    return n + recursiveSum(n - 1);
}
  • 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤, 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
  • 기저 사례(base case) : 더 이상 쪼개지지 않는 최소한의 작업들 (답을 곧장 반환해야 한다.)

 

✒️ 반복문 vs 재귀

  반복성 재귀 함수
기본 명령을 반복 실행 함수 자체를 호출
체재 초기화, 조건, 루프 내 명령문 실행과 제어 변수 업데이트를 포함 탈출 조건만 지정 (조건이 추가될 수 있음)
종료 설정한 조건에 도달할 때까지 반복 탈출 조건에 부합하는 경우 반환
조건 제어 조건이 참이라면 무한 반복 탈출 조건에 수렴하지 않을 경우 무한 재귀
무한 반복 CPU 사이클을 반복적으로 사용 StackOverFlow
스택 메모리 사용하지 않음 함수가 호출될 때마다 새 로컬 변수와 매개 변수 집합, 함수 호출 위치를 저장
속도 빠르다 느리다
가독성 코드 길이와 반복 변수로 인해 가독성 저하될 수 있음 코드 길이와 변수가 적어 가독성이 높아지는 경우가 많음

그럼에도 재귀적인 표현이 훨씬 직관적인 경우가 많고, 변수 사용량을 줄여줌으로써 Side effect를 최소화할 수 있다.

 

📌 예제: 중첩 반복문 대체하기
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        for (int k = j+1; k < n; k++)
            for (int l = k+1; l < n; l++)
                cout << i << " " << j << " " << k << " " << l << endl;
  • 골라야 할 원소수가 늘어날 수록 코드가 지저분하고, 로직이 복잡해진다.
  • 위 코드는 4개의 조각으로 나눌 수 있다. 각 조각에서 하나의 원소를 고르면 된다.
  • 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기면 된다.
    • 원소들의 총 개수
    • 더 골라야 할 원소들의 개수
    • 지금까지 고른 원소들의 번호

 

// 코드 6.2 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

void printPicked(vector<int>& picked);

// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호
// toPick: 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
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();
    }
}

void printPicked(vector<int>& picked) {
    for (int i = 0; i < picked.size(); ++i)
        cout << picked[i] << " ";
    cout << endl;
}

 

📌 예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)
 

algospot.com :: BOGGLE

보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어

algospot.com

5x5에 랜덤한 알파벳이 적혀있고, 상하좌우로 이동하면서 내가 아는 알파벳을 의미하는 연속된 문자열을 찾아내면 된다.

여기서 무식한 방법을 사용하기 위해선 하나의 단어를 택하고, 다음으로 갈 수 있는 모든 방향에 대해 탐색을 해보면 된다.

 

1️⃣ 문제의 분할

  • hasWord(y, x, word) = 보글 게임판 (y, x)에서 시작하는 단어 word의 존재 여부 반환
  • 각 글자를 하나의 조각으로 만들면 된다.
  • 단어를 선택했을 때, 조합이 안 맞으면 재귀 깊이를 다시 한 단계 높이고 다음 단계를 탐색한다.

 

2️⃣ 기저 사례의 선택

  1. (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패한다.
  2. (1번 경우 제외) 원하는 단어가 한 글자인 경우 항상 성공

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

💡 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 처음에 처리하면 반복 코드를 제거할 수 있다.

 

3️⃣ 구현

// 코드 6.3 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘

const int dx[8] = { -1, -1, -1,  1, 1, 1,  0, 0 };
const int dy[8] = { -1,  0,  1, -1, 0, 1, -1, 1 };
// 5*5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환한다.
bool hasWord(int y, int x, const string& word) {
    // 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
    if (y < 0 || y >= 5 || x < 0 || x >= 5) return false;
    // 기저 사례 2: 첫 글자가 일치하지 않으면 실패
    if (board[y][x] != word[0]) return false;
    // 기저 사례 3: 단어 길이가 1이면 성공
    if (word.size() == 1) return true;
    // 인접한 여덟 칸을 검사한다.
    for (int direction = 0; direction < 8; ++direction) {
        int nextY = y + dy[direction], nextX = x + dx[direction];
        // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
        if (hasWord(nextY, nextX, word.substr(1)))
            return true;
    }
    return false;
}

 

📌 시간 복잡도 분석
  • 모든 경우의 수를 세면 그것이 전탐색의 시간 복잡도가 된다.
  • 위 문제의 경우, 답을 하나라도 찾으면 중간에 종료되므로 "최악의 경우"를 가정하고 계산하면 된다. (답이 없을 경우)
  • A로 가득 들어찬 곳에서 "AAAAAH"를 찾는다고 하면, 길이(N)만큼 전방향(8번)을 탐색하게 된다.
  • 따라서 시간 복잡도는 \( 8^{N - 1} = O(8^{N}) \)가 된다.
💡 2차원 배열을 순회하는 과정은 알고리즘 시간 복잡도가 아니라 프로그램 전체 시간 복잡도이므로, 해당 로직은 여기서 고려하지 않는다.

 

📌 완전 탐색 레시피
  1. 전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
    • 최대 크기 입력, 최악의 경우를 가정하고 시간 복잡도를 계산하라.
    • 만약 시간 제한에 걸린다면 설계 패러다임을 적용해야 한다.
  2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눠라.
    • 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
  3. 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성하라.
  4. 조각이 하나밖에 남지 않았거나, 하나도 남지 않은 경우 기저 사례로 선택해 처리하라.

 

📌 이론적 배경: 재귀 호출과 부분 문제
  • 문제(problem)과 부분 문제(subproblem)의 차이를 알아야 한다.
  • 문제'란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미한다.
    • 문제: 주어진 자연수 수열을 정렬하라.
    • 문제: {16, 7, 9, 1, 31}을 정렬하라.
    • 엄밀하게는 특정한 입력을 지정한 후자만을 문제의 정의라 할 수 있다.
  • 보글 게임에서도 (y x), (y-1, x), (y-1, x-1), ...의 단어 적합성을 탐색하는 최소 9가지 정보가 필요하다.
    • 하지만 모두 형식이 같은 또 다른 문제일뿐이다.
    • 이런 문제들을 원래 문제의 부분 문제라 칭한다. 

 

3. 소풍 (문제 ID: PICNIC, 난이도: 하) 

 

📌 문제
 

algospot.com :: PICNIC

소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로

algospot.com

친구를 짝지어주는 간단한 문제다.

 

📌 완전 탐색
  • 재귀 호출을 이용한다면, 우선 각 답을 만드는 과정을 여러 개의 조각으로 나눠라.
  • 전체 문제를 N/2개로 나누어, 한 조각마다 두 학생을 짝지어주는 방법이 있다.

 

📌 중복으로 세는 문제
// 코드 6.4 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드

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 = i+1; 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)과 (1 0), (2 3)은 세지 않아도 (0 1) (2 3)은 세는 것이다. (오름차순)
  • 이번 문제에서는 학생들 중 가장 번호가 빠른 학생의 짝을 먼저 찾아주면 된다.

 

// 코드 6.4 소풍 문제를 해결하는 재귀 호출 코드

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;
}

순간 이게 왜 답이 되는 거지? 싶었는데 문제를 잘못 이해하고 있던 거였다..

난 그냥 묶을 수 있으면 다 묶는 건 줄 알았는데, 두 명씩 짝짓는 문제였다. :)

 

📌 답의 수의 상한
  • 모든 답을 생성해 가며 답의 수를 세는 재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸린다.
  • 이 문제의 최악의 경우는 10명이 모두 친구인 경우다.
    • 이 때 경우의 수는 9 * 7 * 5 * 3 * 1 = 945

 

4. 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)

 

📌 문제
 

algospot.com :: BOARDCOVER

게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이

algospot.com

그리 어렵지 않게 전탐색을 떠올려볼 수 있는 문제다.

'ㄴ'자의 중심부분을 기준으로 빙빙 돌리면, 하나의 좌표에서 최대 4가지 경우가 탐색 가능하다.

 

그리고 우선 입력에서 힁 칸의 수가 3의 배수가 아니라면 무조건 답이 없으니 예외 처리하고 시작해야 한다.

 

📌 중복으로 세는 문제
  • 블록을 하나 놓고 남은 흰 칸들을 재귀 호출로 덮는 방식은 블록을 놓는 순서에 따라 여러 번 세게 된다.
  • 가장 간편한 방법은 가장 윗줄, 가장 왼쪽의 칸을 최우선으로 덮도록 세는 것이다. (순서 강제)

 

📌 답의 수의 상한
  • 문제 조건에 의해 흰 칸은 최대 50개가 있을 수 있다.
  • 놓을 수 있는 블록은 50/3의 몫인 16이 최대치
  • 블록을 놓을 때 4가지 경우의 방향이 존재하므로 4^16 = 2^32 개가 상한이다.
  • 하지만 실제로 가능한 경우가 그리 많지 않다. (흰 칸이 48개여도 답은 1,514에 그친다.)
  • 상한이 그리 크지 않으므로 전탐색으로 충분히 해결할 수 있는 문제다.

 

📌 구현
// 코드 6.6 게임판 덮기 문제를 해결하는 재귀 호출 알고리즘

// 주어진 칸을 덮을 수 있는 네 가지 방법
// 블록을 구성하는 세 칸의 상대적 위치 (dy, dx)의 목록
const int coverType[4][3][2] = {
    { { 0, 0 }, { 1, 0 }, { 0, 1 } },
    { { 0, 0 }, { 0, 1 }, { 1, 1 } },
    { { 0, 0 }, { 1, 0 }, { 1, 1 } },
    { { 0, 0 }, { 1, 0 }, { 1, -1 } }
};

// board의 (y, x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다.
// delta = 1이면 덮고, -1이면 덮었던 블록을 없앤다.
// 만약 블록이 제대로 덮이지 않은 경우 (게임판 밖으로 나가거나, 겹치거나,
// 검은 칸을 덮을 때) false를 반환한다.
bool set(vector<vector<int>>& board, int y, int x, int type, int delta) {
    bool ok = true;
    for (int i = 0; i < 3; ++i) {
        const int ny = y + coverType[type][i][0];
        const int nx = x + coverType[type][i][1];
        if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size())
            ok = false;
        else if ((board[ny][nx] += delta) > 1)
            ok = false;
    }
    return ok;
}

// board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
// board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
// board[i][j] = 0 아직 덮이지 않은 칸
int cover(vector<vector<int>>& board) {
    // 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
    int y = -1, x = -1;
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[i].size(); ++j)
            if (board[i][j] == 0) {
                y = i;
                x = j;
                break;
            }
        if (y != -1) break;
    }
    // 기저 사례: 모든 칸을 채웠으면 1을 반환한다.
    if (y == -1) return 1;
    int ret = 0;
    for (int type = 0; type < 4; ++type) {
        // 만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출한다.
        if (set(board, y, x, type, 1))
            ret += cover(board);
        // 덮었던 블록을 치운다.
        set(board, y, x, type, -1);
    }
    return ret;
}
  • y, x delta 값을 coverType에 저장해두었다.
  • set() 함수로 delta에 따라 블럭을 놓고 치우는 역할을 수행한다. 동시에 블록을 놓을 수 있는지 여부도 판단한다.
  • set()에서 블록을 놓다가 유효하지 않은 칸이 나왔다고 곧장 종료하면, 기존에 놓여있던 블록까지 치워버리게 될 수 있어서 '일단 1을 더해놓고' 나중에 제거하고 있다.

솔직히 보면서...이렇게까지 무식하게 푼다고? 라는 생각이 들었다.

 

5. 최적화 문제(Optimization problem)

 

최적화 문제는 답이 딱 하나밖에 없는 문제가 아니라, 더 좋거나 덜 좋은 답이 있는 문제들이다.

예컨대, n개의 사과 중 r개를 골라 무게의 합을 최대화 하는 문제, 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화하는 문제 등이 그렇다.

단순히 n개의 원소 중에서 r개를 순서 없이 골라내는 방법의 수를 계산하는 것은 포함되지 않는다.

 

📌 예제: 여행하는 외판원 문제
 

2098번: 외판원 순회

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

TSP(Traveling Salesman Problem)은 가장 유명한 최적화 문제 중 하나다. 

 

📌 무식하게 풀 수 있을까?

Network Flow로 풀릴 거 같기도 한데, 제대로 안 풀어봐서 모르겠다.

여튼 도시를 하나씩 방문하면 (n-1)! 가지의 경우가 존재하겠지만, 여기선 n=10으로 고정했다고 가정하면 9! = 362,880 으로 전탐색으로도 널널하다.

 

완전 탐색 문제 풀이의 첫 단계는 "시간 안에 답을 구할 수 있을지 확인"하는 것이다!! 

 

📌 재귀 호출을 통한 답안 생성
// 코드 6.7 여행하는 외판원 문제를 해결하는 재귀 호출 알고리즘

int n; // 도시의 수
double dist[10][10]; // 두 도시 간의 거리를 저장하는 배열

// path: 지금까지 만든 경로
// visited: 각 도시의 방문 여부
// currentLength: 지금까지 만든 경로의 길이
// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
    // 기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료한다.
    if (path.size() == n)
        return currentLength + dist[path[0]][path.back()];
    double ret = INF; // 매우 큰 값으로 초기화
    // 다음 방문할 도시를 전부 시도해 본다.
    for (int next = 0; next < n; ++next) {
        if (visited[next]) continue;
        int here = path.back();
        path.push_back(next);
        visited[next] = true;
        // 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
        double cand = shortestPath(path, visited, currentLength + dist[here][next]);
        ret = min(ret, cand);
        visited[next] = false;
        path.pop_back();
    }
    return ret;
}

방문 여부 배열 visited와 경로 path, 경로 길이 currentLength를 이용하여 n개의 도시로 구성된 경로를 n개의 조각으로 나누었다.

 

6. 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

 

📌 문제
 

algospot.com :: CLOCKSYNC

Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록

algospot.com

처음에 '난이도 하랑 중의 난이도 격차가 제법 큰 것 같은데..?'라고 생각했는데

스위치 번호에 연결된 시계들을 문제 조건에서 줘버려서 시시한 문제가 되어버렸다..

 

📌 문제 변형하기
  • 예제 입출력 설명이 유도하는 방향과 달리 스위치를 누르는 순서는 전혀 중요하지 않다.
  • 스위치를 누르는 순서가 아니라, 각 스위치를 몇 번 누를 것인지가 결과에 영향을 미친다.
  • 그럼에도 전탐색을 하려면 스위치를 누르는 횟수의 모든 조합을 열거할 수 있어야 하는데, 현재로써 조합의 수는 무한대다.
    • 12시간이 지나면 제자리로 돌아오는 성질을 이용하면 유한한 조합으로 바꿀 수 있다.
    • 어떤 스위치든 4번 이상 누르는 것은 의미가 없다.
  •  따라서 전체 경우의 수는 4^10개가 된다.

 

📌 완전 탐색 구현하기
// 코드 6.8 시계 맞추기 문제를 해결하는 완전 탐색 알고리즘

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
// linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
// linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS + 1] = {
    // 0123456789012345
    "xxx.............", // 0번 스위치와 연결된 시계들
    "...x...x.x.x....", // 1번 스위치와 연결된 시계들
    "....x.....x...xx", // 2번 스위치와 연결된 시계들
    "x...xxxx........", // 3번 스위치와 연결된 시계들
    "......xxx.x.x...", // 4번 스위치와 연결된 시계들
    "x.x...........xx", // 5번 스위치와 연결된 시계들
    "...x..........xx", // 6번 스위치와 연결된 시계들
    "....xx.x......xx", // 7번 스위치와 연결된 시계들
    ".xxxxx..........", // 8번 스위치와 연결된 시계들
    "...xxx...x...x.." // 9번 스위치와 연결된 시계들
};
// 모든 시계가 12시를 가리키고 있는지 확인한다.
bool areAligned(const vector<int>& clocks) {
    for (int clock = 0; clock < CLOCKS; ++clock)
        if (clocks[clock] != 12) return false;
    return true;
}
// swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch) {
    for (int clock = 0; clock < CLOCKS; ++clock)
        if (linked[swtch][clock] == 'x') {
            clocks[clock] += 3;
            if (clocks[clock] == 15) clocks[clock] = 3;
        }
}
// clocks: 현재 시계들의 상태
// swtch: 이번에 누를 스위치의 번호
// 가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
// 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
    if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
    // 이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도한다.
    int ret = INF;
    for (int cnt = 0; cnt < 4; ++cnt) {
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }
    // push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 된다.
    return ret;
}
  • 불가능한 경우 INF를 return하여 처리해야 한다. (최소값을 구하고 있는데 -1을 쓸 수는 없으므로)
  • 이건 진짜 좀 이해가 안 가는데..굳이 linked라는 2차원 배열을 그려서 표시했다. 재밌는 방법이긴 한데, 난 안 쓸 것 같다.

 

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

 

📌 모든 순열 만들기
  • 순열(permutation) : 서로 다른 N개의 원소를 일렬로 줄 세운 것
  • 주어진 원소의 모든 순열을 생성해서 풀 수 있는 문제
  • 모든 순열을 생성하는 코드도 신경 써서 작성해보면 좋다. (다른 문제의 부분 문제로 나타날 수 있다.)
  • 단, 가능한 순열의 수는 N!이니 N=10을 넘어간다면 다른 전략을 구상해야 한다.
  • C++ STL의 next_permutation() 함수가 모든 순열을 순서대로 생성하는 작업을 대신 해주므로 유용하다.

 

📌 모든 조합 만들기
  • 조합(combination) : 서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것
  • 경우의 수는 이항 계수 \(  \binom{N}{R} \)로 정의된다.

 

📌 2^(n)가지 경우의 수 만들기
  • n개의 질문에 대한 답이 Y/N 중의 하나라면, 존재 가능한 모든 조합의 수가 \(2^{n}\)가지
  • 각 조합을 하나의 n비트 정수로 표현한다고 하면 재귀 호출을 사용할 것 없이 1차원 for문 하나로 이 조합들을 간단하게 모두 시도할 수 있다.

 

저작자표시 비영리

티스토리툴바