[Algorithm] 완전 탐색 (Exaustive Search)

■ 완전 탐색 (Exaustive Search)

고지식한 방법 (Brute-Force)의 의미를 갖고 있음. 

- 모든 경우의 수를 나열한 후 그 중에서 최선의 해결책을 찾는 방법으로 가장 좋은 결과를 확실히 추출할 수 있음
- brute-force는 문제를 해결하기 위한 간단하고 쉬운 접근법

 

[개념]
1. 완전탐색은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
2. brute-force 혹은 generate-and-test 기법이라고도 부름

 

[특징]
1. 모든 경우의 수를 테스트한 후 최종 해법을 도출
2. 문제에 포함된 자료 (요소, 인스턴스)의 크기가 작다면 유용
3. 학술적 또는 교육적 목적을 위해 알고리즘의 효율성을 판단하기 위한 척도로 사용됨
4. brute-force는 대부분의 문제에 적용 가능
5. 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만 해답을 찾아내지 못할 확률이 작음.

[의의]
1. 주어진 문제를 풀 때 우선 완전탐색으로 접근하여 해답을 도출한 후 성능 개선을 위해 다른 알고리즘을 사용하는 것이 바람직함

 

2. 완전 탐색은 입력의 크기를 작게 해서 간편하고 빠르게 답을 구하는 프로그램을 작성함
: 이를 기반으로 그리디 기법이나 동적 프로그래밍을 이용해 효율적인 알고리즘을 찾을 수 있음.

 

[완전 탐색의 예1. Baby-gin Game]

1. 0~9사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때 3장의 카드가 연속적인 번호를 갖는 경우 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우 triplet이라고 함

 

2. 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin이라 함

(입력예)
(1) 667767은 두 개의 triplet이므로 baby-gin임 (666, 777)
(2) 054060은 한개의 run과 한 개의 triplet이므로 baby-gin임 (456, 000)
(3) 101123은 한 개의 triplet이 존재하나 023이 run이 아니므로 baby-gin이 아님 

▼ 완전 탐색을 활용한 baby-gin 접근
1. 고려할 수 있는 모든 경우의 수 생성하기
2. 6개의 숫자로 만들 수 있는 모든 숫자 나열 (중복 포함)
3. 앞, 뒤 3개가 각각 run 혹은 triplet인지 체크한다.

 

* 순열을 어떻게 생성할 것인가?

: 순열(Permutation)은 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것.

(1) 서로 다른 n개 중 r개를 택하는 순열은 이와 같이 표현 : nPr
(2) nPr은 이와 같은 식이 성립됨 : npr = n * (n-1) * (n-2) * .. * (n-r+1)
(3) nPn = n!이라고 표기하며 Factorial 이라 부름 : n! = n * (n-1) * (n-2) * .. * 2 * 1


[단순하게 순열을 생성하는 방법]
(예) {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수:
for(int i1=1; i1<=3; i1++)

{

    for(int i2=1; i2<=3; i2++)
          if(i2 != i1)
          {
               for(int i3=1; i3<=3; i3++)
                         if(i3 != i1 && i3 != i2)
                              print(i1, i2, i3);
          }

}


이후 모든 경우의 순열에 대해 앞의 3자리와 뒤의 3자리를 잘라 run, triplet 여부를 확인하고 최종적으로 baby-gin인지를 판단

 

 

[완전탐색의 예2. 순차 탐색]

자료가 저장된 배열에서 키 값을 찾기 위해 첫 번째 자료부터 비교하면서 진행

(ex)
SequentialSearch(A[0 .. n], k)
    A[n] = k
    i = 0

    while(A[i] != k)
    {
        i++
    }

if(i < n)
    return i; //탐색 성공
else
    return -1; // 탐색 실패

 

 

위와 같이 모든 경우의 수를 확인하는 것이 완전탐색 [Brute-Force]이다. 어떤 경우에는 매우 효율적일 수 있으나 대부분의 문제에 적용하기에는 수행시간이 매우 오래 걸릴 것이다. 그러므로 이를 통해 문제를 해결했다면 다음 단계는 알고리즘을 올바른 설계 기법으로 최적화하는 것이다.