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

6.1 도입

Brute - Force : 모든 경우를 나열해서 답을 찾는 방법

 

ex) 두 점 사이의 최단 경로

 

1차원 좌표 -7, -3. 1, 9 이 존재 할 때 가장 최단거리를 구해보자

(-7, -3), (-7, 1), (-7, 9), (-3, 1), (-3, 9), (1, 9) 총 6개의 케이스 나온다.

이렇게 모든 케이스를 나열하여서 답을 찾는 것을 완전탐색이라고 함

 

그리고 열명의 학생을 한줄로 세우려고 한다

서로 사이가 안좋은 학생이 존재하고 두 학생은 서로 붙여서 줄 세울수 없다

이 경우 가장 쉬운방법은 모든 학생들 줄 세우는 방법을 구하고 각 경우 사이가 안좋은 붙어 있는지 확인하여 빼주면

조건에 맞게 줄을 세울수 있는 방법을 구할 수 있다

 

6.2 재귀 호출과 완전 탐색

 

재귀호출

재귀함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한조각을 수행하고 나머지는 자기자신을

호출 해 실행하는 함수

 

ex)1~n까지 합을 반환하는 함수를 재귀 형태로 바꾸는 예제

 

반복문 형태

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

 

재귀형태

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

 

재귀호출을 이용하기 위해서는 조각의 하나를 떼어내고 (n) 나머지는 자기 자신을 호출(ReculsiveSum(n-1))을 해야 함

자기자신을 호출하면 1~n-1까지의 조각을 얻을 수 있고 각 조각들이 n을 더해나가면 1~n 합이 나옴

n=1일 때 조각이 하나뿐이니 한 개를 빼면 더 이상 처리할 작업 없음

재귀는 항상 더 이상 쪼개지지 않는 작업에 도달했을때 답을 곧장 반환해야하는 조건을 포함해야 함(기저 사례(base case))

 

ex) 중첩반복문 재귀로 표현하기

 

0번부터 차례대로 매겨진 n개의 원소 중 4개를 고르는 문제

 

반복문 형태

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 << "\n";
        }
     }
  }
}

n개의 원소 중 서로다른 수 4개를 고른다면 위와 같은 코드로 구현 가능

만약 고르고 싶은 개수가 5개면 5중 for문이고 n개라면 n중 for문으로 구현 가능

하지만 재귀함수를 사용한다면 더 간결하게 구현 가능

 

1. 총 원소의 개수(n)

2. 더 골라야 할 원소의 개수(topick)

3. 지금까지 고른 원소의 번호(picked)

 

재귀형태

void pick(int n, vector<int> &picked, int topick)
{
    if(topick==0)
    {
        for(int i=0; i<picked.size(); i++)
        {
            cout << picked[i] << " "; 
        }
        cout << "\n";
        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();
    }
}

여러 for문을 사용할 필요 없이 단 한번의 for문으로 n중 for문을 구현할 수 있다.

 

a~d까지 원소중에 2개만 뽑는다면 재귀 함수의 탐색순서는 위 그림과 같다

우선 빨간색으로가서 a를 뽑고 그다음 (a,b), (a,c), (a,d) 를 뽑은 후 다시 올라간다

그다음 b를 뽑고 (b,c), (b,d) 를 뽑고 c로 가서 (c,d)를 뽑으면 2개를 뽑을 수 있는 모든 경우를 다 탐색하게 된다.

 

예제) 보글게임

 

5*5 격자판에 각각 알파벳이 존재한다

상하좌우 대각선 인접한 칸의 글자를 이어서 단어를 찾는 문제이다

U	R	L	P	M
X	P	R	E	T
G	I	A	E	T
X	T	N	Z	Y
X	O	Q	R	S

문제에서 찾고자 하는 글자가 PRETTY라고 하자

그럼 시작점인 (1,1)에 P가 존재하고 (1, 2), (1,3), (1,4), (2,4), (3,4)의 순서로 탐색 시 PRETTY라는 글자를 찾을 수 있게 된다

이 문제에 대한 해결 방법은 모든 격자에서 시작 위치로부터 8방향을 다 탐색하여 한 조각을 얻고, 자기자신을 호출하여

탐색해나가는 방식으로 하면 정답을 구할 수 있다.

 

문제의 분할

 

1. 각 글자를 하나의 조각으로 만든다

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

    해결할 수 있다

3. 시작 위치에 쓰여진 단어가 첫번째글자와 다르면 false 반환 후 종료

4. 첫글자를 찾으면 인접한 8칸에서 다음 단어를 찾음

5. 이렇게 모든 경우를 탐색하면 정답을 찾음

 

기저 사례 선택

 

더 이상 탐색 없이 간단히 답을 낼 수 있는 경우를 기저 사례로 선택

1. (x, y)에 있는 글자가 원하는 단어의 첫글자가 아닌 경우 항상 실패

2. 원하는 단어가 한 글자인 경우 항상 성공

3. 범위 벗어난 경우에도 실패

 

1, 2번 순서가 바뀌면 안된다 그 이유는 1번이 만족하지 않았을때 2번을 처리해야 되기 때문

 

구현

const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
cosnt int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};

bool hasword(int y, int x, const string &word)
{
   if(!inRange(y,x)) return false;
   if(board[y][x] != word[0]) return false;
   if(word.size()==1) return true;
   
   for(int dir = 0; dir < 8; dir++)
   {
      int ny = y + dy[dir];
      int nx = x + dx[dir];
      if(hasword(ny, nx, word.substr(1)))return true;
   }
   
   return false;
}

 

시간복잡도 분석

 

총 8개의 인접한 영역 탐색

n-1개의 단어 탐색

O(8^n)

 

완전탐색 레시피

 

1. 완전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 정답 수에 비례함(시간 초과시 사용불가, 다른 설계 필요)

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

3. 그 중 하나의 조각을 선택해 답의 일부를 만들고 나머지는 재귀 호출을 해야함

4. 조각이 하나만 남거나 혹은 하나도 남지 않은 경우를 기저 사례로 채택

 

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

ex) 문제 : 주어진 자연수 수열을 정렬하라

      문제 : {16, 7, 9, 1, 31} 을 정렬하라

 

두 문제는 같은 문제같지만 다른 문제임

전자의 경우 특정입력값을 지정하지 않음, 후자의 경우 특정 입력 값을 가짐

재귀호출에서 문제란 항상 수행해야할 작업과 그 작업을 적용할 자료의 조합을 의미

 

에) {1,2,3}을 정렬하는 문제와 {3,2,1}을 정렬하는 문제는 서로 다른 문제이다

후자의 경우만 문제의 정의라고 할 수 있음

 

위에서 본 보글단어의 경우 주어진 칸에서 시작해서 단어를 찾을 수 있는가가 문제 정의임.

1. (y, x)에 첫글자가 있는가?

2.(y-1,x)에 시작해서 단어를 찾을수 있는가

3.인접한 8칸에서 단어를 찾을 수 있는가

 

즉 2번 조건이 총 8개의 조각으로 나눠지고 이것은 원래 문제에서 조각이 된다

조각은 다시말해 원래 문제의 부분문제이다

 

6.3 문제 : 소풍

 

소풍 때 학생들을 두명씩 짝을 지어 행동하게 함

서로 친구인 학생들만 짝을 지어줘야 함

각 학생들의 쌍에 대해 이들의 친구여부 주어질때 학생들을 짝 지을 수 있는 방법 수를 계산

 

짝이 되는 학생이 일부만 달라도 다른방법이다

 

ex) (1, 2), (3, 4), (5, 6)

      (1, 2), (3, 6), (4, 5)

 

6.4 풀이 : 소풍

 

완전탐색

 

가능한 조합의 수를 계산하는 문제를 가장 간단한 방법으로 풀 수 있는것이 완전탐색임

재귀호출을 이용해서 해결하려면 각 답을 만드는 과정을 여러개 조각으로 나누어야 함

전체 문제를 n/2개의 조각으로 나누어 한 조각마다 두 학생을 짝 지어줘야 함

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

 

중복으로 세는 문제

bool areFriend[10][10];

int countPairing(bool taken[10])
{
   bool finished = true;
   for(int i =0; i<n; i++)
   {
       if(!taken[i]) finnished = 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] && areFriend[i][j])
           {
               taken[i] = taken[j] = true;
               ret += countPairing(taken);;
               taken[i] = taken[j] = false;
           }
       }
   }
   
   return ret;
}

위 코드는 2가지 문제점을 가지고 있음

1. 같은 학생 쌍을 2번 짝 짓는다 (0, 1) (1, 0)

2. 다른 순서로 학생을 짝 지어주는 것을 서로 다른경우로 세고 있다 (0, 1)(2, 3), (2, 3)(0, 1)

 

중복으로 세는 상황은 경우의 수 구하는 문제에서 자주 마주친다

 

해결방법 : 항상 특정 형태를 갖는 답만 센다

가장 흔한 방법은 같은 답중 사전 순으로 가장 먼저 오는 답 하나만 세는것이 있음

(2, 3) (0, 1),  (1, 0)(2, 3)은 세지 않고 (0, 1)(2, 3)만 셀린다

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

 

int n;
bool areFriend[10][10];
int countPairing(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 pairwidth = firstfree + 1; pairwidth < n; pairwidth++)
    {
        if(!taken[pairwidth] && areFriend[firstfree][pairwidth])
        {
           ret += countPairing(taken);
           taken[firstfree] = take[pairwidth] = false;
        }
    }
    return ret
}