개요
보고서 하나를 팀장이 반으로 쪼개 두 사람에게 맡기고, 그 두 사람이 또 반씩 쪼개 아래로 내려보낸다고 해보자. 맡은 부분이 서로 겹치지 않으면 각자 쓰고 모아 붙이기만 하면 되니 금방 끝난다.
곤란한 건 양쪽 모두에 같은 자료가 필요할 때다. 누가 먼저 조사해서 공유하지 않으면 아래로 내려갈수록 같은 조사를 하는 사람이 두 배씩 늘어난다. 앞 단계에서 “자료는 정리해서 넘겼다”고 했는데 정리되지 않은 채로 넘어와서, 그 말만 믿고 한 작업이 통째로 틀리는 일도 생긴다.
분할 정복을 배우고 문제를 푸는 동안 이 두 장면이 코드에서 그대로 나왔다. 거듭제곱을 반으로 쪼개는 코드는 한 줄만 잘못 써도 같은 계산을 두 번씩 하고, SWEA 1861의 첫 풀이는 같은 길을 몇 번이고 다시 걸었다. SWEA 5207에서는 “정렬한 상태로 저장한다”는 지문 한 문장을 믿었다가 예제는 다 맞히고 제출에서 틀렸다.
같은 날 배운 AVL·레드 블랙 트리는 이론 정리 - < 레드 블랙 트리는 2-3-4 트리다 >로 따로 뺐다.
분할 정복과 DP — 하위 문제가 겹치는가
둘 다 큰 문제를 작은 문제로 나눈다. 갈리는 지점은 나눈 하위 문제가 서로 겹치느냐다.
- 겹치지 않으면 각각 풀고 합친다 → 분할 정복 ( 병합 정렬의 왼쪽 절반과 오른쪽 절반은 공유하는 원소가 없다 )
- 겹치면 한 번 푼 결과를 저장해 다시 쓴다 → DP ( 피보나치의
f(n-1)과f(n-2)는f(n-3)을 같이 부른다 )
겹치지 않는 구조에 저장을 붙이면 다시 꺼낼 일이 없는 값만 쌓인다.
어떻게 나누느냐가 깊이를 정한다
재귀 트리의 깊이는 분할 모양이 정한다. 반씩 고르게 나누면 깊이가 log₂ n, 1과 n−1로 쏠리게 나누면 깊이가 n이다. 시간 복잡도는 대개 “층 수 × 층마다 하는 일”이고 재귀 스택도 층 수만큼 쌓이니, 깊이 하나가 둘을 같이 결정한다. n = 100만이면 약 20층 대 100만 층이다.
깊이를 어림할 때는 2¹⁰ ≈ 10³을 쓰면 편하다. 10억 ≈ 2³⁰이니 원소 10억 개짜리 이진 검색도 30번 남짓이면 끝난다.
몇 번 나눠야 하는가 — 가짜 동전 24개
가짜 동전 하나가 섞인 24개( 가짜가 더 가볍다 )에서 양팔 저울로 가짜를 찾는 문제다.
저울 한 번의 결과는 왼쪽이 가벼움 / 오른쪽이 가벼움 / 평형 세 가지다. k번 달면 구분할 수 있는 경우는 많아야 3ᵏ가지라 3² = 9 < 24 ≤ 27 = 3³, 최소 3번이 필요하다.
1번째: 8 | 8 | 8 → 가벼운 쪽, 평형이면 남은 8개
2번째: 3 | 3 | 2 → 가벼운 쪽, 평형이면 남은 2개
3번째: 1 | 1 | (1) → 끝
2묶음으로 반씩 나눠 달면 “평형”이라는 결과를 버리게 돼서 24 → 12 → 6 → 3 → 1, 4번이 든다. 결과 갈래 수 ≥ 후보 수로 하한을 잡는 방법은 비교 기반 정렬이 O(n log n)보다 빨라질 수 없다는 증명에도 똑같이 쓰인다 ( 비교 한 번은 2갈래, 후보는 n!가지 ).
빠른 거듭제곱 — 한 줄이 가르는 O(log n)과 O(n)
Cⁿ을 반으로 쪼갠다.
- n이 짝수: Cⁿ = Cⁿᐟ² × Cⁿᐟ²
- n이 홀수: Cⁿ = C⁽ⁿ⁻¹⁾ᐟ² × C⁽ⁿ⁻¹⁾ᐟ² × C
def power(x, n):
if n == 0: # base case. n == 1만 두면 n = 0에서 끝없이 내려간다
return 1
y = power(x, n // 2) # 절반 거듭제곱을 한 번만 계산해 y에 담는다
if n % 2 == 0:
return y * y # 짝수: 절반 × 절반
return y * y * x # 홀수: 절반 × 절반 × x
C⁸은 C → C² → C⁴ → C⁸로 곱셈 3번, C¹³은 호출 4번( 13 → 6 → 3 → 1 )에 곱셈 5번이다.
y에 담지 않고 power(x, n//2) * power(x, n//2)로 두 번 부르면 n = 8에서 호출이 1 + 2 + 4 + 8 = 15번, 일반적으로 2n − 1번이 된다. 같은 하위 문제를 두 번씩 푸는 겹침 구조가 생겨서 O(n)으로 무너진다. 결과를 y에 저장해 두 번 쓰는 건 메모이제이션과 같은 발상이고, 분할 정복 안에서도 겹침이 생기면 DP의 도구가 필요해진다.
이진 검색
정렬돼 있으면 mid와 한 번 비교해서 한쪽 절반에 답이 없다는 걸 보장할 수 있다. 이건 이론 정리 - < 이진 탐색, BST, 그래프 탐색 >에서 정리했다. 그때 빠져 있던 전제가 하나 있는데, mid로 O(1)에 바로 가야 한다. 연결 리스트에서는 mid까지 걸어가는 데만 O(n)이라 이득이 사라진다.
정렬 비용까지 넣으면
데이터가 정렬돼 있지 않다면 정렬부터 해야 한다. n = 100만, 검색 k번으로 비교하면 ( 상수 계수 무시 )
| 방법 | 비용 |
|---|---|
| 선형 탐색 k번 | k × 10⁶ |
| 정렬 후 이진 검색 k번 | 2 × 10⁷ + 20k |
k가 대략 log n( 약 20번 )을 넘으면 정렬하는 쪽이 이긴다. 한두 번 찾고 말 거면 그냥 훑는 게 낫다.
실패했을 때 low가 가리키는 곳
def binary_search(arr, key):
low, high = 0, len(arr) - 1 # 정답이 있을 수 있는 구간 [low, high]
while low <= high:
mid = low + (high - low) // 2 # 중간 위치
if arr[mid] == key:
return mid
if arr[mid] < key:
low = mid + 1 # mid도 답이 아니니 구간에서 뺀다
else:
high = mid - 1
return -low - 1 # 실패: -(삽입 위치) - 1 로 돌려준다 ( Java Arrays.binarySearch 방식 )
[low, high]를 “정답이 있을 수 있는 구간”으로 잡으면 mid ± 1인 이유가 바로 나온다. mid를 확인했는데 아니면 mid도 후보에서 빠진다.
실패로 끝났을 때 low는 key 이상인 첫 위치( lower_bound, 삽입 위치 )다. [2, 4, 7, 9, 11, 19, 23]에서 20을 찾으면
low=0 high=6 mid=3 (9) < 20 → low=4
low=4 high=6 mid=5 (19) < 20 → low=6
low=6 high=6 mid=6 (23) > 20 → high=5 종료, low=6
인덱스 6, 19와 23 사이가 20이 들어갈 자리다.
low + (high - low) // 2인 이유
(low + high) // 2는 덧셈 중간값이 넘칠 수 있다. 32비트 int에서 low = 20억, high = 21억이면 합이 41억으로 최댓값( 약 21.47억 )을 넘는다. 차이 방식은 1억 → 5천만 → 20.5억으로 범위 안에 머문다. Java 표준 라이브러리의 Arrays.binarySearch도 이 버그를 오래 안고 있다가 2006년에 Joshua Bloch가 공개적으로 짚었다.
파이썬 int는 크기 제한이 없어서 어느 쪽으로 써도 문제는 없다.
재귀와 반복
재귀 구현은 호출 깊이만큼 스택을 쓰고( O(log n) ), 반복 구현은 O(1)이다. 재귀 호출이 함수 마지막에 오는 꼬리 호출 형태여도 파이썬은 꼬리 호출 최적화를 하지 않고, C++도 표준이 보장하지 않는다.
Parametric Search — 최적화를 판정으로 뒤집기
“기계 여러 대로 물건 m개를 만드는 최소 시간“처럼 최적값을 묻는 문제를 “시간 T에 m개를 만들 수 있는가“라는 예/아니오 문제로 바꾼다.
def can_make(T, t, m):
return sum(T // ti for ti in t) >= m # 기계 i는 T초에 T // t[i]개를 만든다
T를 키우면 판정이 No, No, …, No, Yes, Yes, …로 한 번만 바뀐다. 이 단조성이 정렬의 역할을 대신해서, 첫 Yes가 나오는 T를 이진 검색으로 찾는다.
슬라이드 p.22 문제는 직접 풀지 않았다. 다만 범위를 잡을 때 걸리는 게 하나 있는데, 기계 1대에 t = 100억, m = 100억이면 답이 10²⁰이라 C++ long long( 약 9.2 × 10¹⁸ )을 넘는다. 파이썬이면 상관없지만 C++로 풀면 상한부터 따져봐야 한다.
병합 정렬 — pop(0)이 숨긴 O(n²)
정렬된 두 배열은 양쪽 맨 앞만 비교하면 합칠 수 있어서 O(a + b)다. 층마다 n개를 옮기고 층이 log n개라 O(n log n)이고, 입력이 어떻든 항상 반으로 자르니 최선과 최악이 같다.
슬라이드 코드는 left.pop(0)으로 맨 앞을 꺼낸다. 파이썬 list는 동적 배열이라 pop(0)이 남은 원소를 전부 한 칸씩 당긴다( O(k) ). 최상위 병합 한 번에만 약 (n/2)²/2번 이동이 생기고 전체가 O(n²)이 된다. 맨 앞 위치를 인덱스로만 옮기면 O(n log n)이 유지된다.
def merge(left, right):
result = []
i = j = 0 # 양쪽에서 아직 안 꺼낸 첫 위치
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= 여야 같은 값에서 왼쪽이 먼저 나온다
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:]) # 남은 쪽을 그대로 붙인다
result.extend(right[j:])
return result
슬라이드 p.28은 left[0] < right[0]이라 값이 같을 때 오른쪽을 먼저 꺼낸다. 병합 정렬은 안정 정렬인데 이 비교 하나로 안정성이 깨진다.
퀵 정렬 — partition 경계에서 일어나는 일
맨 왼쪽을 피벗 p로 잡고 양끝에서 스캔하는 방식이다.
def partition(arr, start, end):
p = arr[start] # 맨 왼쪽이 피벗
left, right = start + 1, end
while left <= right:
while left <= end and arr[left] < p: # p 이상을 만날 때까지
left += 1
while right > start and arr[right] >= p: # p 미만을 만날 때까지
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
arr[start], arr[right] = arr[right], arr[start] # 피벗은 R과 교환
return right
불변식은 start+1 ~ left-1이 p 미만, right+1 ~ end가 p 이상이다.
-
피벗을 L이 아니라 R과 바꾸는 이유: 교차한 순간
arr[right]는 p 미만,arr[left]는 p 이상이다. 피벗 자리( 맨 앞 )에는 p 미만이 와야 하니 R이다. 피벗이 구간 최댓값이면 L은end + 1까지 가 있어서 L과 바꾸면 범위를 벗어난다. -
right > start가 빠지면: 파이썬은 음수 인덱스가 배열 끝으로 감긴다. 전체 최솟값일 때는 IndexError로 터지기라도 하지만, 하위 구간에서는 구간 밖 원소와 피벗을 조용히 바꿔서 결과만 틀린다. -
같은 값이 몰리면:
</>=가 비대칭이라 p와 같은 값은 전부 오른쪽으로 간다.[5, 5, 5, 5, 5]는 L이 인덱스 1에서 바로 서고 R이 start까지 내려가서, 매번 0 : n−1로 갈라져 O(n²)이다. 양쪽 다 같은 값에서 멈추게(arr[i] < p,arr[j] > p) 하면 같은 값이 반반으로 나뉜다.
최악( 이미 정렬된 입력 등 )은 시간 O(n²)에 재귀 깊이도 n이다. 정렬된 10만 개를 넣으면 파이썬 기본 재귀 한도 1000에 걸린다. 작은 쪽만 재귀하고 큰 쪽은 반복문으로 돌리거나, 깊이가 커지면 힙 정렬로 갈아타는 introsort로 깊이를 묶는다. 그래서 이론상 적응성은 없지만, 현대적인 구현에선 이걸 예외처리하여 있는 것처럼 구현한다!
SWEA 5207 이진 탐색 — “정렬한 상태로 저장한다”
문제. 수 N개가 리스트 A에, M개가 리스트 B에 주어진다. B의 각 수가 A에 있는지 이진 탐색으로 찾되, 탐색하면서 고른 구간이 왼쪽·오른쪽을 번갈아 나와야 센다. 그런 수의 개수를 출력한다.
지문에 “정렬한 상태로 리스트 A에 저장한다”는 문장이 있다. 이걸 입력이 정렬돼서 들어온다는 보장으로 읽고 A를 정렬하지 않았다. 공개 예제의 A도 정렬돼 있었으니 예제는 맞았는데 제출하면 통과가 안 됐다. list_A.sort() 한 줄을 넣고서야 통과했고, 그때 코드에 남긴 주석이 이거다.
# 정렬 << 이거 악랄함 왜 테스트 케이스를 미리 정렬된 걸로 줌?
지금 다시 읽으면 그 문장은 입력의 성질이 아니라 받은 다음에 할 일을 말하는 것 같다 ( 히든 케이스를 볼 수 없으니 추측이다 ). 정렬을 넣어서 잃는 것도 거의 없었다. 파이썬 sort()는 Timsort라 이미 정렬된 입력은 run 하나로 알아보고 O(N)에 끝난다. 예제는 문제를 이해하라고 주는 것이고, 입력 보장은 지문 문장에서만 찾는다. 해석이 갈리면 처리해도 손해가 없는 쪽을 고른다.
같이 고친 건 두 가지다.
- 같은 방향이 연속되는 순간
break. 번갈아 나오지 않은 순간 결과는 이미 정해졌다 ( 백트래킹 가지치기와 같은 발상 ) - 찾았는지 여부를 bool 하나로 줄였다
T = int(input())
for test_case in range(1, T + 1):
# N = 이진 탐색될 list(A) 크기, M = 탐색할 정수 list(B) 개수
N, M = map(int, input().split())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
# 두 리스트에 존재하며, 이진 탐색 간 양쪽 구간(left, right)을 번갈아 경험한 정수 수
num_cnt = 0
list_A.sort()
# list_B 숫자들 완전 탐색
for key in list_B:
# 이진 탐색 구현
left = 0
right = N - 1
# find = 탐색 성공 여부
find = False
# -1 은 왼쪽, 1 은 오른쪽 으로 이전과 동일한 결과일 경우 False
prev = 0
while left <= right:
mid = left + ((right - left) // 2)
if list_A[mid] == key:
find = True
break
elif list_A[mid] > key:
if prev == -1: break
prev = -1
right = mid - 1
else:
if prev == 1: break
prev = 1
left = mid + 1
# 찾는 것, 번 갈아 가는게 실패했을 시 early continue
if not find: continue
num_cnt += 1
print(f'#{test_case} {num_cnt}')
SWEA 1861 정사각형 방 — 메모이제이션은 왜 터지나
문제. N×N( N ≤ 1000 ) 방에 1 ~ N²의 서로 다른 수가 적혀 있다. 상하좌우로 인접하면서 정확히 1 큰 방으로만 이동할 수 있다. 가장 많은 방을 지나는 출발 방 번호( 동점이면 가장 작은 번호 )와 지나는 방 개수를 출력한다.
첫 풀이 — 모든 칸에서 따라가기
모든 칸에서 출발해 경로를 끝까지 따라갔다. 수가 전부 달라서 다음으로 갈 수 있는 방은 많아야 하나라, 찾으면 break로 바로 넘어갔다.
T = int(input())
# 상 좌 우 하 순회
dxy = ((-1, 0), (0, 1), (1, 0), (0, -1))
for test_case in range(1, T + 1):
# N = 방의 갯수 // 최대 1000 으로 최대 방 크기는 1,000,000 임
N = int(input())
# rooms = matrix 형태의 숫자가 들어간 방
rooms = [list(map(int, input().split())) for _ in range(N)]
max_cnt = float("-inf")
min_num = float("inf")
for i in range(N):
for j in range(N):
cx = i
cy = j
cnt = 0
changed = True
while changed:
# 4방향 탐색하여 숫자가 클 경우에만 이동
# 중복되는 수가 없으므로 무조건 1개의 길이 있거나 없거나임
changed = False
for dx, dy in dxy:
nx, ny = cx + dx, cy + dy
# rooms 를 넘어가는 값 무시
if nx < 0 or nx >= N or ny < 0 or ny >= N: continue
# 조건을 만족하지 못하면 무시
if rooms[cx][cy] + 1 != rooms[nx][ny]: continue
# 성공 시 값 업데이트 후 다음으로
changed = True
cnt += 1
cx = nx
cy = ny
break
if max_cnt == cnt: min_num = min(min_num, rooms[i][j])
elif max_cnt < cnt:
min_num = rooms[i][j]
max_cnt = cnt
# 출력 조건을 만족하는 가장 작은 방 번호, 최대 이동 방의 수
print(f'#{test_case} {min_num} {max_cnt + 1}')
느린 이유는 빠른 거듭제곱의 두 번 호출과 같다. v에서 출발한 경로의 v+1 이후는 v+1에서 출발할 때 똑같이 다시 걷는다. 겹침 구조다.
큰 값부터 역산
v+1에서 출발한 길이를 알면 v는 바로 나온다.
- v+1이 v와 인접하면
road[v] = road[v + 1] + 1 - 아니면
road[v] = 1
입력을 읽으면서 pos[v] = (i, j)를 채워두고, v = N² − 1부터 1까지 내려가며 road[v]를 채우면 O(N²)이다. length를 N² + 2로 잡은 건 1번부터 쓰고 v + 1을 한 칸 더 조회하기 때문이다.
T = int(input())
# 상 좌 우 하 순회
dxy = ((-1, 0), (0, 1), (1, 0), (0, -1))
for test_case in range(1, T + 1):
# N = 방의 갯수 // 최대 1000 으로 최대 방 크기는 1,000,000 임
N = int(input())
# 1부터 시작해서 + 1, 마지막 값에서 추가 조회를 생각해 + 1
length = N * N + 2
# pos = 숫자들의 위치 정보
pos = [(0, 0)] * length
# road = 이동할 수 있는 경로의 합
road = [1] * length
for i in range(N):
row = list(map(int, input().split()))
for j, v in enumerate(row):
pos[v] = (i, j)
max_cnt = 1
min_num = 1
# 제일 큰 수부터 역산
for v in range(1, length - 2)[::-1]:
cur = pos[v]
nxt = pos[v + 1]
for dx, dy in dxy:
# 4방향 중 다음 숫자 위치와 동일한게 있으면
if cur[0] + dx == nxt[0] and cur[1] + dy == nxt[1]:
# 다음 숫자의 경로 합에 + 1하여 저장
road[v] = road[v+1] + 1
# 최댓값 중 가장 작은 방 번호 저장
if max_cnt > road[v]: break
# 최댓값 갱신
min_num = v
max_cnt = road[v]
break
# 출력 조건을 만족하는 가장 작은 방 번호, 최대 이동 방의 수
print(f'#{test_case} {min_num} {max_cnt}')
큰 값에서 작은 값으로 내려가니까 동점이면 지금 v가 항상 더 작다. 비교 없이 덮어쓰기만 해도 최소 번호가 남는다.
pos[v]는 입력을 읽으면서 enumerate로 채운다. 따로 한 번 더 훑어도 O(N²)으로 같고, 피해야 하는 건 순회 안에서 다시 N²짜리 작업을 하는 구조다. 튜플 100만 개는 수십 MB 단위로 추정돼서 메모리가 빠듯하면 정수 리스트 두 개나 i * N + j 인코딩으로 바꾸면 된다.
초기값 inf가 출력되는 경우
역산으로 바꾼 직후에는 초기값이 첫 풀이처럼 float("-inf"), float("inf")였다. 첫 풀이는 모든 칸에서 cnt가 0 이상으로 나와 한 번은 갱신되니 괜찮았지만, 역산은 인접한 쌍을 찾았을 때만 갱신한다. N = 1이면 range(1, 1)이 비어서 루프가 한 번도 안 돌고 초기값이 그대로 출력된다. 인접한 연속 수가 하나도 없는 배치도 똑같다.
inf 같은 센티널은 반드시 한 번 이상 갱신된다는 보장이 있을 때만 안전하다. 갱신이 없을 때의 정답( 1번 방에서 출발, 방 1개 )을 초기값으로 1 1로 두니 예외 처리 없이 두 경우가 다 맞았다.
top-down으로 짰다면
같은 점화식을 재귀 + 메모이제이션으로 쓰면 계산 순서를 신경 쓸 필요가 없어서 더 편해 보인다. 그런데 1 ~ N²가 한 줄로 이어진 배치면 road(1)이 road(2)를, road(2)가 road(3)을 부르면서 깊이가 N² = 100만이 된다. 파이썬은 기본 한도 1000에서 RecursionError가 나고, sys.setrecursionlimit으로 한도를 올려도 실제 스택 크기는 운영체제가 정하니 그쪽이 먼저 바닥나서 프로세스가 죽을 수 있다.
메모이제이션은 시간만 줄인다. bottom-up은 도는 순서 자체가 “필요한 값이 먼저 준비돼 있음”을 보장하고 스택을 쓰지 않는다.
소감
이미 정렬된 곳에서 분할없는 분할 정복이 해내는 N² 이 웃겼던 것 같다. 개인적으로 오늘 공부한 내용들이 조금 신기했던 것들이 있었다.