직접 풀어보자! 완전탐색 5문제
안녕, 나 코딩냥이다냥! 오늘 문제는 어려워서 막히는 게 아니라 헷갈려서 막히는 쪽이라냥. 뼈대는 다 짧다냥. 대신 "무엇을 고르는 거냥?"을 잘못 잡으면 처음부터 다시 짜야 한다냥.
완전탐색 문제를 풀 때 순서
- 무엇을 고르는지 정한다 — 몇 개냥? 순서를 따지냥?
- 경우의 수를 센다 — 감당되냥? 안 되면 접을 데가 있냥?
- 그 다음에 코드를 짠다
2번을 건너뛰면 다 짜놓고 시간 초과로 돌아온다냥. 세는 데 30초면 된다냥.
세 장을 골라 합이 m 이하이면서 가장 크게 만든다냥.
best = -1
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
total = cards[i] + cards[j] + cards[k]
if total <= m and total > best:
best = total카드가 100장이어도 16만 번쯤이라 넉넉하다냥. 세어보고 시작하는 습관을 여기서 들이자냥.
j 는 i + 1, k 는 j + 1 부터라냥.
셋 다 range(n) 으로 돌리면 같은 카드를 두 번, 세 번 고른다냥.
카드 한 장을 세 번 골라서 합이 나오면 안 되는 거라냥.
숨겨진 테스트가 이걸 잡는다냥.
best 를 0 으로 시작하면 틀린다냥.
어떻게 골라도 m 을 넘는 경우가 있다냥. 그때 답은 -1 인데, 0 으로
시작해두면 0 이 그대로 나온다냥.
숨겨진 테스트에 카드가 10 10 10 이고 m 이 5 인 경우가 있다냥.
n개 중 k개를 고르는 모든 방법을 사전순으로 출력한다냥.
순서를 안 따지는 문제라냥. 1 2 와 2 1 은 같은 방법이라 하나만
출력한다냥. 그러니 combinations 라냥.
from itertools import combinations
for c in combinations(nums, k):
print(*c)print(*c) 는 튜플을 공백으로 펼쳐서 출력한다냥. print(c) 라고 쓰면
괄호와 쉼표까지 나와서 틀린다냥.
입력을 먼저 정렬해야 한다냥.
주어지는 수의 순서는 정해져 있지 않은데 출력은 사전순이라냥.
combinations 는 들어온 순서를 그대로 따라가기 때문에, 정렬하지 않으면
순서가 엉킨다냥.
nums = sorted(nums)공개된 두 번째 예시가 7 3 9 1 로 들어온다냥. 정렬을 안 하면 거기서 바로
틀리니 꼭 확인해보자냥.
그때는 전부 고르는 방법 하나뿐이라냥. k 가 1 인 경우도 있다냥.
둘 다 combinations 가 알아서 해주니 따로 처리할 건 없다냥. 다만
직접 재귀로 짤 거면 이 두 끝을 확인해보자냥.
1 부터 n 까지 중 m개를 골라 줄 세우는 모든 방법을 출력한다냥.
2번과 나란히 놓고 보자냥. 이게 오늘의 핵심이라냥.
입력이 거의 똑같이 생겼는데, 이번엔 줄 세우기라 순서가 다르면 다른
방법이라냥. 1 2 와 2 1 을 둘 다 출력해야 한다냥.
그러니 combinations 가 아니라 permutations 라냥. 2번 코드를 그대로
가져다 쓰면 출력이 모자라서 틀린다냥.
from itertools import permutations
for p in permutations(range(1, n + 1), m):
print(*p)range(1, n + 1) 은 이미 오름차순이라 결과가 저절로 사전순으로
나온다냥. 2번과 달리 따로 정렬할 게 없다냥.
permutations 없이 짜면 이렇게 된다냥. 5번 문제의 예습이라냥.
def go():
if len(cur) == m:
print(*cur)
return
for v in range(1, n + 1):
if used[v]:
continue
used[v] = True
cur.append(v)
go()
cur.pop() # 나올 때 되돌린다냥
used[v] = False # 이것도 같이 되돌린다냥되돌리는 두 줄을 빼먹으면 결과가 완전히 엉킨다냥. 들어갈 때 한 일은 나올 때 되돌린다냥.
합이 s 가 되는 부분집합이 몇 개인지 센다냥.
고를 개수가 정해져 있지 않다냥. 크기가 1인 것도, 전부 다 고른 것도
센다냥. 그래서 combinations 로는 불편하고 재귀가 딱 맞는다냥.
def go(i, total, picked):
if i == n:
if picked > 0 and total == s:
return 1 # 한 가지 찾았다냥
return 0
# 안 고르는 갈래와 고르는 갈래를 더한다냥
return (go(i + 1, total, picked)
+ go(i + 1, total + nums[i], picked + 1))n 이 18이니 2¹⁸ 로 26만쯤이라냥. 넉넉하다냥.
아무것도 안 고른 경우를 세면 안 된다냥.
갈래를 끝까지 뻗으면 하나도 안 고른 경우도 딸려온다냥. 그 합은 0
이라, 목표가 0 일 때 슬쩍 하나가 더 세진다냥.
위 코드의 picked > 0 이 그걸 막는 거라냥.
숨겨진 테스트에 0 0 0 0 에서 합 0 을 세는 경우가 있다냥. 정답은 15
인데 공집합을 세면 16 이 나온다냥. 큰 테스트도 목표가 0 이라 여기서
또 걸린다냥.
수에 음수가 섞여 있다냥. 그래서 "합이 이미 목표를 넘었으니 그만" 같은 가지치기는 여기서 못 쓴다냥. 뒤에 음수가 나와서 다시 내려올 수 있기 때문이라냥.
26만이면 그냥 다 해봐도 되니 걱정 말자냥.
n × n 판에 퀸 n개를 서로 공격 못 하게 놓는 방법의 수를 센다냥.
모든 순열을 만들어놓고 검사하면 시간 초과라냥.
n 이 11이면 순열이 4000만 개라 47초쯤 걸린다냥. 제한은 5초라냥.
놓는 도중에 검사하고 어긋나면 되돌아오면 0.4초라냥.
이 문제는 가지치기를 반드시 써야 풀린다냥. 오늘 5단계가 이걸 위한 거였다냥.
퀸은 같은 행에 둘이 못 있으니 한 줄에 정확히 하나씩 놓으면 된다냥. 그러면 행은 신경 쓸 필요가 없어진다냥.
col[r] 에 r 번째 줄의 퀸이 몇 번째 칸에 있는지 적어두자냥.
def go(r):
if r == n:
return 1 # n 줄을 다 놓았다냥
total = 0
for c in range(n):
if not can_place(r, c):
continue # 접는다냥
col[r] = c
total += go(r + 1)
return totalr 번째 줄 c 번째 칸에 놓으려 한다냥. 이미 놓인 윗줄들과만
비교하면 된다냥.
def can_place(r, c):
for i in range(r):
if col[i] == c:
return False # 같은 열이라냥
if abs(col[i] - c) == r - i:
return False # 대각선이라냥
return True대각선 조건이 헷갈리면 이렇게 생각하자냥 — 대각선으로 놓였다는 건 가로로 움직인 칸 수와 세로로 움직인 칸 수가 같다는 뜻이라냥.
세로 거리는 r - i, 가로 거리는 abs(col[i] - c) 라냥. 둘이 같으면
대각선이라냥.
col[r] = c 를 되돌리지 않아도 괜찮은 이유가 궁금할 수 있다냥.
can_place 가 r 보다 위쪽만 보기 때문이라냥. col[r] 은 다음에
이 자리에 다른 값을 넣을 때 어차피 덮어써진다냥. 아래쪽에 남아 있는
옛날 값은 아무도 안 본다냥.
헷갈리면 되돌려도 된다냥. 답은 똑같이 나온다냥.
n이 1이면 →1(그냥 하나 놓으면 된다냥)n이 2나 3이면 →0(어떻게 놓아도 안 된다냥)n이 4면 →2n이 8이면 →92(체스판 크기라 유명한 숫자라냥)
4 까지 맞으면 뼈대는 제대로 짠 거라냥. 그 다음은 속도 싸움이라냥.
다섯 개 다 풀었냥? 오늘 배운 "일단 다 해보기"는 앞으로 만날 문제에서 가장 먼저 떠올려야 할 방법이라냥. 똑똑한 풀이가 안 보여도 괜찮다냥 — 세어보고 감당되면 그게 정답이라냥.
그리고 감당이 안 될 때는 오늘 마지막에 배운 가지치기를 떠올리자냥.
다음은 그리디라냥. 오늘과 정반대로, 다 해보지 않고 한 번만 훑어서 답을 내는 방법이라냥. 정말 수고했다냥~