[알고리즘] 2. 완전탐색

1. 완전탐색 특징

1. 장점: 반드시 답을 찾아낸다.
2. 단점: 오래 걸린다.
   ※ trade-off 관계: 자원 ↔ 시간

2. 브루트 포스 Brute-force (무차별 대입)

• ex) 비밀번호 숫자 4자리: 모든 경우의 수를 다 넣는다.
• 가장 확실한 방법으로 많이 쓰임
• 암호학, 수학, PS에서 많이 쓰임
• 보안이 허술하면 해당 방법으로도 뚫린다.

예제

1. N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는?

• 두 수를 뽑아 합한 모든 경우를 구하면 된다.
• 8개의 수에서 두 수를 뽑는 모든 경우의 수는 87 / 21 = 28개
  ※ 하지만 시간제한 1초, 100만개의 수가 주어진다면???

2. N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는?
   (시간 제한: 1초, 입력: 2 <= N <= 1000000)

• 정렬을 이용해야한다.
• 빠른 정렬 알고리즘의 시간복잡도는 대체적으로 O(NlogN)이다.

---

탐색할 때 쓰기 좋은 것들

1. 순열 permutation

from itertools import permutations

v = [0, 1, 2, 3]

for i in permutations(v, 4): # 첫번째는 배열, 두번째는 뽑을 갯수
	print(i)

• 모든 경우의 수를 순서대로 살펴볼 때 용이
• permutations()의 반환값 형태는

2. 조합

from itertools import combinations

v = [0, 1, 2, 3]

for i in combinations(v, 2): # 첫번째는 배열, 두번째는 뽑을 갯수
	print(i)

• 파이썬에서만 기본으로 제공
• combinations()의 반환값의 형태는 튜플