Coding Interview Prep · 강의

경우의 수 디코딩과 경로 세기

decode-ways(숫자에서 문자로의 매핑)를 피보나치와 유사한 DP로 해결한 뒤, 단계 크기가 다양한 계단의 경로 수를 계산합니다.

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

디코딩 방법 문제

디코딩 방법(LeetCode 91)은 숫자 문자열을 문자에 대응시킵니다. 'A'=1, 'B'=2, ..., 'Z'=26입니다. 인코딩된 숫자 문자열이 주어졌을 때 서로 다른 디코딩 방법의 수를 계산합니다. 예를 들어 '12'는 'AB'(1+2) 또는 'L'(12)로 디코딩할 수 있으므로 2가지 방법이 있습니다. '226'은 'BZ'(2+26), 'VF'(22+6), 'BBF'(2+2+6)로 디코딩할 수 있으므로 3가지 방법이 있습니다. 앞에 0이 오면 일부 디코딩은 유효하지 않습니다.

# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)

s = '226'
print('Decodings for', s, ':', 3)  # Expected: 3

디코딩 방법의 DP 정식화

dp[i]를 s[:i]를 디코딩하는 방법의 수라고 하겠습니다. 기본 사례는 dp[0] = 1(빈 문자열은 한 가지 방법)이고, s[0] != '0'이면 dp[1] = 1, 그렇지 않으면 0입니다. 전이: s[i-1] != '0'이면 dp[i-1]을 더합니다(한 자리 디코딩). 10 ≤ int(s[i-2:i]) ≤ 26이면 dp[i-2]를 더합니다(두 자리 디코딩). 이는 유효성 검사와 결합된 사실상 피보나치 패턴입니다.

def num_decodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # empty prefix
    dp[1] = 0 if s[0] == '0' else 1
    
    for i in range(2, n + 1):
        # Single digit decode
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        # Two digit decode
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    return dp[n]

print(num_decodings('12'))   # 2
print(num_decodings('226'))  # 3
print(num_decodings('06'))   # 0

선행 0의 함정

디코딩 방법에서 가장 까다로운 부분은 0을 처리하는 것입니다. 단독 '0'은 디코딩할 수 없으므로(0에 대응하는 문자가 없기 때문입니다), s[i-1] == '0'이면 dp[i-1]을 더하지 않습니다. 두 번째 숫자인 '0'은 두 자리 수가 10 또는 20일 때만 유효합니다. '30'이나 '40'(및 그보다 큰 수)은 26을 초과하므로 유효하지 않습니다. 항상 10 ≤ two_digit ≤ 26을 확인해야 하며, two_digit ≤ 26만 확인해서는 안 됩니다.

def num_decodings(s):
    if not s or s[0] == '0': return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1  # s[0] != '0' guaranteed by guard above
    for i in range(2, n + 1):
        one = int(s[i-1])
        two = int(s[i-2:i])
        if one != 0: dp[i] += dp[i-1]  # valid single digit
        if 10 <= two <= 26: dp[i] += dp[i-2]  # valid two digits
    return dp[n]

print(num_decodings('10'))   # 1 (only 'J')
print(num_decodings('30'))   # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100'))  # 0 (dp[2]=1 then '00' invalid, single '0' invalid)

공간을 최적화한 디코딩 방법

피보나치와 마찬가지로 디코딩 방법의 점화식은 두 위치만 거슬러 올라가므로, 두 변수를 사용해 O(n) 공간을 O(1)로 줄일 수 있습니다. prev2(두 단계 전)와 prev1(한 단계 전)을 사용합니다. 각 단계에서 두 값으로부터 curr를 계산한 다음 값을 한 칸씩 이동합니다. 이는 피보나치에서 사용하는 두 변수 최적화와 동일합니다.

def num_decodings_o1(s):
    if not s or s[0] == '0': return 0
    prev2 = 1  # dp[0]
    prev1 = 1  # dp[1]
    for i in range(2, len(s) + 1):
        curr = 0
        if s[i-1] != '0':
            curr += prev1
        two = int(s[i-2:i])
        if 10 <= two <= 26:
            curr += prev2
        prev2, prev1 = prev1, curr
    return prev1

print(num_decodings_o1('226'))   # 3
print(num_decodings_o1('12'))    # 2
print(num_decodings_o1('0'))     # 0

계단에서 경로 세기

계단 오르기(LeetCode 70)는 한 번에 1칸 또는 2칸씩 오를 수 있을 때 n개의 계단을 오르는 방법이 몇 가지인지 묻습니다. 이는 정확히 피보나치 수열입니다: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5입니다. 한 번에 최대 k칸까지 오를 수 있는 경우에는 다음과 같이 일반화됩니다: ways(n) = sum(ways(n-1), ..., ways(n-k)).

def climb_stairs(n):
    if n <= 2: return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

for i in range(1, 8):
    print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!

걸음 수가 가변적인 계단 오르기

주어진 집합(예: {1, 3, 5})에서 원하는 수의 칸을 오를 수 있다면 점화식은 dp[i] = sum(dp[i-k] for k in steps if i-k >= 0)이 됩니다. 메모리를 효율적으로 사용하려면 크기가 max(steps)인 슬라이딩 윈도를 사용합니다. 이는 무제한 배낭 세기 변형으로, 각 걸음 수를 횟수 제한 없이 사용할 수 있습니다.

def count_ways(n, steps):
    dp = [0] * (n + 1)
    dp[0] = 1  # one way to stay at ground
    for i in range(1, n + 1):
        for step in steps:
            if i >= step:
                dp[i] += dp[i - step]
    return dp[n]

# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2]))    # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3]))    # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)

최소 비용으로 계단 오르기

최소 비용으로 계단 오르기(LeetCode 746)는 각 계단에 비용이 주어질 때 꼭대기에 도달하는 최소 비용을 구하는 문제입니다. 계단 i에서는 i+1 또는 i+2로 이동할 수 있습니다. 점화식은 dp[i] = cost[i] + min(dp[i-1], dp[i-2])입니다. 0번 계단이나 1번 계단에서 시작할 수 있습니다. 답은 min(dp[n-1], dp[n-2])입니다.

def min_cost_climbing(cost):
    n = len(cost)
    if n == 1: return cost[0]
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    return min(dp[-1], dp[-2])  # can start from step 0 or 1

print(min_cost_climbing([10, 15, 20]))      # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6

디코딩 방법 II: 와일드카드 숫자

디코딩 방법 II(LeetCode 639)에서는 1~9의 어떤 숫자로든 나타낼 수 있는 와일드카드 문자 '*'를 도입합니다. 이로 인해 유효한 디코딩 수가 크게 증가합니다. 단일 '*'는 숫자 1~9 중 하나이므로 9가지 방법을 만듭니다. 두 개의 '*'는 함께 9×9개의 두 자리 조합을 만들 수 있지만, 그중 26 이하인 조합만 유효합니다(11~19는 9가지, 21~26은 6가지이므로 '**'는 15가지). 경우를 신중하게 나누어 분석해야 합니다.

def num_decodings_ii(s):
    MOD = 10**9 + 7
    prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
    for i in range(1, len(s)):
        curr = 0
        c, p = s[i], s[i-1]
        # Single digit
        if c == '*': curr += 9 * prev1
        elif c != '0': curr += prev1
        # Two digits
        if p == '*' and c == '*': curr += 15 * prev2  # 11-19(9) + 21-26(6)
        elif p == '*': curr += (2 if c <= '6' else 1) * prev2
        elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
        else:
            two = int(p + c)
            if 10 <= two <= 26: curr += prev2
        prev2, prev1 = prev1, curr % MOD
    return prev1 % MOD

print(num_decodings_ii('*'))   # 9
print(num_decodings_ii('1*'))  # 18

피보나치와의 연관성

디코딩 방법과 계단 오르기는 모두 본질을 감춘 피보나치 계열 문제입니다. dp[i]가 dp[i-1]과 dp[i-2]에만 의존하는 DP는 모두 피보나치 형태이며 O(1) 공간으로 해결할 수 있습니다. 유효성 검사(0인 숫자, 걸음 수)는 어떤 전이가 활성화되는지를 바꾸지만, 두 단계만 거슬러 올라가는 기본 구조 자체는 바꾸지 않습니다. 이 계열을 한눈에 알아보는 능력은 면접에서 풀이 시간을 크게 줄여 주는 유용한 패턴입니다.

# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself:        dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs:         dp[i] = dp[i-1] + dp[i-2]
# Decode ways:             dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs:         dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber:            dp[i] = max(dp[i-1], nums[i] + dp[i-2])

# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
    prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1)  # 89

격자에서 경로 세기

관련된 세기 문제로, m×n 격자에서 오른쪽이나 아래쪽으로만 이동할 수 있을 때 왼쪽 위에서 오른쪽 아래로 가는 고유 경로가 몇 개인지 구하는 문제가 있습니다. 답은 이항 계수 C(m+n-2, m-1)입니다. DP 풀이에서는 dp[i][j] = dp[i-1][j] + dp[i][j-1]인 2차원 표를 채웁니다. 이는 피보나치 계단 문제의 2차원 버전으로, 각 칸은 바로 위 칸과 왼쪽 칸의 합입니다.

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    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]

# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
    return math.comb(m + n - 2, m - 1)

print(unique_paths(3, 7))         # 28
print(unique_paths_math(3, 7))    # 28
print(unique_paths(3, 3))         # 6

면접에서 흔히 빠지는 함정 요약

디코딩 방법에서 흔히 발생하는 실수는 다음과 같습니다. (1) '0' 하나만으로는 유효하지 않다는 사실을 잊는 경우입니다. dp[i-1]을 더하기 전에 항상 s[i-1] != '0'을 확인해야 합니다. (2) two_digit <= 26만 사용하고 two_digit >= 10을 확인하지 않는 경우입니다. '07'은 'G'로 디코딩되어서는 안 됩니다. (3) dp[n] 대신 dp[n-1]을 반환하는 경우입니다. 표는 1부터 인덱싱되므로 dp[n]이 전체 문자열에 해당합니다. DP 표가 입력보다 원소를 하나 더 가질 때는 배열 인덱스를 항상 다시 확인해야 합니다.

# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
    dp = [0] * (len(s) + 1)
    dp[0] = dp[1] = 1
    for i in range(2, len(s) + 1):
        if s[i-1] != '0': dp[i] += dp[i-1]
        two = int(s[i-2:i])
        # BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
        # Fix: require two >= 10
        if 10 <= two <= 26: dp[i] += dp[i-2]  # CORRECT
    return dp[len(s)]

print(buggy_decode('06'))   # 0 (correct, '0' alone invalid)
print(buggy_decode('07'))   # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27'))   # 1 (only 'BG', 27>26 so no two-digit)

빠른 확인

이 레슨에서 배운 자료 구조 & 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.

레슨 요약

이 레슨에서는 다음을 배웠습니다. 디코딩 방법은 한 자리(0이 아님)와 두 자리(10~26) 디코딩에 대한 유효성 조건이 있는 피보나치 유사 점화식을 따릅니다. 계단 오르기와 최소 비용 계단 오르기는 O(1) 공간으로 해결할 수 있는 순수한 피보나치 변형입니다. 또한 두 단계만 거슬러 올라가는 피보나치 계열임을 알아보면 면접에서 상당한 시간을 절약할 수 있습니다. 다음으로는 격자에서 고유 경로와 최소 경로 합을 구하는 2차원 DP를 살펴보겠습니다.

자주 묻는 질문

“경우의 수 디코딩과 경로 세기” 강의는 무료인가요?

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

“경우의 수 디코딩과 경로 세기”에서 뭘 배우나요?

decode-ways(숫자에서 문자로의 매핑)를 피보나치와 유사한 DP로 해결한 뒤, 단계 크기가 다양한 계단의 경로 수를 계산합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

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

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

“경우의 수 디코딩과 경로 세기” 강의는 얼마나 걸리나요?

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

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

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

이 강의의 모든 강의

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