개요
오늘 배운 완전탐색과 부분집합, 그중에서도 부분집합을 만드는 세 가지 방법( 반복문·재귀·바이너리 카운팅 )과 가지치기, 그리고 비트 연산까지 적은 기록이다.
앞서 풀던 SWEA 2115. 벌꿀 채취가 정확히 이 부분집합 문제였다. 일꾼이 맡은 M칸 중 어느 칸을 채취할지 고르는 부분이 부분집합 열거인데, 거기서 막혀 있었다.
진행 방식은 강사 역할의 AI가 먼저 질문하고 내가 답한 뒤 피드백을 받는 식이었다. 틀린 답도 같이 적어둔다. 맞은 것만 남기면 왜 그쪽으로 갔는지가 사라진다.
같은 문제를 C++로 짜면서 임시 객체에 막힌 이야기는 C++ - < 2 >에 따로 적었다.
탑을 쌓자 — 그리디가 최적인 이유
문제. 무게가 제각각인 화물 N개를 탑 K개에 나눠 쌓는다. 화물 하나를 올리는 비용은 그 화물의 무게 × 그 화물이 놓인 층 번호다. 층 번호는 탑마다 1층부터 새로 센다. 전체 비용의 합을 최소로 만들어라.
정해야 할 게 두 가지다. 어느 화물을 어느 탑에 넣을지, 그리고 그 탑 안에서 몇 번째로 올릴지. 경우의 수가 금방 커지는데 이 문제는 정렬 한 번으로 끝난다. 그게 왜 되는지가 이번 질문이었다.
내 답은 이랬다.
무거운 화물과 층의 높이가 곱 연산을 하기 때문에, 무조건 무거운 게 저층으로 가야 최솟값을 도출할 수 있다.
방향은 맞았지만 “그럼 탑을 하나씩 채우면 안 되나?”라는 되물음이 왔을 때가 더 명확했다! 탑1을 끝까지 채우고 탑2로 넘어가면 안 되는 이유를 이렇게 답했다.
무거운 화물이 옆에 저층이 비어있음에도 고층으로 들어가 최소비용을 충족하지 못한다.
층 번호는 탑마다 따로 매겨지니, 탑을 하나씩 채우는 순간 무거운 화물을 놓을 곳이 탑1의 5층과 탑2의 1층이 동시에 후보로 남아 있는데도 5층을 먼저 쓰게 된다..
먼저 채워야 할 건 탑이 아니라 층 번호가 낮은 자리 전체다.
교환 논증으로 쓰면 이렇다. 무게가 a > b인 두 화물이 층 i < j에 있을 때, 둘을 바꾸면 비용 차이는
$$ (a \cdot j + b \cdot i) - (a \cdot i + b \cdot j) = (a - b)(j - i) \gt 0 $$
항상 양수다. 즉 무거운 쪽이 위층에 있는 배치는 언제나 바꿔서 더 싸게 만들 수 있다. 바꿀 게 없을 때까지 밀면 무게 내림차순 = 층 번호 오름차순이 남는다. ( 재배열 부등식 )
그래서 코드는 정렬 한 번으로 끝난다. 탑 개수는 층 번호를 만들 때만 쓰인다.
def min_cost(weights, K): # K = 탑 개수
weights.sort(reverse=True) # 무거운 화물부터
floors = [(i // K) + 1 for i in range(len(weights))] # 자리별 층 번호, 만들면 이미 오름차순
total = 0
for w, f in zip(weights, floors): # 무거운 화물 <-> 낮은 층 번호 짝짓기
total += w * f
return total
탑 2개에 화물 5개면 floors가 [1, 1, 2, 2, 3]이다. 1층 자리가 둘, 2층 자리가 둘, 마지막 하나가 3층. 여기에 무게를 내림차순으로 붙여 계산하니 22가 나왔다.
그리디가 “왜 되는지”를 묻는 건 대개 바꿔도 더 나빠지지 않는가를 묻는 것이다!
1234. 비밀번호 — 자료구조를 바꾸면 복잡도가 바뀐다
문제. 숫자로만 이루어진 긴 문자열이 주어진다. 같은 숫자가 연달아 두 개 나오면 그 둘을 지운다. 지우고 나면 양옆이 새로 붙는데, 붙은 둘이 또 같으면 그것도 지운다. 더 지울 게 없을 때까지 반복하고 남은 문자열을 출력한다.
핵심은 지운 뒤 양옆이 붙는다는 조건이다. 한 번 지우는 게 새 쌍을 만들어내니 한 바퀴 훑고 끝나지 않는다.
가장 곧이곧대로 짜면 이런 모양이 된다.
def solve_naive(s):
while True:
for i in range(len(s) - 1): # 쌍 찾기, 최악 O(N)
if s[i] == s[i + 1]:
s = s[:i] + s[i + 2:] # 문자열 재구성, 통째로 다시 만드니 O(N)
break
else: # 한 바퀴 돌았는데 지울 쌍이 없으면 끝
break
return s
복잡도를 먼저 물어봐서 O(N!) 이라고 답했는데 틀렸다. 순열을 만드는 게 아니니 팩토리얼이 나올 자리가 없다. 위 코드를 그대로 세면 쌍 찾기 O(N) × 재구성 O(N) × 최대 N/2회 = O(N²) 가 상한이다. 쌍 하나 지울 때마다 문자열을 통째로 다시 만드는 게 비싸다.
그다음 질문이 “더 빠르게 할 자료구조가 있을까”였고, 여기는 바로 보였다.
Stack으로 사용하면 입력받는 과정에서 가장 최근 입력과 비교해서 바로 지울 수 있다. top() 이후 비교해서 pop() 사용 가능
def solve(s):
stack = []
for ch in s:
if stack and stack[-1] == ch: # 스택 맨 위 = 바로 앞 문자
stack.pop() # 짝이 맞으면 지운다, pop 하면 새 맨 위가 저절로 드러난다
else:
stack.append(ch)
return ''.join(stack) # 남은 게 그대로 정답 순서
스택을 쓰면 “지운 뒤 양옆이 붙는다”가 공짜로 따라온다. pop을 하면 새 맨 위가 저절로 드러나고, 그게 곧 “앞에 붙은 문자”니까. 재구성을 따로 할 필요가 없다.
각 문자는 최대 한 번 push되고 최대 한 번 pop되므로 amortized O(N) 이다.
1238099084 -> 1234
4100112380990844 -> 4123
두 번째가 지운 자리가 연쇄로 이어지는 경우다. 99를 지우니 0끼리 붙고, 그걸 지우니 8끼리 붙고, 또 지우니 4와 4가 만난다.
복잡도를 줄인 게 알고리즘이 아니라 자료구조 선택이었다!
완전탐색과 부분집합
완전탐색은 가능한 경우를 하나도 빼놓지 않고 전부 만들어 보고 그중에서 답을 고르는 방법이다. 답이 틀릴 일이 없는 대신 경우의 수만큼 시간이 든다.
무엇을 고르라는 문제냐에 따라 만드는 모양이 갈린다. 순서가 중요하면 순열, 개수가 정해져 있으면 조합, “각 원소를 넣을지 말지” 면 부분집합이다. 2115에서 필요한 게 이 마지막 모양이었다. M칸 중 어느 칸을 채취할지는 순서도 개수도 정해져 있지 않고, 칸마다 넣고 빼는 결정만 있다.
개수부터
원소가 N개인 집합의 부분집합은 2^N개다. 각 원소마다 “넣는다 / 안 넣는다” 두 가지를 독립으로 정하기 때문이다. 공집합과 자기 자신도 포함한 수다.
이 지수가 곧 완전탐색의 한계선이다. N이 20이면 약 100만, 25면 3,300만, 30이면 10억이다. N이 25쯤 되면 시간 초과가 난다.
반복문으로는 왜 안 되나
구현 세 가지 중 반복문(for 중첩) 은 못 쓴다고 답했다. 결론은 맞았는데 이유는 빗나갔다.
각 요소별 존재 여부를 분기하는 순서를 정하는 게 어렵다
순서가 어려운 게 아니다. 진짜 이유는 for문 개수가 코드를 쓰는 시점에 고정된다는 것이다. 원소 3개면 for 3중첩, 4개면 4중첩. N이 입력으로 들어오는 순간 쓸 수가 없다. 중첩 깊이가 실행 시점에 정해져야 하는데 소스 코드에는 그걸 적을 방법이 없다.
나머지 두 방법은 이 고정을 각각 다르게 푼다.
| 방법 | 중첩을 무엇으로 대신하나 |
|---|---|
| 재귀 | 호출 스택이 중첩을 대신한다. 깊이가 런타임에 정해진다 |
| 바이너리 카운팅 | 중첩을 정수 하나로 평탄화한다. 비트가 곧 선택 여부다 |
재귀
def subsets(arr):
n = len(arr)
result = []
chosen = [False] * n # chosen[i] = i번 원소를 골랐는지
def go(idx): # idx = 지금 넣을지 말지 정할 원소의 인덱스
if idx == n: # 끝까지 정했으면 결과에 담는다
result.append([arr[i] for i in range(n) if chosen[i]])
return
chosen[idx] = False # 안 고르는 쪽 먼저
go(idx + 1)
chosen[idx] = True # 고르는 쪽
go(idx + 1)
go(0)
return result
여기서 False와 True의 순서를 바꾸면 출력이 어떻게 바뀌냐는 질문을 받았다. 나는 “그 요소가 없는 경우부터 출력된다”고 답했는데 정반대였다.
False 먼저 (위 코드)
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
True 먼저
[[1, 2, 3], [1, 2], [1, 3], [1], ...]
먼저 내려가는 가지가 먼저 바닥에 닿으니, 먼저 쓴 쪽이 먼저 출력된다. False를 먼저 쓴 지금 코드가 공집합부터 뱉는 거고, 순서를 바꾸면 전체 집합부터 나온다. 내가 말한 “없는 경우부터”는 지금 코드의 동작이지 순서를 바꾼 뒤의 동작이 아니다.
직접 돌려보기 전엔 트리를 머릿속에서 거꾸로 그리고 있었다..
바이너리 카운팅
def subsets_bit(arr):
n = len(arr)
result = []
for mask in range(1 << n): # 0 ~ 2^n - 1, 정수 하나가 조합 하나
subset = []
for j in range(n):
if mask & (1 << j): # j번 비트가 켜져 있으면 j번 원소를 고른 것
subset.append(arr[j])
result.append(subset)
return result
mask를 0부터 2^n − 1까지 세면서 켜진 비트만 골라 담는다. 상태가 정수 하나뿐이라 코드가 짧고 재귀 깊이 걱정도 없다.
대신 중간 상태가 없다. mask 하나가 곧 완성된 하나의 조합이라, “여기까지 고른 합이 벌써 한계를 넘었으니 그만”이라고 말할 자리가 없다. 이 차이가 뒤에서 그대로 걸린다.
합이 10인 부분집합 — 코드 전에 손으로 세기
문제. {1, 2, 3, ..., 10}의 부분집합 중 원소의 합이 10인 것을 모두 출력하라. 부분집합이 1,024개뿐이니 전부 만들어 보면 끝난다.
그런데 코드를 짜기 전에 먼저 손으로 세어보라고 했다. 답을 알아야 코드가 틀렸을 때 알아챌 수 있고, 세다 보면 어디서 더 안 가봐도 되는지가 보인다. 그게 뒤에 나오는 가지치기다.
내 답은 이랬다.
10 / 9+1 / 8+2 / 7+3 / 6+4 / 5+5 (6개) 정도가 기본이고, 그 안에서 약수들을 이용해 더 만들면 (2+3+5 / 1+4+5 / 1+7+2 / 1+6+3 / 1+2+3+4) (5개) 정도 아닐까?
11개로 셌다. 실제로는 10개다.
틀린 건 딱 하나, 5+5 였다. 집합이니 5를 두 번 쓸 수 없다. 나머지 열 개는 전부 맞았다. 세 개짜리·네 개짜리를 빠짐없이 찾아낸 건 좋았는데 정작 제일 단순한 조건을 놓쳤다..
가장 큰 원소를 기준으로 묶어 세니 빠지는 게 없었다.
| 최대 원소 | 조합 | 개수 |
|---|---|---|
| 10 | 10 | 1 |
| 9 | 9+1 | 1 |
| 8 | 8+2 | 1 |
| 7 | 7+3, 7+2+1 | 2 |
| 6 | 6+4, 6+3+1 | 2 |
| 5 | 5+4+1, 5+3+2 | 2 |
| 4 | 4+3+2+1 | 1 |
| 3 이하 | 다 더해도 6 | 0 |
마지막 줄이 가지치기의 출발점이다. 최대 원소가 3 이하면 아무리 다 더해도 6이라 10을 만들 수 없다. 탐색 중간에도 “여기서 더 가봐야 소용없다”를 말할 수 있다는 얘기다.
먼저 바이너리 카운팅으로
arr = list(range(1, 10 + 1)) # 원소의 범위 1 ~ 10
subsets = []
for mask in range(1 << len(arr)): # 2의 (원소 수)제곱만큼 반복
subset = []
sum_of_subset = 0
for j in range(len(arr)):
if mask & (1 << j): # 현재 10진수를 자릿수로 치환하여 비트 연산자로 존재 시 추가
sum_of_subset += arr[j]
subset.append(arr[j])
if sum_of_subset == 10: # 원하는 합을 만족할 때만 subsets 에 추가
subsets.append(subset)
print(len(subsets), subsets) # 10
1,024번을 빠짐없이 돈다. 답 10개를 찾자고 1,024번을 도는데, 합이 이미 10을 넘은 조합도 끝까지 다 더해보고 나서야 버린다.
재귀로 바꾸면 끊을 수 있다
def count_sum(target=10, n=10):
calls = 0 # 재귀 호출 수를 세서 비교해보려고 둔 변수
# idx = 지금 넣을지 말지 정할 숫자 (1부터 n까지)
# total = 여기까지 넣기로 한 숫자들의 합
def go(idx, total):
nonlocal calls
calls += 1
if total > target: # 이미 넘었으면 아래는 볼 필요가 없다
return 0
if idx > n: # n까지 다 정했으면 채점
return 1 if total == target else 0
return go(idx + 1, total + idx) + go(idx + 1, total) # 넣는다 / 안 넣는다
found = go(1, 0)
return found, calls
total > target에서 return하는 줄 하나가 차이를 만든다.
| 재귀 호출 수 | |
|---|---|
| 가지치기 없음 | 2,047 |
total > 10에서 중단 |
415 |
2,047은 원소 10개짜리 이진 트리의 노드 수( 2^11 − 1 )다. 답 10개를 찾는 데 2,047번 도는 대신 415번으로 줄었다.
여기 조건이 하나 붙는다. 원소가 전부 양수라서 이게 성립한다. 지금 합이 이미 10을 넘었으면 앞으로 더할수록 커지기만 하니 아래를 볼 이유가 없다. 음수가 섞여 있으면 아래에서 다시 내려올 수 있어서 같은 가지치기가 틀린 답을 낸다.
2817. 부분 수열의 합 — 원소 개수까지 제한이 붙으면
문제. {1, 2, ..., 12} 중에서 원소를 정확히 N개 골라 합이 K가 되는 경우가 몇 가지인지 센다.
앞 문제에 조건이 하나 늘었다. 합만 보는 게 아니라 고른 개수도 맞아야 한다. 바이너리 카운팅에서 “고른 개수”는 곧 mask에 켜진 비트 개수다.
# import sys
# sys.stdin = open('sample_input (3).txt', 'r')
T = int(input())
def count_bits(n):
count = 0
while n > 0:
n &= (n - 1) # 가장 오른쪽에 있는 1을 제거, 브라이언 커니핸(Brian Kernighan)의 알고리즘
count += 1
return count
for test_case in range(1, T + 1):
N, K = map(int, input().split()) # N = 부분 집합 원소 수, K = 원하는 원소의 합
arr = range(1, 12 + 1)
subsets = []
# 원소의 범위 1 ~ 12
for i in range(1 << len(arr)): # 2의 (원소 수)제곱만큼 반복
if count_bits(i) != N: continue # 집합의 원소 수 가 N개일 때만 진행
subset = []
sum_of_subset = 0
for j in range(len(arr)):
if i & (1 << j): # 현재 10 진수를 자릿수로 치환하여 비트 연산자로 존재 시 추가
sum_of_subset += arr[j]
subset.append(arr[j])
if sum_of_subset == K: # 원하는 합을 만족할 때만 subsets 에 추가
subsets.append(subset)
print(f'#{test_case} {len(subsets)}')
여기서 재밌는 건 count_bits다. 비트를 하나씩 오른쪽으로 밀며 세는 대신 n &= n - 1 을 쓴다.
n - 1은 가장 오른쪽 1을 0으로 바꾸고 그보다 오른쪽을 전부 1로 만든다. 여기에 &를 걸면 그 오른쪽 1들이 전부 지워지면서, 가장 오른쪽 1 하나만 사라진다.
n = 0b10110100
n - 1 = 0b10110011 <- 맨 오른쪽 1(4의 자리)이 0이 되고 아래가 1로 채워진다
n & .. = 0b10110000 <- 그 1 하나만 지워졌다
그래서 반복 횟수가 비트 폭(12번)이 아니라 켜진 비트 개수만큼이다. N개짜리 조합만 찾으면 되는 이 문제에선 딱 N번 돌고 끝난다.
파이썬이라면
bin(i).count('1')이나i.bit_count()( 3.10+ )로도 된다. 직접 써본 건 비트가 어떻게 지워지는지 보려고였다.
2115. 벌꿀 채취 — 결정이 두 겹으로 쌓인 문제
문제. N×N 격자의 각 칸에 꿀이 든 벌통이 하나씩 있다. 일꾼 두 명을 보내는데, 각 일꾼은 한 행에서 가로로 붙어 있는 M칸을 통째로 맡는다. 두 일꾼이 맡은 칸은 한 칸도 겹치면 안 된다.
맡은 M칸을 전부 채취하는 건 아니다. 일꾼은 통을 C만큼밖에 못 들고 간다. 그래서 M칸 중에서 꿀 양의 합이 C 이하가 되도록 골라 채취한다. 수익은 채취한 칸의 제곱합이다. 6, 5, 5를 채취했다면 수익은 36 + 25 + 25다.
두 일꾼 수익의 합이 최대가 되게 하라는 게 문제다.
결정이 두 겹으로 쌓여 있다.
| 결정 | 무엇을 정하나 | 제약 |
|---|---|---|
| 바깥 | 두 일꾼의 구간을 어디에 놓을까 | 서로 겹치지 않게 |
| 안쪽 | 그 M칸 중 어느 칸을 채취할까 | 꿀 양의 합이 C 이하 |
안쪽부터 푸는 게 순서다. “M칸이 주어졌을 때 최대 수익”이 정해져야 바깥에서 구간을 비교할 수 있다.
첫 시도 — 그리디
그 안쪽 결정을 나는 이렇게 접근했다.
M칸 내 숫자들을 전부 제곱하여 더한 뒤, 작은 수로 정렬해서 C 제곱보다 낮아질 때까지 제곱 수를 빼기
두 군데가 틀렸다.
먼저 C는 꿀 양의 합에 걸리는 제한이지 제곱합에 걸리는 게 아니다. C와 비교할 값은 제곱하기 전의 합이다.
더 중요한 건 작은 수부터 빼는 게 최적이 아니라는 것이다. 반례를 받았다.
cells = [6, 5, 5], C = 10
작은 수부터 빼기 : 6+5+5 = 16 > 10
5 빼고 6+5 = 11 > 10
5 빼고 6 = 6 <= 10 -> 수익 36
최적 : [5, 5] 합 10 <= 10 -> 수익 50
큰 값 하나를 지키려다 그보다 더 큰 조합을 통째로 날린다. 제곱합은 합이 같으면 한쪽에 몰린 쪽이 크니 큰 수가 유리한 건 맞는데, 그게 “큰 수를 무조건 남겨라”가 되지는 않는다. 6을 버려야 5 두 개가 들어온다.
골라낼 규칙이 없으니 M칸의 모든 부분집합을 다 봐야 한다. 앞에서 정리한 그 부분집합이다. M이 작아서( 보통 5 이하 ) 2^M은 감당된다.
뼈대를 채우다 — 누적합을 제곱했다
mask를 도는 바깥 반복문과 비트를 확인하는 안쪽 반복문까지는 주어졌고, “이 칸을 고르기로 했을 때 무엇을 해야 하는가” 가 TODO로 비어 있었다. 내가 채운 게 아래 주석 밑 네 줄이다.
def best_profit(cells, C):
best = 0
for mask in range(1 << len(cells)):
profit = 0 # 고른 칸들의 꿀 양 합
total = 0 # 고른 칸들의 수익 합
for j in range(len(cells)):
if mask & (1 << j):
# ↓ 여기가 TODO였다
if profit + cells[j] > C : break
profit += cells[j]
total += profit ** 2 # 문제의 줄
best = max(best, total)
return best
[6, 5, 5], C = 10으로 돌리니 125가 나왔다. 정답은 50이다.
profit은 지금까지 고른 칸들의 합인데 그걸 제곱해서 더하고 있었다. 5를 고른 시점에 profit이 5라 25를 더하고, 5를 더 고른 시점에 profit이 10이라 100을 더한다. 합쳐서 125다. 제곱해야 할 건 누적합이 아니라 방금 고른 칸 하나다.
profit이라는 이름 하나를 “합”과 “수익” 양쪽으로 쓰고 있던 게 컸다. C 제한에 쓰는 합과 제곱해서 쌓는 수익은 서로 다른 값인데, 변수 하나에 얹으니 어느 쪽인지 헷갈렸다. 그래서 고칠 때 이름을 갈랐다.
def best_profit(cells, C):
best = 0
m = len(cells)
for mask in range(1 << m): # M칸의 모든 부분집합
amount = gain = 0 # amount = 꿀 양의 합(C 제한용), gain = 제곱합(수익)
for j in range(m):
if mask & (1 << j): # j번 칸을 채취하기로 한 경우
amount += cells[j]
gain += cells[j] ** 2 # 누적합이 아니라 이 칸 하나를 제곱한다
if amount > C: # 통 용량을 넘으면 이 조합은 버린다
continue
best = max(best, gain)
return best
break도 걸렸었다. break는 결과를 틀리게 하지는 않는다. 앞부분만 고른 조합도 그 자체로 유효하고 뒤쪽 칸을 고르는 경우는 어차피 다른 mask에서 평가되기 때문이다. 다만 읽을 때 “여기서 끊으면 뒤 칸들을 못 보는 거 아닌가” 하고 한 번 멈추게 된다. 의도와 동작이 어긋난 자리라 continue 쪽으로 바꿨다.
두 일꾼 — 같은 행 조건
두 번째 일꾼을 어떻게 붙이냐는 질문에는 솔직히 못 풀었다고 답했다.
아직 2번째를 못 풀어서 현재는 O(M)뿐
같은 행에 있을 때 겹치지 않는 조건은 맞췄다. 시작 열이 c1, c2( c1 < c2 )이면
c1 + M <= c2
c1에서 시작한 일꾼이 c1 + M − 1까지 쓰니, c2는 c1 + M부터여야 한다.
행이 다르면 이 조건이 아예 필요 없다. 그래서 답이 두 갈래로 갈린다. 같은 행인 경우와 다른 행인 경우를 따로 계산하고 큰 쪽을 남기면 된다.
복잡도를 잘못 셌다
두 구간을 어떻게 짝지을지 물었을 때 나는 “O(N²·M²)에서 O(N²·M)이 되겠지”라고 답했는데, 애초에 세는 단위가 틀렸다.
짝짓기 비용은 M이 아니라 구간의 개수로 세야 한다. 시작 위치가 될 수 있는 칸은 행마다 N − M + 1개, 행이 N개니
$$ W = N(N - M + 1) $$
두 구간을 전부 짝지으면 O(W²)이고, M이 상수라면 O(N⁴) 이다. 이걸 아래 방법으로 O(N²)까지 줄인다. 그러면 병목은 짝짓기가 아니라 전처리 O(N² · 2^M · M) 쪽으로 넘어간다.
M이 코드에 상수처럼 보여서 M으로 세고 있었는데, 실제로 늘어나는 건 구간의 개수 쪽이었다.
최종 코드
# import sys
# sys.stdin = open('2115.txt', 'r')
T = int(input())
def best_profit(cells, C):
best = 0
m = len(cells)
for mask in range(1 << m):
amount = gain = 0
for j in range(m):
if mask & (1 << j):
amount += cells[j]
gain += cells[j] ** 2
if amount > C:
continue
best = max(best, gain)
return best
for test_case in range(1, T + 1):
N, M, C = map(int, input().split()) # N = 벌통 크기, M = 벌통 개수, C = 채취가능 최대 양
board = [list(map(int, input().split())) for _ in range(N)]
starts = [(r, c) for r in range(N) for c in range(N - M + 1)] # 시작 가능한 위치 선정
profit = {(r, c): best_profit(board[r][c:c + M], C) for r, c in starts} # 선정한 위치를 기준으로 최적의 합 저장
answer = 0
row_best = []
for r in range(N):
p = [profit[(r, c)] for c in range(N - M + 1)]
row_best.append(max(p)) # col(열) 기준 제일 높은 값 종합
left = p[:] # p(row(행) 기준 col(열)별 모든 최댓값) 복사
for c in range(1, len(p)): # 같은 row(행) 의 경우 마지막 일꾼 전에 최대 값을 계산하기 편하게 하기
left[c] = max(left[c - 1], p[c]) # 왼쪽부터 순회하며 col(열)별 지금까지 중 최댓값 저장하기
for c2 in range(M, len(p)): # 같은 행의 1번째, 2번째 일꾼들의 최대 합 계산
answer = max(answer, left[c2 - M] + p[c2])
row_best.sort(reverse=True) # 열별 최댓값 기준 정렬
answer = max(answer, row_best[0] + row_best[1])
print(f"#{test_case} {answer}")
전처리 — 구간마다 최대 수익
starts와 profit이 전처리다. 같은 구간을 두 번 계산하지 않으려고 시작 위치 (r, c)마다 best_profit을 한 번씩만 돌려 딕셔너리에 담아둔다.
board[r][c:c + M]이 그 구간이다. 시작은 포함, 끝은 제외인 슬라이싱이라 정확히 M칸이 잘린다.
첫 테스트케이스( N = 4, M = 2, C = 13 )에서 만들어진 표는 이랬다.
37 82 81
81 89 89
25 41 34
68 40 85
행은 4개 그대로인데 시작 열만 N − M + 1 = 3이라 하나 줄어 있다.
다른 행 — 상위 두 개면 끝
row_best가 이걸 한다. 행마다 최댓값을 하나씩 뽑아두고 마지막에 내림차순 정렬해 큰 것 둘을 더하는데, 하나씩만 뽑았으니 둘은 반드시 다른 행이라 겹칠 일이 없다. 조건 검사가 아예 필요 없다.
위 표의 행별 최댓값이 [82, 89, 41, 85]니 상위 둘인 89와 85를 더해 174, 그대로 예시 출력에 적힌 답이다.
같은 행 — prefix max
여기가 left다. 같은 행이면 c1 + M <= c2를 지켜야 하는데, 모든 (c1, c2) 쌍을 다 보면 행마다 O(N²)가 된다. 그런데 c2를 하나 고정해놓고 보면 c1 후보는 0 ~ c2 - M 구간 전체고, 그 구간에서 필요한 건 최댓값 하나뿐이라 왼쪽부터 오는 동안의 최댓값을 미리 쌓아두면 된다.
left = p[:]
for c in range(1, len(p)):
left[c] = max(left[c - 1], p[c]) # left[c] = 0번부터 c번까지 중 최댓값
이렇게 해두면 left[c2 - M]이 곧 “c2와 겹치지 않는 범위 안에서 첫 번째 일꾼이 낼 수 있는 최대” 가 되고, 한 번 훑으면서 갱신하니 행마다 O(N)으로 끝난다.
정말 그런지 작은 값으로 세어봤다. M = 2, p = [10, 50, 20, 30, 40]이면 left = [10, 50, 50, 50, 50]이고
| c2 | left[c2 − 2] | p[c2] | 합 |
|---|---|---|---|
| 2 | 10 | 20 | 30 |
| 3 | 50 | 30 | 80 |
| 4 | 50 | 40 | 90 |
쌍을 6개 전부 세어봐도 최대는 역시 90이었다.
answer = max(answer, ...) 꼴은 best_profit 안의 best = max(best, gain)과 같다. 후보를 하나씩 던지고 제일 큰 것만 남긴다.
가지치기는 어디에 걸리나
마지막으로 완전탐색을 어디서 끊을 수 있냐는 질문을 받았다.
현재 합이 C를 넘어갈 때 가지치기 가능하며, Binary Counting으로 하려면 현재 상태가 있어야 하는데 최종 결과 조합만 존재해서 결국은 다 돌게 된다
여기는 맞췄다. 지금 best_profit은 바이너리 카운팅이라 “현재까지의 합”이 없다. mask 하나가 이미 완성된 조합이고, amount를 다 더하고 나서야 C를 넘었는지 안다. 끊으려면 중간 상태를 들고 있는 재귀여야 한다.
그리고 이게 가능한 건 꿀 양이 전부 1~9, 양수라서다. 앞의 “합이 10인 부분집합”에서와 같은 조건이다.
| 중간 상태 | 가지치기 | |
|---|---|---|
| 바이너리 카운팅 | 없음 ( mask = 완성형 ) | 불가 |
| 재귀 | 있음 ( 호출마다 누적 ) | 가능 |
M이 작으면 2^M이 어차피 작아서 바이너리 카운팅으로 충분하다. 재귀로 바꿔 얻는 건 M이 커졌을 때의 여유다.
[참고] 비트 연산
부분집합을 정수 하나로 표현하는 순간부터 비트 연산이 필요해진다.
~5는 왜 -6인가
~는 모든 비트를 뒤집는다. ~5 == -6이 되는 이유를 이렇게 답했다.
부호를 결정하는 맨 앞자리가 1로 반전되어 -가 되었고, 2의 보수로 음수를 읽기에 -6
C++ 기준으로는 정확한 설명이다. 고정된 폭( 예: 32비트 ) 안에서 맨 앞이 부호 비트고, 2의 보수로 읽으면 -6이다.
그런데 파이썬은 정수에 고정 폭이 없다. 임의 정밀도라 “32번째 자리가 부호”라고 말할 자리 자체가 없다. 파이썬은 부호 비트가 왼쪽으로 무한히 이어진다고 보고, 그래서 결과가 항상 이 공식으로 떨어진다.
$$ \sim x = -x - 1 $$
~5 = -6, ~0 = -1, ~(-1) = 0. 결과값은 C++과 같은데 근거가 다르다. 같은 답이 나온다고 같은 이유는 아니었다!
원하는 자리만 뒤집기
“특정 비트만 반전시키려면?”이라는 질문에 xor(^)와 0을 쓴다고 답했는데 반대였다.
bit ^ 0 # 그대로
bit ^ 1 # 뒤집힌다
xor는 “다르면 1”이다. 0과 xor하면 원래 값이 그대로 나오고, 1과 xor해야 뒤집힌다. 그래서 전체를 뒤집으려면 1로 꽉 찬 마스크가 필요하다.
>>> bin(0b0101 ^ ((1 << 4) - 1))
'0b1010'
(1 << 4) - 1이 0b1111이다. 자릿수를 아는 상태에서 만드는 전체 마스크로 자주 쓰인다. 바로 위 count_bits의 n & (n - 1)과 같은 계열의 요령이다.
1 << j의 한계 — 파이썬에는 없고 C++에는 있는 것
바이너리 카운팅을 C++로 옮길 때 1 << j가 어디까지 되냐고 물어서 이렇게 답했다.
int의 기본 4byte(32bit)에 따라 32를 넘어가면 문제가 생기고, 더 큰 메모리를 갖는 자료형을 쓰면 된다
방향은 맞는데 경계가 틀렸다. 32가 아니라 31부터다. 맨 앞 한 자리가 부호로 쓰이니 값으로 쓸 수 있는 건 31자리뿐이다.
-
1 << 31— int의 부호 비트를 건드린다. 표준 버전마다 규정이 달라서 안 쓰는 게 낫다 -
1 << 32이상 — 시프트 폭이 타입의 비트 수 이상이라 어느 버전에서도 정의되지 않는다
제일 잘 걸리는 함정은 받는 쪽만 크게 만드는 경우다.
long long x = 1 << 40; // 이미 int에서 시프트한 뒤 대입한다
long long y = 1LL << 40; // 이렇게 써야 한다
받는 변수 타입은 계산에 관여하지 않는다. 왼쪽 피연산자 1이 int라서 시프트가 int 안에서 일어난다. C++ - < 1 >에서 double b = 7 / 2;가 3.0이 되던 것과 정확히 같은 함정이다.
파이썬에서는 1 << 40이 그냥 된다. 임의 정밀도라 넘칠 자리가 없다.
다만 실전에서 이 경계에 닿을 일은 드물다. 부분집합 완전탐색은 N이 25쯤에서 이미 시간 초과라, 40비트짜리 마스크를 돌릴 만큼 살아남지 못한다.
다른 언어와 견줘 보면
이번에 파이썬으로 정리하면서 C++과 갈린 지점들이다.
| 개념 | Python | C++ |
|---|---|---|
| 큰 시프트 |
1 << 40 그대로 된다 |
1 << 31부터 위험, 1LL << 40으로 쓴다 |
~x |
부호 비트가 무한히 이어진다고 보고 -x-1
|
고정 폭 2의 보수 |
| 구간 넘기기 | board[r][c:c+M] |
iterator 범위 생성자 또는 포인터+길이 |
| 임시 객체 전달 | 구분이 없다 | non-const 참조엔 못 넘긴다, const 참조는 된다 |
| 좌표 → 값 표 |
dict에 (r, c) 키로 바로 |
map<pair<int,int>,int>보다 2차원 vector
|
| 스택 |
list의 append/pop, 그대로 join
|
std::stack은 순회가 안 돼 std::string이 편하다 |
| 켜진 비트 수 |
i.bit_count() ( 3.10+ ) |
std::popcount ( <bit>, C++20 ) |
| 최댓값 갱신 | max(best, x) |
std::max(best, x) ( <algorithm> ) |
| 내림차순 정렬 | sort(reverse=True) |
sort(..., greater<int>()) |
| 행 최댓값 | max(p) |
*max_element(begin, end) |
특히 걸리는 건 스택 줄이다. 파이썬에서는 list를 스택으로 쓰다가 그대로 ''.join(stack) 하면 답이 나온다. C++의 std::stack은 순회할 방법이 없어서 pop으로 꺼내면 역순이 된다. 남은 내용을 그대로 읽으려면 std::string의 push_back / back / pop_back을 쓰는 게 낫다.
std::stack이 불편한 게 아니라 일부러 접근을 막아놓은 것이다. “위에서만 넣고 뺀다”를 타입으로 못 박은 어댑터라, 편하게 쓰고 싶으면 어댑터를 안 쓰면 된다.
소감
스킬 수정 이후 처음 쓰는 AI 블로그 글인데, 아직도 어색한 부분들이 보여 수정을 꽤나 더 거쳐야할 것 같다..