Algorithm 01. 완전 검색 1

1. baby-gin 게임

0~9사이에서 6장을 뽑고 3장의 카드가 연속숫자일 경우 Run, 3장이 동일한 숫자일 경우 Trplete이라 한다. 만약 6장이 run과 triplete으로만 구성될 수 있으면 baby-gin이라 한다.

 

예시)

667767 -> 666, 777 baby-gin

054060 -> 000. 456 baby-gin

101134 -> baby-gin X

 

6자리 숫자를 입력받아 baby-gin 여부를 판단하는 알고리즘은? 가장 쉬운 방법은 완전검색이다.

 

2. 완전 검색(Brute-force)

 

• 문제의 해를 위해 모든 경우의 수를 나열하는 기법
• 문제를 해결하기 위한 가장 쉬운 접근법
  • 상대적으로 빠른 시간에 문제 해결 알고리즘을 설계할 수 있다.
• 대부분의 문제에 적용가능
• 문제의 자료의 수가 작을 때, 즉, 검색할 모든 경우의 수가 적을 때 유용하다.

3. 리스트에서 특정값 찾기

1) 순차검색

리스트의 모든 원소 비교하기

def sequentialSearch(a, n, key):
    i = 0
    while i< n and a[i] != key:
    	i += 1
    if i < n : return i # 성공
    else : return -1 # 실패

최악의 경우 리스트에 특정값이 존재하지 않는 경우이며, 모든 자료들에 대해 특정값과 비교작업을 수행해야한다. 데이터가 많아질수록 연산횟수도 증가한다.

 

# 완전검색 활용

• 문제의 크기가 커지면 시간 복잡도가 매우 크게 증가
• 수행 속도는 느리지만 해답을찾아내지 못할 확률이 적다.
  • 입력의 크기를 작게해서 빠르게 답을 구하는 알고리즘을 완전검색으로 설계
• 그 후에, 그리디 또는 DP로 효율적인 알고리즘을 찾는다.

# 어려운 문제 해결 방안

1. 완전 검색으로 접근하여 해답 도출

2. 성능 개선을 위해 다른 알고리즘 사용

3. 해답 확인

 

4. 완전검색으로 baby-gin 문제풀기

입력 : 2, 3, 5, 7, 7, 7

2 3 5 7 7 7

2 3 7 5 7 7

2 3 7 7 5 7 

...

7 7 7 5 3 2

모든 경우의 순열을 나열하고, 앞의 세자리와 뒤의 세자리를 잘라서 run, triplete로 baby-gin여부를 판단한다.

 

6개의 숫자 중에서 3개의 숫자를 선택한다. 남은 3개는 그대로 하나의 선택이 된다. 따라서 6개의 숫자 중에서 3개를 선택하는 모든 경우의 수를 생성하고 선택된 숫자들의 순서는 고려하지 않아도 된다. 그러나 단순 순열 생성시 중복된 작업을 수행하게 된다. 

 

완전 검색은 모든 경우의 수를 나열하는 과정에서 중복된 경우의 수를 생성할 수 있다. 이때 중복을 제거할 수 있다면 시간을 단축할 수 있다.