- Authors
- Name
- Youngju Kim
- @fjvbn20031
FAANG 코딩 인터뷰 완전 정복: 동적 프로그래밍 패턴
동적 프로그래밍(DP)은 FAANG 인터뷰에서 가장 자주 출제되는 주제 중 하나입니다. 이 글에서는 인터뷰에서 반드시 알아야 할 DP 패턴을 체계적으로 정리합니다.
1. DP 접근법 체계
DP 문제 인식하는 법
동적 프로그래밍 문제는 두 가지 핵심 특성을 가집니다.
최적 부분 구조 (Optimal Substructure)
- 전체 문제의 최적해가 부분 문제의 최적해로 구성됩니다
- 예: 최단 경로 문제에서 A→C 최단 경로는 A→B + B→C 최단 경로의 합
중복 부분 문제 (Overlapping Subproblems)
- 같은 부분 문제가 여러 번 반복하여 등장합니다
- 피보나치 수열: fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2) → fib(3)이 중복
DP 문제 인식 신호
- "최대", "최소", "최장", "최단"을 구하는 문제
- "몇 가지 방법이 있는가?" 같은 카운팅 문제
- "가능한가?" 같은 가능성 판별 문제
- 배열, 문자열에서 부분 구조를 탐색하는 문제
Top-down vs Bottom-up 비교
# Top-down (Memoization) - 재귀 + 캐시
def fib_topdown(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo)
return memo[n]
# Bottom-up (Tabulation) - 반복문 + 테이블
def fib_bottomup(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
| 특성 | Top-down | Bottom-up |
|---|---|---|
| 구현 방식 | 재귀 + 메모이제이션 | 반복문 + 테이블 |
| 직관성 | 문제를 자연스럽게 분해 | 순서를 먼저 파악해야 함 |
| 공간 | 콜스택 오버헤드 | 테이블 공간만 |
| 속도 | 필요한 부분만 계산 | 모든 상태 계산 |
| 최적화 | 어려움 | 공간 최적화 가능 |
DP 설계 4단계
- 상태 정의: dp[i]가 무엇을 의미하는지 명확히 정의
- 점화식: dp[i]를 이전 상태로 표현
- 초기값: 기저 사례(base case) 설정
- 계산 순서: 의존 관계에 따라 계산 순서 결정
2. 1D DP 패턴
Climbing Stairs (LeetCode 70)
def climbStairs(n: int) -> int:
if n <= 2:
return n
# dp[i] = i번째 계단에 도달하는 방법의 수
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 공간 최적화: O(n) -> O(1)
def climbStairs_optimized(n: int) -> int:
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return curr
- 시간 복잡도: O(n)
- 공간 복잡도: O(1) (최적화 버전)
House Robber (LeetCode 198)
def rob(nums: list) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# dp[i] = i번째 집까지 훔칠 수 있는 최대 금액
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_optimized(nums: list) -> int:
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1
House Robber II (LeetCode 213)
원형 배열 처리: 첫 번째 집과 마지막 집을 동시에 선택 불가
def rob2(nums: list) -> int:
def rob_linear(houses):
prev2, prev1 = 0, 0
for h in houses:
prev2, prev1 = prev1, max(prev1, prev2 + h)
return prev1
if len(nums) == 1:
return nums[0]
# 첫 번째 집 포함 (마지막 집 제외) vs 마지막 집 포함 (첫 번째 집 제외)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
Maximum Product Subarray (LeetCode 152)
음수가 있으므로 최솟값도 추적해야 합니다.
def maxProduct(nums: list) -> int:
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# 음수 * 음수(최솟값) = 양수(최댓값)이 될 수 있음
candidates = (num, max_prod * num, min_prod * num)
max_prod = max(candidates)
min_prod = min(candidates)
result = max(result, max_prod)
return result
- 시간 복잡도: O(n)
- 공간 복잡도: O(1)
Jump Game I & II (LeetCode 55, 45)
# Jump Game I: 도달 가능한지 판별
def canJump(nums: list) -> bool:
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + jump)
return True
# Jump Game II: 최소 점프 횟수
def jump(nums: list) -> int:
jumps = current_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumps
Longest Increasing Subsequence (LeetCode 300)
# O(n^2) DP 방법
def lengthOfLIS(nums: list) -> int:
n = len(nums)
# dp[i] = nums[i]로 끝나는 LIS의 길이
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# O(n log n) 이진 탐색 방법
import bisect
def lengthOfLIS_nlogn(nums: list) -> int:
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
3. 2D DP 패턴
Unique Paths (LeetCode 62)
def uniquePaths(m: int, n: int) -> int:
# dp[i][j] = (0,0)에서 (i,j)까지의 경로 수
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]
# 공간 최적화: 1D 배열
def uniquePaths_optimized(m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]
Minimum Path Sum (LeetCode 64)
def minPathSum(grid: list) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 첫 행 초기화
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# 첫 열 초기화
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
Longest Common Subsequence (LeetCode 1143)
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp[i][j] = text1[:i]와 text2[:j]의 LCS 길이
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
- 시간 복잡도: O(m * n)
- 공간 복잡도: O(m * n), 최적화 시 O(min(m, n))
Edit Distance (LeetCode 72)
def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
# dp[i][j] = word1[:i]를 word2[:j]로 변환하는 최소 연산 수
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 기저 사례
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # 삭제
dp[i][j-1], # 삽입
dp[i-1][j-1] # 교체
)
return dp[m][n]
Coin Change (LeetCode 322)
def coinChange(coins: list, amount: int) -> int:
# dp[i] = 금액 i를 만드는 최소 동전 수
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Coin Change 2 (LeetCode 518)
def change(amount: int, coins: list) -> int:
# dp[i] = 금액 i를 만드는 방법의 수 (완전 배낭 문제)
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
0/1 Knapsack (배낭 문제)
def knapsack(weights: list, values: list, capacity: int) -> int:
n = len(weights)
# dp[i][w] = i번째 물건까지 고려할 때 무게 w 이하의 최대 가치
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # 선택 안 함
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# 공간 최적화: 역방향 순회
def knapsack_optimized(weights: list, values: list, capacity: int) -> int:
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
4. 구간 DP (Interval DP)
구간 DP는 배열의 특정 구간 [i, j]에 대한 최적 해를 구하는 패턴입니다. 핵심: dp[i][j] = 구간 i부터 j까지의 최적값
Burst Balloons (LeetCode 312)
def maxCoins(nums: list) -> int:
# 양 끝에 가상의 1 추가
nums = [1] + nums + [1]
n = len(nums)
# dp[i][j] = nums[i+1..j-1] 구간의 풍선을 모두 터뜨려 얻는 최대 동전
dp = [[0] * n for _ in range(n)]
# 구간 길이 2부터 시작 (인접한 두 경계 사이에 풍선이 없음)
for length in range(2, n):
for left in range(n - length):
right = left + length
for k in range(left + 1, right):
# k번 풍선을 구간 [left, right]에서 마지막으로 터뜨릴 때
coins = nums[left] * nums[k] * nums[right]
dp[left][right] = max(
dp[left][right],
dp[left][k] + coins + dp[k][right]
)
return dp[0][n-1]
- 시간 복잡도: O(n^3)
- 공간 복잡도: O(n^2)
Palindromic Substrings (LeetCode 647)
def countSubstrings(s: str) -> int:
n = len(s)
# dp[i][j] = s[i..j]가 팰린드롬이면 True
dp = [[False] * n for _ in range(n)]
count = 0
# 길이 1: 항상 팰린드롬
for i in range(n):
dp[i][i] = True
count += 1
# 길이 2
for i in range(n - 1):
if s[i] == s[i+1]:
dp[i][i+1] = True
count += 1
# 길이 3 이상
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
count += 1
return count
Longest Palindromic Subsequence (LeetCode 516)
def longestPalindromeSubseq(s: str) -> int:
n = len(s)
# dp[i][j] = s[i..j]에서 가장 긴 팰린드롬 부분 수열의 길이
dp = [[0] * n for _ in range(n)]
# 길이 1: 항상 1
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
Matrix Chain Multiplication 개념
행렬 A1 _ A2 _ ... * An의 곱셈 횟수를 최소화하는 문제입니다.
- dp[i][j] = 행렬 i부터 j까지 곱할 때의 최소 연산 수
- 점화식:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j])withi <= k < j
5. DP on Trees and Graphs
House Robber III (LeetCode 337)
트리에서 인접한 노드를 동시에 선택할 수 없을 때 최대 합을 구합니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob3(root: TreeNode) -> int:
def dfs(node):
if not node:
return (0, 0) # (선택 안 함, 선택함)
left_no, left_yes = dfs(node.left)
right_no, right_yes = dfs(node.right)
# 현재 노드를 선택하지 않으면: 자식들 각각의 최댓값 합
not_rob = max(left_no, left_yes) + max(right_no, right_yes)
# 현재 노드를 선택하면: 자식들은 선택 불가
rob = node.val + left_no + right_no
return (not_rob, rob)
return max(dfs(root))
Unique Binary Search Trees (LeetCode 96)
def numTrees(n: int) -> int:
# dp[i] = i개의 노드로 만들 수 있는 BST의 수 (카탈란 수)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for nodes in range(2, n + 1):
for root in range(1, nodes + 1):
left_count = dp[root - 1]
right_count = dp[nodes - root]
dp[nodes] += left_count * right_count
return dp[n]
6. FAANG DP 출제 경향
Google은 Hard 난이도의 DP 문제를 선호합니다.
- Burst Balloons, Regular Expression Matching, Wildcard Matching
- 상태 공간이 복잡한 문제 (3D DP 등)
- 구간 DP나 비트마스크 DP
준비 팁: 재귀에서 시작해 메모이제이션을 추가하고, 마지막에 Bottom-up으로 변환하는 과정을 연습하세요.
Meta (Facebook)
Medium 난이도의 실용적인 DP 문제가 많습니다.
- Coin Change, Longest Common Subsequence
- Decode Ways, Word Break
- 실제 제품 설계와 연관된 DP 문제
준비 팁: 코드 간결성과 설명 능력이 중요합니다. 점화식을 먼저 설명하고 코드를 작성하세요.
Amazon
실용적인 Medium DP 문제가 주로 출제됩니다.
- House Robber 시리즈, Jump Game
- Longest Increasing Subsequence, Maximum Subarray
- 시스템 디자인과 연계된 최적화 문제
준비 팁: 리더십 원칙과 함께 알고리즘 설명을 연결하면 좋습니다.
상태 공간 최적화
많은 2D DP를 1D로 최적화할 수 있습니다.
# LCS 2D -> 1D 최적화
def lcs_optimized(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
if m < n:
text1, text2 = text2, text1
m, n = n, m
# 이전 행만 유지
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[n]
최적화 원칙:
- 현재 행이 이전 행에만 의존 → 롤링 배열 (2D → 1D)
- 현재 값이 바로 이전 값에만 의존 → 변수 2개 (1D → O(1))
- 역방향 순회로 공간 절약 (0/1 Knapsack)
7. 연습 문제 퀴즈
퀴즈 1: 다음 중 dp[i] = max(dp[i-1], dp[i-2] + nums[i])로 정의되는 문제는?
정답: House Robber
설명: dp[i]는 i번째 집까지 고려할 때 훔칠 수 있는 최대 금액입니다. i번째 집을 선택하면 i-1번째 집은 선택 불가하므로 dp[i-2] + nums[i], 선택하지 않으면 dp[i-1]이 됩니다.
퀴즈 2: Coin Change 문제에서 dp[0] = 0으로 초기화하는 이유는?
정답: 금액 0을 만드는 데 필요한 동전 수는 0이기 때문입니다.
설명: dp[0] = 0은 기저 사례로, 금액 0은 아무 동전도 사용하지 않아도 됩니다. dp[1], dp[2], ...는 dp[0]을 기반으로 계산됩니다. 만약 dp[0] = 0이 아니면 모든 값이 잘못 계산됩니다.
퀴즈 3: LCS에서 dp[i][j] = dp[i-1][j-1] + 1 조건은 언제 성립하나?
정답: text1[i-1] == text2[j-1]일 때, 즉 현재 비교하는 두 문자가 같을 때
설명: 두 문자가 같으면 이전까지의 LCS에 현재 문자를 추가할 수 있으므로 dp[i-1][j-1] + 1이 됩니다. 다를 경우에는 max(dp[i-1][j], dp[i][j-1])을 취합니다.
퀴즈 4: Burst Balloons에서 k를 "마지막으로 터뜨리는 풍선"으로 정의하는 이유는?
정답: 독립적인 부분 문제로 분리하기 위해서입니다.
설명: k를 "처음 터뜨리는 풍선"으로 정의하면 터뜨린 후 이웃이 변경되어 부분 문제가 독립적이지 않게 됩니다. 반면 k를 "마지막 풍선"으로 정의하면 [left, k]와 [k, right] 구간이 각자 독립적으로 계산 가능하며, k가 마지막에 터질 때의 점수는 항상 nums[left] _ nums[k] _ nums[right]로 고정됩니다.
퀴즈 5: O(n log n)의 LIS 알고리즘에서 tails 배열이 의미하는 것은?
정답: tails[i]는 길이 i+1인 증가 부분 수열에서 가능한 가장 작은 끝값입니다.
설명: tails 배열은 실제 LIS를 나타내지 않고, 각 길이의 LIS가 끝날 수 있는 가장 작은 값을 저장합니다. 이를 통해 이진 탐색으로 새로운 숫자가 어디에 삽입될지 O(log n)에 찾을 수 있습니다. tails 배열의 최종 길이가 LIS의 길이입니다.
마무리
동적 프로그래밍은 처음에는 어렵게 느껴지지만, 패턴을 익히면 체계적으로 접근할 수 있습니다.
학습 순서 추천:
- Climbing Stairs, Fibonacci (DP 기초)
- House Robber 시리즈 (1D DP)
- Unique Paths, Minimum Path Sum (2D DP)
- LCS, Edit Distance (문자열 DP)
- Coin Change (배낭 문제)
- Burst Balloons (구간 DP)
- House Robber III (트리 DP)
인터뷰 팁:
- 항상 상태 정의부터 시작하세요
- 점화식을 말로 설명하고 코드를 작성하세요
- Brute force → Memoization → Tabulation 순서로 최적화하세요
- 시간/공간 복잡도를 항상 분석하세요