[Algorithm] 완전 탐색 - 브루트 포스(brute force), 너비 우선 탐색(BFS. Breadth-first search)

브루트 포스(brute force)

brute: 무식한, force: 힘   무식한 힘으로 해석할 수 있다.

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

• 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
• 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
• 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

   * 너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊으므로 그때
     따로 작성하도록 하겠다.

 

문제해결 방법

 ① 주어진 문제를 선형 구조로 구조화한다.

 ② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

 ③ 구성된 해를 정리한다.

 

예제 및 알고리즘

1. 10의 약수의 합을 구하기

10의 약수가 될 수 있는 모든 자연수를 구조화 하자.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 자료를 선형으로 구성하였다.

구조화된 자료가 선형 구조이므로 순차 탐색을 활용하여 첫 번째 원소부터 마지막 원소까지 탐색한다.

탐색하면서 10의 약수가 되는 값만 남겨두고 10의 약수가 될 수 없는 값을 배제한다.

10의 약수는 10을 현재 우너소로 나누어떨어지면 그 원소는 10의 약수이다.

위의 과정을 거치면 집합은 다음과 같이 정리된다.

{1, 2, 5, 10}

마지막으로 탐색결과를 정리하여 최종 해를 구한다.

1 + 2 + 5 + 10 = 18

int sum = 0;
   for(int i = 1; i <= n; i = i + 1)
      if(n % i == 0)
         sum = sum + i;
print sum on the screen;

 

2. 거스름돈을 지불할 수 있는 방법의 수와 최소 동전의 개수 구하기

10원과 50원으로 120원을 지불할 수 있는 모든 방법의 수와 최소 동전의 개수를 구해보자.

주어진 동전의 종류가 2가지이므로 2차원 즉 행렬의 형태로 구조화하여 일반적 방법으로 해결할 수 있다.

행을 50원, 열을 10원으로 생각하고 구조화해보자.

위 행렬에서 행렬(0, 0)은 50원 동전 0개, 10원 동전은 0개를 지불하는 방법으로 생각할 수 있다.

따라서 행렬(1, 7)은 50원 동전 1개, 10원 동전 7개로 120원을 지불하는 방법이 된다.

구조화하고 행렬을 2차원으로 탐색하여 120을 이루는 모든 경우의 수를 조사하여, 구한 값들 중 행의 값 + 열의 값의 합의 최소값을 찾으면 최소 동전의 수가 된다.

위 행렬을 탐색해 보면 120원을 지불할 수 있는 경우의 수는 (0, 12), (1, 7), (2, 2)의 3가지이며, 이들의 사용한 동전의 수는 각 행과 열의 합이다. 따라서 사용한 최소 동전의 수는 이 값들 중 최소값이므로 4이다.

120원을 지불할 수 있는 모든 경우의 수 : 3가지, 최소 지불 동전의 수 : 4개

int change = 120, ways = 0, min = INF;
   for(i = 0; i * 50 <= change; i = i + 1)
      for(j = 0; j * 10 <= change; j = j + 1)
         if( (i * 50) + (j * 10) = change)
            ways = ways + 1;
            if(min > i+j)
               min = i+j;
print ways, min on the screen;

 

너비 우선 탐색(BFS, Breadth-first search)

• 그래프에서 완전탐색 방법 중 하나
• 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향으로 탐색을 진행해 나가는 방식

 

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 한다.
• 해가 존재하지 않는다면 유한(finite) 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한(infinite) 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.