Grid DP 악몽: 기본 사례를 매번 완벽히 해결하는 방법
Source: Dev.to
TL;DR
- 주제: 격자 기반 DP(경로, 장애물, 최소 비용)의 기본 경우 설정
- 면접 가치: 공식만 아는 것이 아니라 점화식 전제 조건을 이해하고 있음을 보여줍니다.
- 핵심 단계: 테이블 방향 선택, 첫 행/열 초기화, 장애물 처리, 점화식 적용
- 흔히 저지르는 실수: 장애물 뒤에 값을 0으로 초기화하지 않음,
i/j인덱스 혼동, 메모 기본값 무시 - 얻을 수 있는 것: 시각적 템플릿, TypeScript 코드, 흔한 실수, 연습 문제
초보자 친화적인 설명
왜 기본 경우가 모든 것을 좌우하는가
점화식은 이웃 셀이 유효할 때만 작동합니다. 첫 행이나 열이 잘못되면 아래 모든 셀이 오류를 물려받습니다. 기본 경우를 계약 설정처럼 생각하세요.
테이블 방향 선택하기
dp[i][j]가 왼쪽 위에서부터 행 i, 열 j를 의미하도록 할지 결정합니다. 하나의 규칙에 맞춰 코딩 전에 반드시 다시 선언하세요—이는 면접 커뮤니케이션 가이드에서 강조하는 습관입니다.
장애물은 시드(seed)를 바꾼다
첫 행이나 열에 막힌 셀이 하나라도 있으면, 그 뒤의 모든 셀은 0이어야 합니다. 대부분의 튜토리얼이 놓치는 함정이 바로 여기입니다.
단계별 학습 가이드
1) 상태와 점화식 정의하기
장애물이 있는 Unique Paths 문제: dp[i][j] = (i, j)까지의 경로 수.
점화식:
dp[i][j] = dp[i‑1][j] + dp[i][j‑1] if grid[i][j] is free2) 시작 셀 초기화하기
grid[0][0]이 막혀 있으면 답은 0입니다. 그렇지 않다면 dp[0][0] = 1로 설정합니다. 이 과정을 큰 소리로 말해보면 기억에 도움이 됩니다.
3) 첫 행과 첫 열 시드하기
첫 행을 j = 1 … m‑1까지 순회하면서: 셀이 열려 있고 이전 셀이 1이면 1을, 아니면 0을 넣습니다. 첫 열도 i에 대해 동일하게 수행합니다. 표로 시각화해 보세요.
4) 나머지 표 채우기
(1,1)부터 시작하는 각 셀에 대해, 막힌 경우 0을, 그렇지 않으면 위와 왼쪽 값을 더합니다. 설명은 간결하게 유지합니다.
5) 작은 격자로 검증하기
2×2, 3×3 격자에 (0,1) 혹은 (1,0)에 장애물을 두고 테스트합니다. 시드가 제대로 0이 되는지 표를 그려 확인하세요.
시각화 예시: 장애물이 있는 Unique Paths
function uniquePathsWithObstacles(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
// Start cell
if (grid[0][0] === 1) return 0;
dp[0][0] = 1;
// First row
for (let j = 1; j < cols; j++) {
dp[0][j] = grid[0][j] === 0 && dp[0][j - 1] === 1 ? 1 : 0;
}
// First column
for (let i = 1; i < rows; i++) {
dp[i][0] = grid[i][0] === 0 && dp[i - 1][0] === 1 ? 1 : 0;
}
// Rest of the table
for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
if (grid[i][j] === 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[rows - 1][cols - 1];
}첫 행·열에서 장애물이 나타나면 전파가 멈추고, 그 아래 모든 셀은 0이 된다는 점에 주목하세요.
실전 준비 전략
손으로 표 그리기
4×4 격자를 다양한 장애물 배치로 스케치하고 직접 채워 보세요. 손으로 직접 해보면 시드 규칙을 코드보다 빠르게 체득할 수 있습니다.
다른 방향 시도하기
행 우선(row‑major)과 열 우선(column‑major) 두 가지 채우기를 모두 연습하세요. 선택 이유를 설명하는 것은 면접에서 큰 플러스 포인트이며, AI 준비 프리머와도 연결됩니다.
최소 비용 변형 추가하기
합을 min(top, left) + cost[i][j] 로 바꾸어 보세요. 시드 로직은 동일하므로 기본 경우가 문제 유형을 초월한다는 점을 강화할 수 있습니다.
가벼운 가이드 활용하기
LeetCopilot 같은 도구는 초기 시드에서 장애물을 놓쳤을 때 알려줘, 잘못된 점화식에 시간을 낭비하기 전에 경고해 줍니다.
피해야 할 흔한 실수
- 시작 셀이 막혀 있는 경우를 놓치는 것 – 항상
grid[0][0]을 확인하고 필요하면 바로0을 반환하세요. - 장애물 뒤에도 1이 계속 이어지는 경우 – 첫 행·열에서 장애물을 만나면 그 뒤 모든 셀은
0이어야 합니다. - 인덱스 혼동 –
dp[i][j]가 행i, 열j를 의미한다는 규칙을 일관되게 유지하세요. - 기본값을 1로 초기화하는 것 –
dp를 1로 채우면 장애물이 0으로 바뀌지 않아 오류가 발생합니다. 처음엔 0으로 채우고 의도적으로 시드하세요.
FAQ
기본 경우가 올바른지 어떻게 확인하나요?
시드 후 첫 행·열을 확인하세요. 장애물이 정확히 반영돼 있어야 나머지를 채울 수 있습니다.
격자 DP 전에 무엇을 연습하면 좋을까요?
2D 배열에 익숙해지고, climbing stairs 같은 1D DP를 먼저 마스터하세요.
격자 DP가 면접에서 중요한가요?
네. 경로, 비용, 카운팅 문제에 자주 등장하며, 기본 경우의 명확성을 자주 평가합니다.
1D 롤링 배열로 바꿀 수 있나요?
가능하지만, 기본 경우가 정확히 구현된 뒤에만 적용하세요. 첫 행·열 로직은 그대로 유지됩니다.
결론
격자 DP에서 기본 경우를 정확히 잡아야 오류가 연쇄적으로 퍼지는 일을 방지할 수 있고, 면접관에게 기본 원리부터 생각한다는 인상을 줄 수 있습니다. 시작 셀을 신중히 시드하고, 장애물 뒤는 0으로 만들면 점화식이 기대한 대로 동작합니다.
코딩 인터뷰 준비와 LeetCode 패턴 마스터를 돕는 AI 어시스턴스를 찾고 있다면, LeetCopilot을 확인해 보세요.