기초 개념
완전탐색
일단 다 해 보면 안 되나
번호는 세 자리입니다. ▲▼로 번호를 맞추고 「열어 보기」를 누르세요. 누를 때마다 1번으로 셉니다. 같은 번호를 또 해 보지 않으려면 어떤 순서가 좋을까요?
0
0
0
열어 본 횟수 0
0번 만에 열었습니다. 운이 좋으면 빨리 열리고, 운이 나쁘면 1,000번째에 열립니다.
순서가 들쭉날쭉하면 번호를 빠뜨리거나 같은 번호를 또 해 봅니다. 순서를 정해 두면 이렇게 됩니다.
000 → 001 → 002 → … → 999번호 하나를 열어 보면 1번. 끝까지 가면 최악 1,000번입니다.
- 한 일 — 될 수 있는 번호를 하나도 빠뜨리지 않고 전부 해 봤다
- 자릿수가 하나 늘면 — 경우가 열 배가 된다
가능한 경우를 빠짐없이 다 해 보는 방법 = 완전탐색
경우의 수10 × 10 × …1,000가지
사람1초에 한 번1,000번17분
컴퓨터1초에 1천만 번1,000번✔ 1초 안
물건 담기도 같은 모양입니다. 물건 개수를 N이라고 두겠습니다. 물건마다 담기와 안 담기, 두 가지라서 경우는 2 × 2 × … = 2^N가지입니다.
경우가 적을 때만 쓸 수 있다
물건 개수가 N이면 경우는 2^N가지입니다. 물건이 하나 늘 때마다 두 배가 됩니다.
물건 30개1,073,741,824가지
물건 20개1,048,576가지
물건 10개1,024가지
- N 이 10 이하 — 순서까지 따지는 N! 가지도 된다(10! = 3,628,800)
- N 이 20 이하 — 담을지 말지 2^N 가지가 된다(20 × 2^20 ≈ 2천만 번)
- N 이 1,000 이하 — 둘씩 짝짓는 이중 반복문 N²이 된다(100만 번)
- N 이 20을 훌쩍 넘으면 — 2^N 은 못 쓴다. 다른 방법을 찾아야 한다
문제가 N 이 작다고 알려 주면 완전탐색을 먼저 떠올립니다.
코드는 모든 경우를 숫자 하나로 센다
물건 3개의 무게는 2, 3, 4, 값은 3, 4, 5. 가방 한도는 5 입니다. 담을지 말지는 8가지이고, 경우마다 번호(mask)를 붙입니다.
| mask | 담은 물건 | 무게 | 값 | 한도 5 안? |
|---|---|---|---|---|
| 0 = 000 | 없음 | · | · | · |
| 1 = 001 | 0 | · | · | · |
| 2 = 010 | 1 | · | · | · |
| 3 = 011 | 0·1 | · | · | · |
| 4 = 100 | 2 | · | · | · |
| 5 = 101 | 0·2 | · | · | · |
| 6 = 110 | 1·2 | · | · | · |
| 7 = 111 | 0·1·2 | · | · | · |
mask— 담을 물건을 0 과 1 로 적은 번호. 오른쪽 자리가 0번 물건이다. 3 = 011 이면 0번·1번을 담는다range(2 ** n)— 경우의 수만큼 반복한다. 물건이 3개라 0 부터 7best— 한도 안의 경우 중 지금까지 가장 좋은 값
다음을 눌러 8가지를 위에서부터 훑어 보세요. 중간에 한 번 물어봅니다.
물건의 무게 (칸 아래 번호가 물건 번호)
20
31
42
| mask | 담은 물건 | 무게 | 값 | 한도 5 안? |
|---|---|---|---|---|
| 0 = 000 | 없음 | · | · | · |
| 1 = 001 | 0 | · | · | · |
| 2 = 010 | 1 | · | · | · |
| 3 = 011 | 0·1 | · | · | · |
| 4 = 100 | 2 | · | · | · |
| 5 = 101 | 0·2 | · | · | · |
| 6 = 110 | 1·2 | · | · | · |
| 7 = 111 | 0·1·2 | · | · | · |
다음을 눌러 한 줄씩 넘겨 보세요
n = 3
best_pack.py
- 1def best_pack(weights, values, limit):
- 2 n = len(weights)
- 3 best = 0
- 4 for mask in range(2 ** n):
- 5 w = sum(weights[i] for i in range(n) if mask >> i & 1)
- 6 v = sum(values[i] for i in range(n) if mask >> i & 1)
- 7 if w <= limit and v > best:
- 8 best = v
- 9 return best
0 / 39
mask 가 5 이면 어떤 물건을 담을까요?
빠뜨리거나 두 번 세면 틀린다
range(2 ** n - 1)— 마지막 경우, 전부 담기를 빠뜨린다- 조합과 순열 — [1, 2, 3] 에서 둘을 고를 때 순서를 안 따지면 3가지(12, 13, 23)이고, 순서까지 따지면 6가지(12, 21, 13, 31, 23, 32)다
- 담을지 말지는 순서가 없다 — 0번·1번 물건과 1번·0번 물건은 같은 경우라서 한 번만 센다. 순서까지 세는 것은 순열 쪽이다
itertools—product는 자리마다 고르기,combinations([1, 2, 3], 2)는 3개,permutations([1, 2, 3], 2)는 6개를 만든다
N 이 20을 훌쩍 넘으면 이 방법은 끝나지 않습니다. 줄이는 방법은 뒤쪽 장에서 봅니다.
문제에서 이 말이 보이면
N 이 작다(20 이하)모든 경우조건을 만족하는 것 중 최선
다음 장에서는 양쪽 끝에서 좁혀 오는 투 포인터를 봅니다.