Coding Interview Prep · 강의

표 작성을 이용한 상향식 DP

하향식 해법을 반복적인 DP 표로 변환하고, 최근 몇 개의 값만 필요할 때 공간을 O(n)에서 O(1)로 줄입니다.

표 작성을 이용한 상향식 DP은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

상향식 DP: 표 작성법

상향식 DP(표 작성법)는 가장 작은 부분 문제에서 시작하여 답을 완성해 가며 부분 문제의 답을 표에 채웁니다. 아래로 재귀 호출한 뒤 돌아오면서 캐시하는 대신, 가장 작은 문제부터 반복적으로 계산합니다. 표는 일반적으로 1차원 또는 2차원 배열이며, 각 칸은 이전에 채운 칸을 바탕으로 계산됩니다. 이 방식은 재귀를 완전히 없애므로 호출 스택과 재귀 제한이 필요 없고, 캐시 지역성도 더 좋습니다.

# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)

# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')

상향식 피보나치

상향식 피보나치는 dp[0..n]을 왼쪽에서 오른쪽으로 채웁니다. i >= 2일 때 dp[i] = dp[i-1] + dp[i-2]입니다. 기저 사례인 dp[0] = 0과 dp[1] = 1은 배열에 직접 저장합니다. 전체 표를 사용하면 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. dp[i]가 마지막 두 값에만 의존한다는 것을 알게 되면 두 개의 변수로 공간을 O(1)까지 줄일 수 있습니다. 이것이 공간 최적화 단계입니다.

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0  # base case
    dp[1] = 1  # base case
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Space-optimised to O(1):
def fib_optimised(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_optimised(50))  # 12586269025

상향식 동전 교환

동전 교환에서는 dp[0..amount]가 상향식 표가 되며, dp[i]는 금액 i를 만들기 위한 최소 동전 개수입니다. dp[0] = 0(금액 0에는 동전 0개)을 초기화하고 dp[1..amount] = 무한대로 설정합니다. 1부터 목표 금액까지 각 금액 i에 대해 모든 동전을 시도합니다. i >= coin이면 dp[i] = min(dp[i], 1 + dp[i - coin])으로 갱신합니다. 답은 dp[amount]이며, 여전히 무한대라면 -1입니다.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins for amount 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:  # can use this coin
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2: (5+6)
print(coin_change([2], 3))             # -1: impossible
print(coin_change([1, 2, 5], 11))      # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249))  # 20

계산 순서: 핵심 통찰

계산 순서는 상향식 DP의 핵심입니다. 어떤 상태 dp[i]에 대해서든, 해당 상태가 의존하는 모든 상태를 먼저 계산해야 합니다. dp[i]가 dp[i-1]과 dp[i-2]에 의존하는 1차원 DP라면 왼쪽에서 오른쪽으로 채웁니다. dp[i][j]가 dp[i-1][j]와 dp[i][j-1]에 의존하는 2차원 DP라면 행 단위로 채웁니다(위에서 아래로, 왼쪽에서 오른쪽으로). 코드를 작성하기 전에 항상 의존 관계 화살표를 그려 계산 순서를 확인하세요.

# Fill order examples:

# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n

# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.

# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems

print('Draw dependencies first, then determine fill order')

상향식 LCS: 2차원 표

최장 공통 부분 수열의 상향식 표 크기는 (m+1) × (n+1)이며, dp[i][j]는 s1[:i]와 s2[:j]의 LCS를 나타냅니다. 기저 사례는 dp[0][j] = dp[i][0] = 0입니다(빈 문자열과 어떤 문자열의 LCS도 0입니다). 행 단위로 표를 채웁니다. s1[i-1] == s2[j-1]이면 dp[i][j] = 1 + dp[i-1][j-1]이고, 그렇지 않으면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])입니다. 답은 dp[m][n]입니다.

def lcs_bottom_up(s1, s2):
    m, n = len(s1), len(s2)
    # (m+1) x (n+1) table, initialised to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:         # characters match
                dp[i][j] = 1 + dp[i-1][j-1]
            else:                            # skip one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs_bottom_up('abcde', 'ace'))   # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB'))  # 4: 'BCAB' or 'BDAB'

공간 최적화: 순환 배열

많은 2차원 DP 표는 dp[i][j]가 현재 행과 이전 행에만 의존한다는 점을 이용하여 1차원(또는 2개 행)으로 줄일 수 있습니다. prev와 curr이라는 두 배열을 유지하거나, 올바른 순서로 하나의 배열을 갱신합니다. LCS에서 dp[i][j]는 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]에 의존하므로 이전 행만 유지해도 충분합니다.

def lcs_space_optimised(s1, s2):
    m, n = len(s1), len(s2)
    # Keep only one row (previous row state)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = 1 + prev[j-1]  # dp[i-1][j-1]
            else:
                curr[j] = max(prev[j], curr[j-1])  # dp[i-1][j] and dp[i][j-1]
        prev = curr
    return prev[n]

print(lcs_space_optimised('abcde', 'ace'))   # 3
# Space: O(n) instead of O(mn)

상향식 하우스 로버

하우스 로버의 상향식 풀이는 dp[0..n-1]을 채우며, dp[i]는 0번부터 i번까지의 집을 털어서 얻을 수 있는 최대 이익입니다. dp[0] = nums[0], dp[1] = max(nums[0], nums[1])이고, i >= 2일 때 dp[i] = max(dp[i-1], dp[i-2] + nums[i])입니다. dp[i]가 마지막 두 값에만 의존하므로 두 개의 변수로 즉시 O(1)까지 공간을 최적화할 수 있습니다. 이는 두 단계 전 상태에 의존하는 1차원 DP의 일반적인 패턴입니다.

def rob_bottom_up(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]

    # Full table version: O(n) space
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

def rob_optimised(nums):
    # O(1) space: only need last two values
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

print(rob_optimised([2, 7, 9, 3, 1]))  # 12

격자에서의 최소 경로 합

최소 경로 합(LeetCode #64)은 왼쪽 위에서 오른쪽 아래까지 이동하는 경로 중 값의 합이 최소인 경로를 찾는 문제입니다(오른쪽이나 아래로만 이동할 수 있습니다). 2차원 DP에서 dp[i][j]는 (i,j) 칸에 도달하는 최소 합입니다. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])입니다. 왼쪽에서 오른쪽으로, 위에서 아래로 채웁니다. 기저 사례는 dp[0][0] = grid[0][0]이며, 첫 번째 행은 오른쪽으로만 이동하는 방식으로 채우고 첫 번째 열은 아래로만 이동하는 방식으로 채웁니다.

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    # Fill first row (can only come from left)
    for c in range(1, cols):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    # Fill first column (can only come from above)
    for r in range(1, rows):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    # Fill rest of the table
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
    return dp[rows-1][cols-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7: 1+3+1+1+1

DP 표를 제자리에서 수정하기

추가 공간이 허용되지 않을 때는 입력 격자 자체를 DP 표로 수정할 수 있는 경우가 있습니다. 최소 경로 합 문제에서는 grid[i][j]를 해당 칸에 도달하는 최소 비용으로 덮어씁니다. 이렇게 하면 추가 공간을 O(1)로 사용할 수 있지만 입력이 손상됩니다. 항상 이 상충 관계를 면접관에게 설명하고 허용되는지 확인하세요. 입력을 보존해야 한다면 순환 배열 방식을 사용하세요.

def min_path_sum_inplace(grid):
    rows, cols = len(grid), len(grid[0])
    # Modify grid in-place (O(1) extra space, destroys input)
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue  # starting cell
            elif r == 0:
                grid[r][c] += grid[r][c-1]  # first row
            elif c == 0:
                grid[r][c] += grid[r-1][c]  # first column
            else:
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[rows-1][cols-1]

import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid)))  # 7

동전 교환에서 하향식과 상향식 비교

두 접근법 모두 동전 교환을 최적으로 해결하지만 실제 사용에서는 차이가 있습니다. 하향식은 작성하기 더 깔끔하고 실제로 도달 가능한 하위 문제만 계산합니다. 상향식은 주어진 동전으로 도달할 수 없는 금액도 포함하여 0부터 목표 금액까지 모든 금액을 계산합니다(이 금액들은 무한대로 남습니다). 희소한 문제(도달 가능한 상태가 적은 경우)에서는 하향식이 더 효율적이고, 밀집된 문제에서는 상향식의 추가 비용이 더 적습니다.

import functools

# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0: return 0
        if rem < 0: return float('inf')
        return 1 + min(dp(rem - c) for c in coins)
    r = dp(amount)
    return r if r != float('inf') else -1

# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change_top([1,5,6,9], 11))    # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2

고유 경로: 전형적인 2차원 DP

고유 경로(LeetCode #62)는 오른쪽이나 아래쪽으로만 이동하면서 m×n 격자의 왼쪽 위에서 오른쪽 아래까지 가는 경로의 수를 셉니다. 점화식은 간단합니다. dp[i][j] = dp[i-1][j] + dp[i][j-1]로, 위에서 오는 경로와 왼쪽에서 오는 경로를 더합니다. 기본 경우로 첫 번째 행과 첫 번째 열 전체에는 각각 정확히 1개의 경로만 있습니다(이동 방향이 하나뿐이기 때문입니다). 이 2차원 DP는 O(mn) 시간에 표를 채우며, 순환 행을 사용하면 O(n) 공간으로 줄일 수 있습니다.

def unique_paths(m, n):
    # dp[i][j] = number of paths to reach cell (i,j)
    dp = [[1] * n for _ in range(m)]
    # Base: first row and first column are all 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3

# O(n) space rolling row:
def unique_paths_opt(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

print(unique_paths_opt(3, 7))  # 28

빠른 확인

이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.

단원 복습

이 단원에서 배운 내용: 표 작성법을 사용한 상향식 DP와 의존성 화살표로부터 표를 채울 순서를 결정하는 방법, 순환 배열(O(mn)에서 O(n)으로)과 두 변수 추적(O(n)에서 O(1)으로)을 사용한 공간 최적화, 그리고 피보나치, 동전 교환, LCS, 집 도둑질, 최소 경로 합의 상향식 구현입니다. 다음으로 동전 교환과 최소 비용 계단 오르기 문제를 처음부터 끝까지 해결해 보겠습니다.

자주 묻는 질문

“표 작성을 이용한 상향식 DP” 강의는 무료인가요?

네 — “표 작성을 이용한 상향식 DP” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“표 작성을 이용한 상향식 DP”에서 뭘 배우나요?

하향식 해법을 반복적인 DP 표로 변환하고, 최근 몇 개의 값만 필요할 때 공간을 O(n)에서 O(1)로 줄입니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.

“표 작성을 이용한 상향식 DP” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← Coding Interview Prep(으)로 돌아가기