동적 계획법 안내서 · 5/6
아래 다섯 문제는 이 안내서를 위해 새로 만든 문제입니다. 풀이를 읽기 전에 먼저 상태, 점화식, 기저 사례, 계산 순서를 종이에 적고 코드로 옮겨 보세요. 모든 풀이는 Python 3.9 이상에서 실행됩니다.
계단이 n칸 있습니다. 0번 칸에서 시작해 한 번에 1, 2, 3칸씩 오를 수 있지만, 부서진 칸은 밟을 수 없습니다. n번 칸에 도착하는 방법의 수를 1_000_000_007로 나눈 나머지로 구하세요.
예: n = 4이고 2번 칸이 부서졌다면 0-1-4, 0-3-4, 0-1-3-4의 세 가지가 가능합니다. 0-2-4나 0-1-2-3-4는 2번 칸을 밟으므로 안 됩니다.
풀이: ways[i] = i번 칸에 서는 방법의 수. 부서진 칸은 0이고, 나머지는 ways[i] = ways[i-1] + ways[i-2] + ways[i-3]입니다. 기저 사례는 ways[0] = 1입니다.
MOD = 1_000_000_007
def count_climbs(n: int, broken: set[int]) -> int:
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
if i in broken:
continue
ways[i] = sum(ways[i - s] for s in (1, 2, 3) if i - s >= 0) % MOD
return ways[n]
print(count_climbs(4, {2})) # 3
print(count_climbs(30, set())) # 53798080물류 창고 바닥이 통행료가 적힌 격자로 되어 있습니다. 로봇은 왼쪽 위 칸에서 출발해 오른쪽이나 아래로만 움직여 오른쪽 아래 칸에 도착해야 하며, 들어가는 모든 칸(첫 칸 포함)의 통행료를 냅니다. 최소 통행료 합을 구하세요.
풀이: cost[r][c] = (r, c) 칸에 도착하는 최소 비용. 각 칸은 위나 왼쪽에서만 들어오므로 cost[r][c] = grid[r][c] + min(위, 왼쪽)입니다. 각 행은 바로 위 행만 필요하므로 한 행만 들고 있으면 됩니다.
def cheapest_route(grid: list[list[int]]) -> int:
cols = len(grid[0])
row = [0] * cols
for r, line in enumerate(grid):
for c, toll in enumerate(line):
if r == 0 and c == 0:
row[c] = toll
elif r == 0:
row[c] = row[c - 1] + toll
elif c == 0:
row[c] = row[c] + toll
else:
row[c] = min(row[c], row[c - 1]) + toll
return row[-1]
print(cheapest_route([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # 7검색창에서 사용자가 입력한 단어와 가장 가까운 상품 이름을 추천하려고 합니다. 두 단어 사이의 거리를, 한 단어를 다른 단어로 바꾸는 데 필요한 한 글자 삽입, 삭제, 교체의 최소 횟수(레벤슈타인 거리)로 정의하고 이를 계산하세요.
풀이: d[i][j] = s의 앞 i글자와 t의 앞 j글자 사이의 거리. 두 글자가 같으면 d[i][j] = d[i-1][j-1], 다르면 삭제(d[i-1][j]), 삽입(d[i][j-1]), 교체(d[i-1][j-1]) 중 최솟값에 1을 더합니다. 기저 사례는 d[i][0] = i, d[0][j] = j입니다.
def edit_distance(s: str, t: str) -> int:
prev = list(range(len(t) + 1))
for i, a in enumerate(s, start=1):
cur = [i] + [0] * len(t)
for j, b in enumerate(t, start=1):
if a == b:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
print(edit_distance("keybaord", "keyboard")) # 2
print(edit_distance("kitten", "sitting")) # 3한 팀이 정수 금액의 상금 여러 개를 받았습니다. 상금을 두 묶음으로 나누어 두 묶음의 합을 정확히 같게 만들 수 있을까요?
풀이: 합이 홀수면 불가능합니다. 짝수라면 합이 total // 2인 부분집합이 있는지 묻는 문제가 되고, 이는 참/거짓 값을 쓰는 0/1 배낭입니다. can[s]는 지금까지 본 상금으로 합 s를 만들 수 있으면 참입니다. 상금마다 한 번만 쓰도록 합을 큰 쪽에서 작은 쪽으로 돕니다.
def can_split_evenly(prizes: list[int]) -> bool:
total = sum(prizes)
if total % 2:
return False
target = total // 2
can = [True] + [False] * target
for p in prizes:
for s in range(target, p - 1, -1):
can[s] = can[s] or can[s - p]
return can[target]
print(can_split_evenly([3, 1, 5, 9, 4])) # False (합 22, 합 11인 부분집합 없음)
print(can_split_evenly([3, 1, 5, 9, 2])) # True (9 + 1 = 3 + 5 + 2)날마다의 기온이 주어질 때, 고른 날마다 직전에 고른 날보다 기온이 엄격하게 높아지는 가장 긴 날짜 열(연속일 필요 없음)을 찾아 그중 하나를 돌려주세요.
풀이: O(n^2) LIS는 복원이 쉽습니다. length[i]는 i번째 날에서 끝나는 가장 긴 증가 부분 수열의 길이이고, parent[i]는 그 수열에서 바로 앞의 날을 기억합니다.
def warming_streak(temps: list[int]) -> list[int]:
if not temps:
return []
n = len(temps)
length = [1] * n
parent = [-1] * n
for i in range(n):
for j in range(i):
if temps[j] < temps[i] and length[j] + 1 > length[i]:
length[i] = length[j] + 1
parent[i] = j
i = max(range(n), key=length.__getitem__)
streak = []
while i != -1:
streak.append(temps[i])
i = parent[i]
return streak[::-1]
print(warming_streak([12, 9, 14, 10, 15, 11, 18, 13])) # [12, 14, 15, 18]입력이 길다면 복잡도 장의 bisect 버전에 위치 배열을 더해 O(n log n)으로 복원할 수 있습니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.