격자의 고유 경로와 최소 경로 합
장애물이 있는 경우와 없는 경우의 고유 경로를 위해 2차원 DP 표를 채운 다음, 경로를 따라가는 값의 합을 최소화하도록 확장합니다.
격자의 고유 경로와 최소 경로 합은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
격자의 고유 경로
고유 경로(LeetCode 62)는 m×n 격자에서 오른쪽이나 아래쪽으로만 이동할 수 있을 때 왼쪽 위 모서리에서 오른쪽 아래 모서리로 가는 서로 다른 경로가 몇 개인지 묻습니다. 3×7 격자의 답은 28입니다. 핵심은 (i,j) 칸으로 가는 모든 경로가 (i-1,j)(위쪽) 또는 (i,j-1)(왼쪽)에서 와야 한다는 점이며, 이로부터 자연스럽게 2차원 DP를 정식화할 수 있습니다.
# 3x7 grid: robot starts at (0,0), goes to (2,6)
# Must make exactly 2 down-moves and 6 right-moves
# Total moves = 8, choose 2 for down = C(8,2) = 28
import math
print('Unique paths 3x7:', math.comb(3+7-2, 3-1)) # 28
print('Unique paths 3x3:', math.comb(3+3-2, 3-1)) # 6
print('Unique paths 2x2:', math.comb(2+2-2, 2-1)) # 2고유 경로를 위한 2D DP 표
dp[i][j]를 (i,j) 칸에 도달하는 경로의 수로 정의합니다. 첫 번째 행과 첫 번째 열은 모두 1입니다(맨 위 행이나 맨 왼쪽 열의 어떤 칸에 도달하는 방법은 하나뿐입니다). 나머지 칸에는 dp[i][j] = dp[i-1][j] + dp[i][j-1]을 적용합니다. 행 단위로 표를 채우면 답은 dp[m-1][n-1]입니다. 시간 복잡도는 O(m×n)이고 공간 복잡도는 O(m×n)이지만, O(n)으로 줄일 수 있습니다.
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
# First row and column stay as 1s (base cases)
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, 3)) # 6
print(unique_paths(1, 1)) # 1 (already at destination)O(n)으로 공간 최적화
dp[i][j]는 현재 행과 이전 행에만 의존하므로, 전체 2차원 표를 하나의 1차원 배열로 바꿀 수 있습니다. 모든 값을 1로 초기화한 다음 각 행에서 제자리 갱신을 수행합니다: dp[j] += dp[j-1]. i번째 행을 처리한 후에는 dp[j]에 2차원 표에서의 dp[i][j] 값이 저장됩니다. 이는 2차원 DP 문제에서 흔히 사용하는 최적화 패턴입니다.
def unique_paths_1d(m, n):
dp = [1] * n # initial row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] was dp[i-1][j], dp[j-1] is dp[i][j-1]
return dp[n-1]
print(unique_paths_1d(3, 7)) # 28
print(unique_paths_1d(3, 3)) # 6
# Or use math for O(1)
import math
print(math.comb(3+7-2, 3-1)) # 28고유 경로 II: 장애물
고유 경로 II(LeetCode 63)에서는 격자에 장애물(1로 표시된 칸)을 추가합니다. 장애물을 통과하는 경로는 유효하지 않으므로 obstacle[i][j] == 1이면 dp[i][j] = 0입니다. 그렇지 않으면 점화식은 동일합니다: dp[i][j] = dp[i-1][j] + dp[i][j-1]. 시작점이나 끝점이 막혀 있으면 즉시 0이 됩니다. 기본 사례를 신중하게 초기화해야 합니다. 첫 번째 행이나 열에서 1이 한 번 나타나면 그 행이나 열의 이후 모든 칸은 0입니다.
def unique_paths_with_obstacles(obstacle_grid):
m, n = len(obstacle_grid), len(obstacle_grid[0])
dp = [[0] * n for _ in range(m)]
# First row
for j in range(n):
if obstacle_grid[0][j] == 1: break
dp[0][j] = 1
# First column
for i in range(m):
if obstacle_grid[i][0] == 1: break
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
if obstacle_grid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
grid = [[0,0,0],[0,1,0],[0,0,0]]
print(unique_paths_with_obstacles(grid)) # 2최소 경로 합 문제
최소 경로 합(LeetCode 64)은 음이 아닌 정수로 채워진 m×n 격자에서 오른쪽이나 아래쪽으로만 이동하여 왼쪽 위에서 오른쪽 아래까지 경로에 포함된 모든 수의 합을 최소화하는 경로를 찾는 문제입니다. 예를 들어 [[1,3,1],[1,5,1],[4,2,1]]에서는 1→3→1→1→1 경로의 합이 7입니다. DP 상태는 고유 경로 문제와 같지만, 점화식에서는 덧셈 대신 최솟값을 사용합니다.
grid = [[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]
# Optimal path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)
# Values: 1 + 3 + 1 + 1 + 1 = 7
print('Expected minimum path sum:', 7)최소 경로 합 DP 구현
dp[i][j]를 (i,j) 칸에 도달하는 최소 비용으로 정의합니다. 기본 사례는 dp[0][0] = grid[0][0]입니다. 첫 번째 행은 dp[0][j] = dp[0][j-1] + grid[0][j]입니다(왼쪽에서 오는 방법뿐입니다). 첫 번째 열은 dp[i][0] = dp[i-1][0] + grid[i][0]입니다(위쪽에서 오는 방법뿐입니다). 일반적인 경우는 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])입니다. 이는 최적성 원리를 그대로 옮긴 것입니다.
def min_path_sum(grid):
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): # first row
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m): # first column
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] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7제자리 최소 경로 합
입력 격자를 수정해도 된다면 별도의 DP 표를 할당하지 않고 격자를 제자리에서 갱신할 수 있습니다. 이렇게 하면 입력을 제외한 추가 공간이 O(1)로 줄어듭니다. 면접관이 이 최적화를 묻는 경우가 있으므로, 수정하기 전에 입력을 변경해도 되는지 확인해야 합니다. 수정할 수 없다면 1차원 순환 배열 기법을 사용해 입력을 변경하지 않고 O(n) 공간으로 해결할 수 있습니다.
def min_path_sum_inplace(grid):
m, n = len(grid), len(grid[0])
# Mutate in place
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
if i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7삼각형 최소 경로 합
삼각형(LeetCode 120)은 각 단계에서 바로 아래 행의 인접한 숫자로 이동하는 삼각형 배열에서 위에서 아래까지의 최소 경로 합을 구하는 문제입니다. 아래에서 위로 올라가는 DP가 가장 깔끔합니다. 끝에서 두 번째 행부터 시작하여 각 칸에 바로 아래에 있는 두 칸 중 최솟값을 더합니다. 이렇게 하면 시작 인덱스를 추적할 필요가 없고, 답이 자연스럽게 꼭대기로 올라옵니다.
def minimum_total(triangle):
# Bottom-up: start from second-to-last row
dp = triangle[-1][:] # copy of bottom row
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
dp[col] = triangle[row][col] + min(dp[col], dp[col+1])
return dp[0]
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print(minimum_total(triangle)) # 11 (2+3+5+1)던전의 격자 DP
던전 게임(LeetCode 174)은 음수(피해)와 양수(회복) 값이 있는 격자의 오른쪽 아래 모서리에 갇힌 공주를 구하기 위해 필요한 최소 초기 체력을 구하는 문제입니다. 오른쪽이나 아래쪽으로만 이동해야 합니다. 핵심은 DP 표를 뒤에서부터(오른쪽 아래에서 왼쪽 위로) 채우면서 각 칸에 필요한 최소 체력을 계산하는 것입니다. 각 칸에서는 dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])을 적용합니다. 체력은 항상 1 이상이어야 합니다.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[0]*n for _ in range(m)]
# Fill from bottom-right
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
for i in range(m-2, -1, -1): # last column
dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
for j in range(n-2, -1, -1): # last row
dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
need = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
print(calculate_minimum_hp(dungeon)) # 7격자 DP 문제 비교
격자 DP 문제는 구조는 같지만 채우는 방향과 전이 연산이 다릅니다. 고유 경로는 덧셈을 사용해 모든 방법을 셉니다. 최소 경로 합은 최솟값을 사용해 최적화합니다. 던전 게임은 뒤에서부터 채워 미래에 필요한 체력을 계산합니다. 새로운 격자 DP 문제를 만났다면 다음을 스스로 물어보세요. (1) 각 칸은 무엇을 나타내는가? (2) 어느 방향으로 채우는가? (3) 이웃 칸을 어떤 연산으로 결합하는가? 이 세 질문에 답하면 전체 풀이가 드러납니다.
# Summary: Grid DP Patterns
#
# Problem Fill Dir Transition
# Unique Paths top-left dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Unique Paths II top-left same but 0 if obstacle
# Min Path Sum top-left dp[i][j] = grid[i][j] + min(above, left)
# Triangle bottom-up dp[col] = row[col] + min(dp[col], dp[col+1])
# Dungeon bottom-right max(1, min(right, down) - cell)
# Recognise the pattern, write the transition, verify with examples
print('Grid DP summary complete')격자 DP의 복잡도 요약
여기서 다루는 모든 격자 DP 문제는 O(m×n) 시간에 실행됩니다. 공간 복잡도는 전체 표를 사용할 때 O(m×n)에서, 1차원 순환 배열을 사용하면 O(n)까지 줄어들며, 격자를 제자리에서 수정할 수 있다면 추가 공간은 O(1)까지 줄어듭니다. 면접에서는 O(m×n) 풀이를 제시한 후 O(n) 공간 최적화도 언급하세요. 이는 풀이 간 절충점을 알고 있음을 보여 줍니다. 모든 문제에서 고유 경로의 수학 공식처럼 탐욕법으로 해결할 수 있는 간단한 방법이 있는지도 고려해야 합니다.
# O(n) space version of Min Path Sum
def min_path_sum_1d(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
dp[0] += grid[i][0] # first column: only from above
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_1d(grid)) # 7빠른 확인
이 레슨에서 배운 자료 구조 & 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.
레슨 요약
이 레슨에서는 다음을 배웠습니다. 고유 경로는 dp[i][j] = dp[i-1][j] + dp[i][j-1]로 2차원 표를 채우며 조합론을 사용하면 O(1)에 계산할 수 있습니다. 최소 경로 합은 같은 구조를 사용하지만 덧셈을 최솟값으로 바꾸어 최적 경로 비용을 구합니다. 또한 모든 격자 DP 문제는 칸마다 상태를 정의하고 전이 연산자(합, 최솟값, 최댓값)를 선택하는 패턴을 공유합니다. 다음으로는 두 수열에 2차원 DP를 적용해 최장 공통 부분 수열을 살펴보겠습니다.
자주 묻는 질문
“격자의 고유 경로와 최소 경로 합” 강의는 무료인가요?
네 — “격자의 고유 경로와 최소 경로 합” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“격자의 고유 경로와 최소 경로 합”에서 뭘 배우나요?
장애물이 있는 경우와 없는 경우의 고유 경로를 위해 2차원 DP 표를 채운 다음, 경로를 따라가는 값의 합을 최소화하도록 확장합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“격자의 고유 경로와 최소 경로 합” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 격자의 고유 경로와 최소 경로 합
- 최장 공통 부분 수열
- 편집 거리(Levenshte인)
- 2차원 DP 공간 최적화