다 해보면 된다냥! 완전탐색

• 다 해보기 전에 경우의 수를 먼저 센다.
• 중첩 반복문으로 모든 짝을 훑는다.
• combinations 와 permutations 를 구분해서 쓴다.
• 재귀로 고른다 / 안 고른다 를 뻗는다.
• 안 될 게 뻔한 갈래는 미리 접는다.

비유로 이해하기 — 자물쇠 열기

네 자리 숫자 자물쇠는 0000 부터 9999 까지 만 번이면 반드시 열린다냥. 손으로도 할 만하다냥.

그런데 여덟 자리면 1억 번이라냥. 방법은 똑같이 맞는데 평생 걸린다냥.

완전탐색은 항상 맞는 방법이라냥. 문제는 맞고 틀리고가 아니라 끝나느냐라냥.

n! 은 정말 갑자기 커진다냥. 오늘 5번 문제로 직접 재본 숫자라냥.

• 8! 은 4만쯤 — 눈 깜짝할 새라냥
• 10! 은 360만쯤 — 몇 초 걸린다냥
• 11! 은 4000만쯤 — 파이썬으로 47초나 걸린다냥
• 12! 은 4억 8천만 — 재볼 엄두도 안 난다냥

10 에서 11 로 딱 하나 늘었을 뿐인데 시간은 열 배가 된다냥. 그래서 먼저 세는 습관이 중요한 거라냥.

세어봤는데 너무 크면 어떡하냥? 두 가지 길이 있다냥.

1. 가지치기 — 다 해보되 안 될 갈래는 접는다냥 (오늘 5단계라냥)
2. 더 좋은 방법 찾기 — 정렬이나 딕셔너리로 확 줄인다냥 (4장, 5장이라냥)

그런데 세어봤더니 감당되면 그냥 다 해보면 된다냥. 괜히 어려운 방법을 찾을 필요가 없다냥. 이게 오늘의 가장 중요한 이야기라냥.

안쪽 반복문이 i + 1 에서 시작하는 게 핵심이라냥.

j 를 0 부터 돌리면 두 가지가 망가진다냥.

• i 와 j 가 같아져서 같은 것을 두 번 고른다냥
• (1, 2) 와 (2, 1) 을 둘 다 세서 개수가 두 배가 된다냥

고르는 문제에서 1 번과 2 번을 고른 것과 2 번과 1 번을 고른 건 같은 거라냥. 그래서 뒤쪽만 보게 만드는 거라냥.

최댓값을 구할 때 시작값을 조심하자냥.

위에서 best 를 -1 로 시작한 건 이유가 있다냥. 하나도 못 고르는 경우를 구분해야 하기 때문이라냥. 0 으로 시작하면 "못 골랐다"와 "합이 0이다"가 똑같아 보인다냥.

오늘 1번 문제의 숨겨진 테스트가 정확히 그걸 잡는다냥.

문제를 읽고 셋 중 무엇인지부터 정하자냥. 여기서 갈리면 뒤는 다 틀린다냥.

구분하는 방법은 딱 하나라냥 — 순서를 바꾸면 다른 답이냥?

• 반에서 대표 2명 뽑기 → 순서 상관없다냥 → combinations
• 1등과 2등 정하기 → 순서가 다르면 다르다냥 → permutations

오늘 2번과 3번 문제가 일부러 나란히 붙어 있다냥. 입력이 똑같이 생겼는데 이거 하나로 답이 갈린다냥.

입력이 정렬되어 있으면 결과도 사전순으로 나온다냥.

반대로 말하면, 입력이 뒤죽박죽인데 사전순으로 출력하라고 하면 먼저 정렬해야 한다냥.

nums = sorted(nums)      # 빼먹으면 순서가 엉킨다냥
for c in combinations(nums, k):
    print(*c)

오늘 2번 문제의 입력이 일부러 정렬되어 있지 않다냥.

7장에서 만든 그 코드라냥

def go(cur):
    if len(cur) == n:
        print(cur)
        return
    go(cur + "0")
    go(cur + "1")

길이 n 인 이진 문자열을 전부 만드는 코드였다냥. 그런데 이게 뭐였냐면 — 각 자리마다 0 이냐 1 이냐를 모든 경우로 뻗은 것이라냥.

0 을 "안 고른다", 1 을 "고른다" 로 읽으면 그대로 모든 부분집합이 된다냥. 새로 배우는 게 아니라 이름만 바뀐 거라냥.

리스트에 담아가며 풀 거면 넣었으면 반드시 빼야 한다냥.

picked.append(nums[i])
go(i + 1)
picked.pop()          # 이 줄을 빼먹으면 전부 틀린다냥

리스트는 하나를 계속 돌려 쓰는 것이라, 되돌리지 않으면 다음 갈래가 앞 갈래의 흔적을 그대로 물려받는다냥.

위에 쓴 것처럼 total + nums[i] 로 값을 넘기는 방식이면 이 걱정이 아예 없다냥. 처음에는 이 쪽이 안전하다냥.

비유로 이해하기 — 미로에서 벽을 만났을 때

미로를 걷다가 벽에 막혔다냥. 그럼 거기서 돌아 나오지, 벽 너머로 갈 수 있는 길을 계속 상상하지는 않는다냥.

그런데 "모든 경우를 만들고 나서 검사하기"는 그 상상을 다 하는 거라냥. 이미 어긋난 상태에서 뒤를 전부 만들어보고, 다 만든 다음에야 버린다냥.

만드는 도중에 검사하고, 어긋나면 그 자리에서 돌아 나오는 것 — 이게 가지치기라냥.

count 같은 바깥 변수를 건드리는 대신 찾은 개수를 돌려주는 방식이라냥. 이러면 global 을 쓸 일이 없어서 실수가 줄어든다냥.

왜 이렇게 많이 줄어드냥?

첫 줄과 둘째 줄만 놓고 이미 어긋났다고 해보자냥. 그럼 나머지 아홉 줄을 어떻게 놓든 전부 틀린 답이라냥.

다 만들고 검사하는 방법은 그 아홉 줄을 끝까지 다 만들어본다냥. 가지치기는 그 자리에서 접는다냥. 버려지는 갈래 하나를 접을 때마다 그 아래 전부가 통째로 사라진다냥.

갈래를 되돌아 나올 때 표시해둔 것도 같이 되돌려야 한다냥.

used[v] = True
go(i + 1)
used[v] = False      # 되돌아 나왔으니 표시도 풀어준다냥

4단계의 pop() 과 똑같은 이야기라냥. 들어갈 때 한 일은 나올 때 되돌린다 — 이것만 기억하면 된다냥.