Algorithm 01. 완전검색 2

1. 조합적 문제

완전 검색은 특정 조건을 만족하는 경우나 요소를 찾는 검색 알고리즘이다. 이것은 순열(Permutation), 조합(Combination), 부분집합(Subset)과 같은 조합적 문제(Combinatorial Problems)들과 관련이 많다.

 

다음 이동비용이 가중치와 숙박비로 주어진 그래프에서 출발 도시에서 도착 도시까지 다른 도시들을 한번씩만 방문하여 도착하는 최소비용 경로는 무엇일까?

 

완전검색으로는 어떻게 풀고 완전 검색보다 더 좋은 알고리즘은 무엇일까?

 

2. 순열

서로 다른 n개중 r개를 택하는 순열

 

nPr = n * (n - 1) * (n - 2) * ... * (n - r + 1)

nPn = n!

 

예시) 1, 2, 3, 4 순열 생성

첫번째로 1을 선택하면 나머지 2, 3, 4의 순열

그 다음 2를 선택하면 3, 4의 순열

3을 선택하고 남은 4의 순열

이런식의 트리구조가 된다.

 

대부분의 문제가 다음과 같이 순서화된 요소들의 집합에서 최선의 방법을 찾는 것이다. 

 

> 순회 외판원 문제

방문해야할 도시가 n개라면 가능한 모든 경로는 n!이고, 그 중에서 최선의 경로를 찾으면 된다.

 

3. 문제점

시간 복잡도가 n에 비례해서 폭발적으로 증가한다. 1씩 증가함에 따라 실행시간이 기하급수적으로 증가한다. 따라서 n의 값이 증가되면 순열을 완전검색으로 구해서 해결하는 것은 현실적으로 어렵다

 

4. 해결방안

1, 2, 3을 포함하는 모든 순열

for i1 in range(1, 4): # 첫번째 요소 선택
    for i2 in range(1, 4): # 두번째 요소 선택
        if i2 != i1:
            for i3 in range(1, 4): # 세번째 요소 선택
            	if i3 != i1 and i3 != i2: 
                    print(i1, i2, i3)      

Baby-Gin 문제는 6개의 for loop로 모든 순열을 만들어서 판별할 수 있다. 그러나 너무 오래걸려서 재귀 호출을 이용해 필요한 횟수만큼 반복을 수행하여 순열을 생성한다.

 

5. 순열 생성 방식

• 사전식 순서(Lexicographi-Order)
  • 오름차순에서 내림차순으로 정렬하는 방식
  • 1 2 3 / 1 3 2 / ... / 3 2 1
• 최소 변경을 통한 방법(Minimum-Exchange requirement)
  • 각 순열을 이전 상테에서 딱 두개의 요소를 교환하여 생성한다.
  • 1 2 3 / 3 2 1 / 2 3 1 / 2 1 3 / 3 1 2 / 1 3 2
  • Johnson-Trotter 알고리즘

6. Johnson-Trotter 알고리즘

순열 생성 후 처음 시작상태로 돌아온다.

 

7. 대표적인 순열 생성 방법

N개의 요소가 있을 때 N번의 선택으로 순열 생성

첫번째 요소에 3을 넣을 때는 인덱스0과 2를 교환한다. 즉, 1과 3을 교환하는 것이다. 두 번째 요소를 결정할 때는 첫번째 요소는 빼고 교환이 진행된다.

 

순열이 생성되는 모든 과정을 그리면 트리구조를 가진다.

• 요소의 수는 4개
• 루트는 자식이 4개, 트리의 높이가 1인 내부노드들은 자식이 3개가 되는 구조의 트리가 된다.
• 4번의 선택을 하므로 트리의 높이는 4가된다.
• 트리를 순회하는 것과 같이 재귀호출을 통해서 순열을 생성한다.
• 트리의 단말에 도착하면 하나의 순열 생성

# a[] : 데이터가 저장된 리스트
# n : 원소의 개수
# k : 현재까지 선택된 원소의 수
def perm(n, k):
    if k == n: # 하나의 순열이 생성된 경우
    	print(a) # 해당 순열 출력
    else:
    	for i in range(k, n):
            a[k], a[i] = a[i], a[k] # 교환을 통한 선택
            perm(n, k + 1) # 선택된 원소 수를 1개 증가시키고 재귀호출
            a[k], a[i] = a[i], a[k] # 이전 상태로 복귀

...

8. 순열 라이브러리

1) 순열

import itertools
mylist = [1, 2, 3]
result = itertools.permutations(mylist) # (mylist, 3)과 같다. r을 생략시 기본값이 리스트크기
print(list(result))

안의 순열들이 tuple형식으로 저장되어있다.

2) 중복순열

import itertools
mylist= [1, 2, 3]
result = itertools.product(mylist, repeat=3)
print(list(result))

repeat으로 명시하고 인자값을 주저야한다.

9. 부분집합

• 집합의 포함된 원소들을 선택하는 것
• 원소들의 그룹에서 최적의 부분집합을 찾는 것
• 배낭 짐싸기
  • 배낭과 물건 집합
  • 배낭의 무게 > 배낭의 담는 물건 무게의 총합
  • 이때, 가치의 합이 최대가 되는 물건들을 선택하는 문제
• N개의 원소를 포함한 집합
  • 모든 부분집합은 2^n개 
  • 원소 수 증가시 부분집합의 개수는 지수적으로 증가

> 소스코드

각 부분집합에 포함되는 여부를 1과 0으로 나타내어 표현하기

arr = [2, 3, 4, 5] # 실제 집합
bit = [0] * len(arr)
for i in range(2):
    bit[0] = i # 0번째 원소
    for j in range(2):
    	bit[1] = j # 1번째 원소
        for k in range(2) : 
            bit[2] = k # 2번째 원소
            for l in range(2):
            	bit[3] = l # 3번째 원소
                print([arr[x] for x in range(len(bit)) if bit[x]])) # 생성된 부분집합 출력       

하나의 부분집합 비트는 네 개의 비트로 표현할 수 있는 하나의 양의 정수에 대응한다.

print(bit)를 함께 수행해보았다.

 

10. 비트표현을 이용해서 부분집합 생성

• 바이너리 카운팅을 통한 사전적 순서
  • 부분집합 생성하는 간단한 방법
  • 원소 수에 해당하는 N개의 비트열을 이용
  • i번째 비트값이 1이면 i번째 원소가 포함됨을 의미

예시) A, B, C, D

0000부터, 1111까지의 binary counting을 하고 그 bit pattern에서 1에 해당하는 값은 집합에 포함되는 것을 이용하면 오름차순으로 부분집합을 구할 수 있다.

 

> 소스코드

바이너리 카운팅을 이용한 부분집합 생성코드

arr = [2, 3, 4, 5]
n = len(arr) # n : 원소의 개수

for i in range(1 << n) : # 1 << n = 2^n과 같다. 부분집합의 개수를 의미
    for j in range(n) : # 원소 수만큼 비트를 비교
    	if i & (1 << j): # i의 j번째 비트가 1이면 j번째 원소를 출력 => 왜 이게 이 표현??
        	print(arr[j], end=",")
    print()

List Comprehension이용

arr = [2, 3, 4, 5]
for i in range(1 << len(arr)):
    print([arr[j] for j in range(len(arr)) if i & (1 << j)])

 

11. 조합

서로 다른 n개 중 r개를 순서없이 고르는 것

• C(n, r) = n! / ((n-r)! * r!) ,  n >= r
• C(n, 0) = 1, C(n , n) = 1
• C(n, r) = C(n, n-r)
• C(n, r) = C(n-1, r-1) + C(n-1, r) -> 재귀적 표현

예시) 5C3 = 4C2 + 4C3

다섯개에서 세 개를 선택하는 모든 경우 = 5가 반드시 포함되는 경우 + 5가 반드시 포함되지 않는 경우

• 5가 반드시 포함 -> 5를 제외한 나머지 4개 중 2개 선택
• 5가 반드시 포함되지 않음 -> 5를 제외한 나머지 4개 중 3개 선택

> 소스코드

# an[] : n개의 원소를 가지고 있는 리스트
# tr[] : 조합이 임시 저장될 r개의 크기리스트

def comb(n, r):
    if r == 0: print(tr) # r개의 원소에 대한 선택이 끝난 상태
    elif n < r : return
    else:
    	tr[r-1] = an[n-1]
        comb(n-1, r-1)
        comb(n-1, r)

print(comb(5, 3))

12. 라이브러리를 이용한 조합, 중복조합

import itertools
mylist = [1, 2, 3]
result = itertools.combinations(mylist, r=2) # r 생략불가
print(list(result))

import itertools
mylist = [1, 2, 3]
resutl = itertools.combinations_with_replacement(mylist, r=2) # r 생략불가
print(list(result))