[알고리즘] 3. 완전 검색과 순열

1. 완전 검색 Exaustive Search

• 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법.
• Brute-force / generate-and test라고도 함.
• 모든 경우의 수를 테스트하고, 최종 해법을 도출하는 방법.
• 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.

*완전 검색의 필요성

(1) 완전 검색으로 시작

• 모든 경우의 수를 생성, 테스트 → 속도는 느리지만 해답을 찾아낼 수 있다.
• 우선 완전 검색으로 접근해 답을 찾고, 다른 알고리즘을 사용해 성능개선하기

2. 순열 Permutation

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 nPr이라고 표현한다.

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

• nPn = n!이라고 표기하며, Factorial이라고 한다.

n! = n * (n-1) * (n-2) * ... * 2 * 1

import itertools

arr = [2,3,5,7,7,7,0,0,0,0]
nPr = list(itertools.permutations(arr,10))
for x in nPr :
	print(x)
print(len(nPr))

• 단순하게 순열을 생성하는 법

1. {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)