설계 기법 코드
노트의 개념을 Python 3로 옮긴 코드다. 표준 라이브러리만 쓰고, 파일 끝의 assert 예제가 그대로 실행된다. 복사해 python3 파일이름.py로 돌려 보자.
분할 정복
"""분할 정복: 문제를 같은 모양의 작은 문제로 나눠 풀고 답을 합친다. 예제는 최댓값 찾기와 카라츠바 곱셈이다.
시간: 최댓값 T(n) = 2T(n/2) + 1 = O(n), 카라츠바 T(n) = 3T(n/2) + O(n) = O(n^1.585) (n은 자릿수)
공간: 재귀 깊이 O(log n)
"""
import random
def max_divide(values: list, low: int = 0, high: int | None = None) -> tuple[int, int]:
"""values[low..high]의 최댓값과 비교 횟수. 반으로 나눠 양쪽 최댓값 중 큰 쪽을 고른다."""
if high is None:
high = len(values) - 1
if low == high:
return values[low], 0
middle = (low + high) // 2
left, left_comparisons = max_divide(values, low, middle)
right, right_comparisons = max_divide(values, middle + 1, high)
return max(left, right), left_comparisons + right_comparisons + 1
def karatsuba(x: int, y: int) -> int:
"""음이 아닌 정수 x, y의 곱. 반으로 나눈 곱셈 네 번을 세 번으로 줄인다."""
if x < 10 or y < 10:
return x * y
half = max(len(str(x)), len(str(y))) // 2
split = 10**half
x_high, x_low = divmod(x, split)
y_high, y_low = divmod(y, split)
high = karatsuba(x_high, y_high)
low = karatsuba(x_low, y_low)
# (높은+낮은)끼리의 곱에서 high와 low를 빼면 가운데 두 항의 합만 남는다
middle = karatsuba(x_high + x_low, y_high + y_low) - high - low
return high * split * split + middle * split + low
if __name__ == "__main__":
assert max_divide([3, 9, 2, 7, 5, 1, 8, 6]) == (9, 7)
assert max_divide([4]) == (4, 0)
# 맨 위 단계: 12·56 = 672, 34·78 = 2652, 46·134 = 6164, 가운데 2840
assert (12 + 34) * (56 + 78) - 12 * 56 - 34 * 78 == 2840
assert karatsuba(1234, 5678) == 7006652
assert karatsuba(0, 987) == 0
assert karatsuba(7, 8) == 56
rng = random.Random(7)
for _ in range(200):
x = rng.randint(0, 10**12)
y = rng.randint(0, 10**9)
assert karatsuba(x, y) == x * y
sample = [rng.randint(-50, 50) for _ in range(rng.randint(1, 20))]
found, comparisons = max_divide(sample)
assert found == max(sample)
assert comparisons == len(sample) - 1
print("ok")동적 계획법
"""동적 계획법: 겹치는 작은 문제의 답을 표에 적어 두고 다시 쓴다. 예제는 피보나치(메모이제이션)와 0/1 배낭(타뷸레이션)이다.
시간: 피보나치 O(n), 배낭 O(nW) (n은 물건 수, W는 무게 한도), 최소 동전 O(Vk)
공간: 피보나치 O(n), 배낭 O(nW) 표 (한 줄로 줄이면 O(W))
"""
import random
from functools import cache
from itertools import combinations
def fib_naive(n: int, counter: list[int]) -> int:
"""메모 없는 재귀. counter[0]에 호출 수를 더한다."""
counter[0] += 1
if n < 2:
return n
return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)
@cache
def fib_memo(n: int) -> int:
"""메모이제이션(위에서 아래로): 같은 인자는 한 번만 계산한다."""
if n < 2:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
def knapsack(items: list[tuple[int, int]], capacity: int) -> tuple[int, list[int]]:
"""0/1 배낭(아래에서 위로). (무게, 가치) 목록에서 최대 가치와 고른 물건 번호(1부터)를 돌려준다."""
best = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
for row, (weight, value) in enumerate(items, start=1):
for limit in range(capacity + 1):
best[row][limit] = best[row - 1][limit]
if weight <= limit:
best[row][limit] = max(best[row][limit], best[row - 1][limit - weight] + value)
# 오른쪽 아래에서 거꾸로: 값이 위 칸과 다르면 그 물건을 넣은 것이다
chosen = []
limit = capacity
for row in range(len(items), 0, -1):
if best[row][limit] != best[row - 1][limit]:
chosen.append(row)
limit -= items[row - 1][0]
return best[len(items)][capacity], sorted(chosen)
def knapsack_one_row(items: list[tuple[int, int]], capacity: int) -> int:
"""표를 한 줄로 줄인 0/1 배낭. 한도를 큰 쪽부터 돌아야 같은 물건을 두 번 넣지 않는다."""
best = [0] * (capacity + 1)
for weight, value in items:
for limit in range(capacity, weight - 1, -1):
best[limit] = max(best[limit], best[limit - weight] + value)
return best[capacity]
def min_coins_table(coins: list[int], amount: int) -> list[float]:
"""0~amount원을 만드는 최소 동전 수 표. 만들 수 없으면 inf."""
best = [0.0] + [float("inf")] * amount
for value in range(1, amount + 1):
for coin in coins:
if coin <= value:
best[value] = min(best[value], best[value - coin] + 1)
return best
def knapsack_brute_force(items: list[tuple[int, int]], capacity: int) -> int:
"""모든 부분집합을 시험한 최대 가치(검산용)."""
return max(
sum(value for _, value in subset)
for size in range(len(items) + 1)
for subset in combinations(items, size)
if sum(weight for weight, _ in subset) <= capacity
)
if __name__ == "__main__":
counter = [0]
assert fib_naive(6, counter) == 8
assert counter[0] == 25
assert [fib_memo(n) for n in range(7)] == [0, 1, 1, 2, 3, 5, 8]
assert fib_memo(90) == 2880067194370816120
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
assert knapsack(items, 5) == (7, [1, 2])
assert knapsack_one_row(items, 5) == 7
assert knapsack_one_row([(2, 3)], 4) == 3
assert knapsack([], 5) == (0, [])
assert min_coins_table([1, 3, 4], 6) == [0, 1, 2, 1, 1, 2, 2]
rng = random.Random(8)
for _ in range(200):
sample = [(rng.randint(1, 6), rng.randint(1, 10)) for _ in range(rng.randint(0, 6))]
capacity = rng.randint(0, 12)
expected = knapsack_brute_force(sample, capacity)
value, chosen = knapsack(sample, capacity)
assert value == knapsack_one_row(sample, capacity) == expected
assert sum(sample[index - 1][0] for index in chosen) <= capacity
assert sum(sample[index - 1][1] for index in chosen) == expected
print("ok")탐욕법
"""탐욕법: 단계마다 지금 가장 좋아 보이는 것을 고르고 되돌아보지 않는다. 맞는 예(회의실 배정)와 틀리는 예(거스름돈 반례)를 함께 본다.
시간: 거스름돈 O(k + 동전 수), 회의실 배정 O(n log n) (끝나는 시간으로 정렬)
공간: O(n)
"""
import random
from itertools import combinations
def greedy_change(coins: list[int], amount: int) -> list[int]:
"""남은 금액보다 크지 않은 가장 큰 동전을 되풀이해 낸다. 다 거슬러 주지 못하면 빈 리스트."""
taken = []
for coin in sorted(coins, reverse=True):
while coin <= amount:
taken.append(coin)
amount -= coin
return taken if amount == 0 else []
def min_change_count(coins: list[int], amount: int) -> float:
"""동적 계획법으로 구한 최소 동전 수(검산용). 만들 수 없으면 inf."""
best = [0.0] + [float("inf")] * amount
for value in range(1, amount + 1):
best[value] = min((best[value - coin] + 1 for coin in coins if coin <= value), default=float("inf"))
return best[amount]
def select_meetings(meetings: list[tuple[int, int]]) -> list[tuple[int, int]]:
"""끝나는 시간이 가장 이른 회의부터, 앞서 고른 회의와 겹치지 않으면 고른다. 개수가 최대다."""
chosen = []
last_end = float("-inf")
for start, end in sorted(meetings, key=lambda meeting: meeting[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
def max_meetings_brute_force(meetings: list[tuple[int, int]]) -> int:
"""서로 겹치지 않는 회의를 가장 많이 고른 개수(검산용)."""
for size in range(len(meetings), 0, -1):
for subset in combinations(sorted(meetings), size):
if all(left[1] <= right[0] for left, right in zip(subset, subset[1:])):
return size
return 0
if __name__ == "__main__":
assert greedy_change([500, 100, 50, 10], 760) == [500, 100, 100, 50, 10]
assert len(greedy_change([10, 5, 1], 14)) == min_change_count([10, 5, 1], 14) == 5
# 반례: 탐욕은 10 + 1 + 1 + 1 + 1, 최적은 7 + 7
assert greedy_change([10, 7, 1], 14) == [10, 1, 1, 1, 1]
assert min_change_count([10, 7, 1], 14) == 2
assert greedy_change([4, 3, 1], 6) == [4, 1, 1]
assert min_change_count([4, 3, 1], 6) == 2
assert greedy_change([5, 3], 7) == []
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (6, 10), (8, 11), (9, 12)]
assert select_meetings(meetings) == [(1, 4), (5, 7), (8, 11)]
assert select_meetings([]) == []
rng = random.Random(9)
for _ in range(200):
amount = rng.randint(0, 200)
assert len(greedy_change([500, 100, 50, 10, 5, 1], amount)) == min_change_count([500, 100, 50, 10, 5, 1], amount)
sample = []
for _ in range(rng.randint(0, 7)):
start = rng.randint(0, 10)
sample.append((start, start + rng.randint(1, 5)))
assert len(select_meetings(sample)) == max_meetings_brute_force(sample)
print("ok")백트래킹
"""백트래킹: 하나씩 골라 나가다 규칙에 어긋나면 그 갈래를 버리고 직전 선택으로 되돌아간다. 예제는 N-Queens와 부분집합 합이다.
시간: 최악 지수 시간(N-Queens는 O(N!) 근처). 가지치기는 차수가 아니라 실제로 훑는 갈래를 줄인다.
공간: O(N) — 지금까지의 선택과 재귀 스택
"""
def solve_n_queens(size: int, first_only: bool = False) -> list[list[int]]:
"""N×N 판의 해(행마다 퀸의 열, 0부터)를 모두, 또는 첫 해 하나만 돌려준다."""
solutions: list[list[int]] = []
queens: list[int] = []
# 쓰인 열과 두 방향 대각선(행-열, 행+열)을 들고 다니면 "안전한가?"가 O(1)이다
used_cols: set[int] = set()
used_down: set[int] = set()
used_up: set[int] = set()
def place(row: int) -> bool:
if row == size:
solutions.append(list(queens))
return first_only
for col in range(size):
if col in used_cols or row - col in used_down or row + col in used_up:
continue
queens.append(col)
used_cols.add(col)
used_down.add(row - col)
used_up.add(row + col)
if place(row + 1):
return True
queens.pop()
used_cols.remove(col)
used_down.remove(row - col)
used_up.remove(row + col)
return False
place(0)
return solutions
def subset_sums(nums: list[int], target: int, prune: bool = True) -> tuple[list[list[int]], int]:
"""오름차순 양수 nums에서 합이 target인 조합 전부와 호출 수. prune이면 target을 넘는 순간 뒤의 수를 건너뛴다."""
solutions: list[list[int]] = []
chosen: list[int] = []
calls = 0
def explore(start: int, total: int) -> None:
nonlocal calls
calls += 1
if total == target:
solutions.append(list(chosen))
for index in range(start, len(nums)):
if prune and total + nums[index] > target:
# 정렬돼 있으니 뒤의 수를 더해도 넘는다
break
chosen.append(nums[index])
explore(index + 1, total + nums[index])
chosen.pop()
explore(0, 0)
return solutions, calls
if __name__ == "__main__":
assert solve_n_queens(4, first_only=True) == [[1, 3, 0, 2]]
assert solve_n_queens(5, first_only=True) == [[0, 2, 4, 1, 3]]
known_counts = {1: 1, 2: 0, 3: 0, 4: 2, 5: 10, 6: 4, 8: 92}
for size, count in known_counts.items():
assert len(solve_n_queens(size)) == count
for solution in solve_n_queens(6):
for row in range(6):
for other in range(row):
assert solution[row] != solution[other]
assert abs(solution[row] - solution[other]) != row - other
assert subset_sums([2, 3, 5, 7], 10) == ([[2, 3, 5], [3, 7]], 11)
assert subset_sums([2, 3, 5, 7], 10, prune=False) == ([[2, 3, 5], [3, 7]], 16)
assert subset_sums([], 0) == ([[]], 1)
assert subset_sums([4], 3) == ([], 1)
print("ok")두 포인터·슬라이딩 윈도
"""두 포인터와 슬라이딩 윈도: 인덱스 두 개를 한 방향으로만 움직여 쌍이나 연속 구간을 O(n)에 찾는다.
시간: O(n) — 두 인덱스가 각각 많아야 n번 움직인다
공간: O(1)
조건: 두 포인터는 정렬된 배열, 슬라이딩 윈도는 값이 모두 양수일 때만 맞다.
"""
import random
def pair_with_sum(sorted_values: list[int], target: int) -> tuple[int, int] | None:
"""정렬된 배열에서 합이 target인 두 칸의 위치. 없으면 None."""
left, right = 0, len(sorted_values) - 1
while left < right:
total = sorted_values[left] + sorted_values[right]
if total == target:
return left, right
# 합이 작으면 왼쪽 값은 남은 가장 큰 값과도 모자라니 버린다
if total < target:
left += 1
else:
right -= 1
return None
def longest_window(values: list[int], limit: int) -> tuple[int, int] | None:
"""합이 limit 이하인 가장 긴 연속 구간 [start, end](양 끝 포함). 값이 모두 양수라고 가정한다."""
best = None
start = 0
total = 0
for end, value in enumerate(values):
total += value
while total > limit and start <= end:
total -= values[start]
start += 1
if start <= end and (best is None or end - start > best[1] - best[0]):
best = (start, end)
return best
def longest_window_brute_force(values: list[int], limit: int) -> int:
"""모든 구간을 시험한 가장 긴 길이(검산용). 음수가 있어도 맞다."""
return max(
(end - start + 1 for start in range(len(values)) for end in range(start, len(values)) if sum(values[start : end + 1]) <= limit),
default=0,
)
def window_length(window: tuple[int, int] | None) -> int:
"""구간의 길이. 없으면 0."""
return 0 if window is None else window[1] - window[0] + 1
if __name__ == "__main__":
assert pair_with_sum([1, 3, 4, 6, 8, 11, 14], 19) == (4, 5)
assert pair_with_sum([1, 3, 6, 8, 11, 14, 16], 20) == (2, 5)
assert pair_with_sum([2, 5, 8, 12, 15], 20) == (1, 4)
assert pair_with_sum([1, 2], 10) is None
assert pair_with_sum([], 0) is None
assert window_length(longest_window([4, 2, 1, 3, 1, 1, 2, 5, 1], 7)) == 4
assert longest_window([2, 1, 3, 1, 1, 4, 2, 1], 6) == (1, 4)
assert longest_window([9], 3) is None
# 음수가 섞이면 틀린다: 3을 버린 뒤 -5가 와도 되돌아가지 않는다
assert window_length(longest_window([3, 4, -5, 2, 1], 5)) == 4
assert longest_window_brute_force([3, 4, -5, 2, 1], 5) == 5
rng = random.Random(10)
for _ in range(300):
sample = sorted(rng.randint(0, 30) for _ in range(rng.randint(0, 12)))
target = rng.randint(0, 60)
has_pair = any(sample[i] + sample[j] == target for i in range(len(sample)) for j in range(i + 1, len(sample)))
assert (pair_with_sum(sample, target) is not None) == has_pair
positives = [rng.randint(1, 6) for _ in range(rng.randint(0, 12))]
limit = rng.randint(0, 15)
assert window_length(longest_window(positives, limit)) == longest_window_brute_force(positives, limit)
print("ok")