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

문제풀이 과정에서 가장 간단하면서 틀릴 가능성이 낮은
'완전 탐색(exhaustive search)' 알고리즘과
이를 구현하는데 유용한 '재귀 호출(recursion)'을 이해하고
문제를 통해 직접 구현해보자.

 

 

완전 탐색과 재귀 호출

완전 탐색

• 완전 탐색(exhaustive search): 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법
• 경우의 수가 커지더라도 컴퓨터의 계산 능력을 고려하면 생각보다 훨씬 간편하게 문제를 풀 수도 있다.

 

재귀 호출

• 재귀 함수(recursive function): 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
• 재귀 함수에는 "더이상 쪼개지지 않는" 최소한의 작업에 도달했을 때, 답을 바로 반환하는 조건문을 포함해야 하는데 이를 기저 사례(base case)라고 한다.

#include <iostream>

using namespace std;

int sum(int n)
{
    int ret = 0;
    for(int i=0; i<= n; i++)
    {
        ret += i;
    }
    return ret;
}

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

int main(void)
{
    cout<<sum(10)<<" "<<recursiveSum(10)<<endl;
    return 0;
}

55 55

-> sum 함수의 기능을 재귀로 표현한 recursiveSum

 

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

https://www.algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string board[5];

// y,x가 범위 안에 있으면 true, 밖이면 false
bool inRange(int y, int x)
{
    if(y >= 0 && y < 5 && x >= 0 && x < 5)
        return true;
    else
        return false;
}

//y,x에서 시작해서 word가 존재하면 true
bool hasWord(int y, int x, const string& word)
{
    //y,x가 범위 밖이면 false 반환
    //y,x 위치의 글자가 단어의 첫 글자가 아닌 경우 false 반환
    //word의 길이가 1글자면 true 반환
    //검증한 다음 글자에 대해서 y,x의 주변 위치에서 hasWord 실행
    if(!inRange(y, x))
        return false;
    else if(board[y][x] != word[0])
        return false;   
    else if(word.size() == 1)
        return true;
    else
    {    
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (i == 0 && j == 0)
                {
                    continue;
                }
                if (hasWord(y + i, x + j, word.substr(1)))
                {
                    return true;
                }
            }
        }
    }
    return false;
}

int main(void)
{
    int C;
    cin >> C;

    while(C--)
    {
        //board 채우기
        for(int i = 0; i < 5; i++)
        {
            cin>>board[i];
        }

        int N;
        cin >> N;
        //N개의 word 검증
        for(int n = 0; n < N; n++)
        {
            bool Check = false;
            string word;
            cin >> word;
            for(int a = 0; a < 5; a++)
            {
                for(int b = 0; b < 5; b++)
                {
                    Check = hasWord(a, b, word);
                    if(Check)
                    {
                        break;
                    }
                }
                if(Check)
                {
                    break;
                }
            }
            if(Check)
            {
                cout << word << " YES" << endl;
            }
            else
            {
                cout<< word << " NO" << endl;
            }
        }
    }
    return 0;
}

1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
PRETTY YES
GIRL
GIRL YES
REPEAT
REPEAT YES
KARA
KARA NO
PANDORA
PANDORA NO
GIAZAPX
GIAZAPX YES

>> board의 모든 위치에 대해서 hasWord를 적용해 완전 탐색!!

>> 입력이 잘못되거나, 범위를 벗어난 경우를 기저 사례로 맨 처음에 처리해버리는 습관 -> 함수 호출 시점에 오류 검사를 할 필요가 없어짐

 

시간 복잡도 분석

• 마지막 글자만 board에 포함되지 않고 앞의 글자들이 연결된다고 했을 때 최악의 경우라고 할 수 있다.
• 이 경우 각 칸에 최대 8개의 이웃이 있고, 탐색은 단어의 길이 N에 대해 N-1 단계 진행되기 때문에 최대 후보의 수는 8^(N-1)이고, 이를 Big-O Notation으로 표현하면 시간 복잡도는 $O(8^N)$이다.
• 지수 함수의 특성에 따라 단어의 길이가 길어질수록 시간 복잡도는 급격히 늘어나기 때문에 단어가 짧은 경우만 사용하는 것이 좋다고 볼 수 있다.

 

배운 점

• 기본 자료형에 대해서 [][] << 2중으로 인덱싱하여 arr처럼 접근할 수 있음.
• while(cases--) << 해당 형태로 간단하게 case를 나눌 수 있음

완전 탐색 레시피

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 입력을 가정했을 때 답의 개수를 계산하고, 제한 시간 안에 생성할 수 없다면 다른 설계 패러다임을 적용하자.

2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이다.

3. 2.에서 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.

4. 조각이 하나만 남은 경우, 혹은 하나도 남지 않은 경우는 기저 사례로 선택해 처리한다.

 

재귀 호출과 부분 문제

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

위에서 특정한 입력을 지정한 후자의 경우는 '문제', 원래 문제의 일부를 나타내는 전자의 경우를 '부분 문제'라 한다.

 

예제2: 소풍 (문제 ID: PICNIC, 난이도: 하)

https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

 

#include <iostream>
#include <cstring>
#include <cassert>
#include <vector>

using namespace std;

int n, m;
bool areFriends[10][10];  //둘이 친구인지 판별

/***
중복을 고려하지 않은 경우!!
bool countPairings(bool taken[10])
{
    //base case: 모든 학생이 짝을 찾았다면 종료
    bool finished = true;
    for(int i=0; i<n; i++)
        if(!taken[i])
            finished = false;
    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;
}
***/

int countPairings(bool taken[10])
{
    //남은 학생들 중 가장 번호가 빠른 학생
    int firstFree = -1;
    for(int i=0; i<n; i++)
    {
        if(!taken[i])
        {
            firstFree = i;
            break;
        }
    }

    //base case: 모든 학생이 짝을 찾았으면 종료
    if(firstFree == -1) return 1;
    int ret = 0;
    for(int pairWith = (firstFree+1); pairWith < n; pairWith++) //이미 짝을 찾은 학생의 경우를 skip하고 탐색
    {
        if(!taken[pairWith] && areFriends[firstFree][pairWith])
        {
            taken[firstFree] = taken[pairWith] = true;
            ret += countPairings(taken);
            taken[firstFree] = taken[pairWith] = false;
        }
    }
    return ret;
}

int main(void)
{
    int cases;
    cin >> cases;

    while(cases--)    //cases 횟수만큼 반복
    {
        cin >> n >> m;
        assert(n<=10);
        memset(areFriends, 0, sizeof(areFriends));  //areFriends 배열 모두 0으로 초기화
        for(int i=0; i<m; i++)
        {
            int a, b;
            cin >> a >> b;
            assert(0 <= a && a < n && 0 <= b && b < n);
            assert(!areFriends[a][b]);
            areFriends[a][b] = areFriends[b][a] = true;
        }
        bool taken[10];
        memset(taken, 0, sizeof(taken));
        cout << countPairings(taken) << endl;
    }
}

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

>> 학생 수 size를 가진 arr에 중첩 반복문으로 접근하여 i, j가 서로 친구인지, 각각 이미 짝이 있는지 판별

problem1) (1, 0), (0, 1)과 같이 중복되는 경우까지 중복으로 센다.

problem2) (0, 1) 후에 (2, 3)을 짝지어주는 거과 (2, 3) 후에 (0, 1)을 짝짓는 것을 다르게 판별.

 

Solving) 짝짓는 순서를 강제하기 -> 각 단계에서 가장 빠른 번호 학생의 짝을 찾는다. 

 

시간 복잡도 분석

• 가장 많은 답을 가질 수 있는 경우는 모든 학생이 서로 친구인 경우이다.
• 가장 번호가 빠른 학생이 선택할 수 있는 짝은 9명, 7명, 5명 ... 1명이다. 
• 따라서, 최조 답의 개수는 9*7*5*3*1 = 945가 된다.

 

배운 점

• int arr[][] -> 배열 형태로 접근 가능
• assert(expression) -> expression이 false면 assert error!(오류 검출)
• memset(포인터, 설정할 값, 크기) -> 1바이트 단위로 해당 주소를 초기화

 

 

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

https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

 

#include<numeric>
#include<algorithm>
#include<cassert>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

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

//type에 맞게 board를 채우거나 비운다(mode==1이면 덮고, mode ==-1이면 비움)
//제대로 채워지지 않는 경우 false 반환(범위를 넘어가거나, 이미 채워진 경우)
bool set(int y, int x, vector<vector<int>>& board, int type, int mode)
{
    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] += mode) > 1) // 이미 채워져 있으면
        {
            ok = false;
        }
    }
    return ok;
}

//채울 수 있는 경우의 수 반환
int NumofCases(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(y, x, board, type, 1))
            ret += NumofCases(board);
        // 덮었던 블록을 치운다
        set(y, x, board, type, -1);
    }
    return ret;
}

int main(void)
{
    int cases;
    cin>>cases;


    for(int cc=0; cc<cases; cc++)
    {
        int H, W;
        cin >>H>>W;
        assert(1 <= H && H <= 20);
        assert(1 <= W && W <= 20);
        vector<vector<int>> BlankBoard(H, vector<int>(W, 0));
        for(int a=0; a<H; a++)
        {
            string Blocks;
            cin>>Blocks;
            for(int b=0; b<W; b++)
            {
                if(Blocks[b] == '#')
                    BlankBoard[a][b] = 1;
            }
        }
        int numCases = NumofCases(BlankBoard);
        cout << numCases << endl;
    }
    return 0;
}

3 
3 7 
#.....# 
#.....#
##...##
0
3 7
#.....#
#.....# 
##..###
2
8 10
##########
#........#
#........# 
#........#
#........#
#........#
#........# 
##########
1514

>> 최좌측 상단의 비어있는 위치를 찾은 이후 그로부터 4가지 case로 블럭을 채우는 과정을 재귀를 통해서 반복

>> set 함수에서 mode가 자체적으로 칸을 채우고 비워주므로, 코드를 추가할 필요 없다.

 

시간 복잡도 분석

• 최대 int(50/3) = 16개의 블록을 놓을 수 있기 때문에 4가지 case로 나눠서 생각하면 가능한 답의 상한은 4^16 = 2^32개가 된다.

 

배운 점

• 디버깅하느라 정말 한참 걸린 문제인데 원인은 vector 매개변수 전달에서 발생했다.
• vector를 매개변수로 전달할 때, 참조자 형태로 전달해야 함수 내부에서 해당 vector의 내부 구성요소를 변화시킬 수 있다. 또한, vector의 경우 메모리 공간을 많이 차지할 확률이 크므로, 복사의 형태가 아닌 참조자 형태로 전달하는 것이 좋다.

 

최적화 문제

• 최적화 문제(Optimization problem): 문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾는 문제를 의미한다.
• ex) n개의 사과 중에서 r개를 골라 무게의 합을 최대화하는 문제
• 이를 해결하는 여러 가지 방법이 있는데, 이중 가장 기초적인 것이 완전 탐색이다.

 

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

https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

const int INF = 9999;
const int CLOCKS = 16;
const int SWITCHES = 10;

const char linked[SWITCHES][CLOCKS+1] =
{
    "xxx.............",
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
};


//12시에 맞춰져있는지
//clocks는 현재 시계들의 상태
bool areAlinged(const vector<int>& clocks)
{
    for(int clock = 0; clock<CLOCKS; clock++)
    {
        if(clocks[clock] != 12)
        {
            return false;
        }
    }
    return true;
}

void push(vector<int>& clocks, int swtch)   //vector는 상당히 큰 메모리 공간을 가질 수 있기 때문에 복사본으로 전달하는 것을 피해야 한다.
{
    for (int clock = 0; clock < CLOCKS; clock++)
    {
        if(linked[swtch][clock] == 'x')
        {
            clocks[clock] += 3;
            if(clocks[clock] == 15)
            {
                clocks[clock] = 3;
            }
        }
    }
}

//남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수 반환
//불가능하면 INF 반환
int solve(vector<int>& clocks, int swtch)
{
    //base case: 마지막 스위치에서 clocks가 모두 정렬되어있으면 0 반환
    if(swtch == SWITCHES)
    {
        return areAlinged(clocks) ? 0 : INF;
    }

    int ret = INF;
    for(int cnt = 0; cnt < 4; cnt++)
    {
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }
    return ret;
}

int main(void)
{
    int cases;
    cin >> cases;
    while(cases--)
    {
        vector<int> clocks(16, 0);
        for(int clock = 0; clock<CLOCKS; clock++)
        {
            cin >> clocks[clock];
        }
        int answer = solve(clocks, 0);
        cout<<(answer >= INF ? -1 : answer)<<endl;
    }

    return 0;
}

2
12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12
2
12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6
9

>> 스위치를 누르는 순서는 중요하지 않음 -> 스위치를 몇 번 누를지만 알아내면 된다.

>> 시계는 12시가 지나면 제 자리로 돌아온다는 점을 이용하여, 스위치를 누르는 횟수를 각각 최대 3번으로 제한할 수 있다. 또한, 반복문에서 15 = 12로 설정하면 쉽게 주기함수처럼 이용할 수 있다.

>> 답을 구할 수 없는 경우 굳이 작은 값에 집착하지 않고, 매우 큰 수가 나오면 -1로 반환하면 된다.

>> 스위치가 각각 어떤 시계에 연결되어있는지 나타내는 char 배열을 이용한다. 

 

시간 복잡도 분석

• 스위치를 누르는 최대 횟수가 3회이므로, 스위치를 누르는 경우의 수는 0~3회로 4가지이다.
• 열 개의 스위치가 있으니, 전체 경우의 수는 4^10 = 1048576이다.

 

 

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

모든 순열 만들기

• 순열(permutation): 서로 다른 N개의 원소를 일렬로 줄 세운 것
• 가능한 순열의 수는 $N!$ -> $N$이 10을 넘어가면 시간 안에 모든 순열을 생성하기 어려움
• C++은 STL에 포함된 $next_permutation()$ 함수에서 모든 순열을 순서대로 생성하는 작업을 대신해준다.

 

모든 조합 만들기

• 조합(combina-tion): 서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것

 

$2^n$가지 경우의 수 만들기

• n개의 질문에 대한 답이 yes/no 중 하나일 때, 존재할 수 있는 모든 조합의 수는 $2^n$가지이다.
• 각 조합을 하나의 n비트 정수로 표현한다고 생각하면 1차원 for문 하나로 간단하게 모두 시도할 수 있다. (16장)

 

---

참고자료

• 구종만, < 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 >, 인사이트, 2012.11.01