[알고리즘] [6] 완전탐색, 순열

1. Baby-gin Game

• 0 ~ 9 사이의 숫자 카드에서 임의로 6장을 뽑았을 때 3장의 카드가 연속 번호를 가지는 run과 3장의 카드가 동일한 번호를 가지는 triplet으로만 구성되는 경우를 baby-gin이라고 한다.
• 6자리 숫자를 입력받았을 때 baby-gin 여부를 판단하는 프로그램을 작성한다.
• (1, 2, 3, 1, 2, 3) 정렬하여 확인하는 등 탐욕 알고리즘적인 접근은 해답을 찾지 못할 수도 있다.

2. 완전 검색 (Exhaustive Search)

• 모든 경우의 수를 나열하고 확인하는 기법
• Brute force 혹은 generate-and-test 기법이라고 부른다.
• 상대적으로 빠른 시간에 알고리즘 설계가 가능하며 경우의 수가 작은 경우 유용하다.
• 수행 속도는 느리지만 해답을 찾아내지 못할 확률은 적다.
• 순열, 조합, 부분집합과 같은 조합 문제와 관련이 있다.

3. 순열과 조합

• 순서에 의미가 있다면 순열, 없다면 조합이다.

순열 (Permutation)

• 서로 다른 n개 중 r개를 택하여 한 줄로 나열하는 것 : nPr
• TSP (Traveling Salesman Problem) : 회사에서 출발하여 모든 고객의 집을 방문하며 집까지 도착하는 최선의 시간
  >> 가능한 모든 순서로 방문을 시도한다.
• N개의 요소들에 대해 n!의 순열이 존재하므로 시간 복잡도가 폭발적으로 증가한다.
• 순열을 구현하는 방법 : 반복문, 재귀
• nPr 을 반복문으로 구현하는 경우, n의 값은 반복문의 개수와 무관하다.
• 재귀로 구현할 경우, 더 이상 뽑을 자리가 없는 경우를 기저 조건으로 하여 구현한다.

// {1, 2, 3} 모든 순열 생성

perm(cmt)
	if cnt == 3:
    	순열 생성 완료
	else:
        for i from 1 to 3:
            if visit[i] == true continue;

            numbers[cnt] = i
            visit[i] = true
            perm(cnt + 1)
            visit[i] = false