LeetCode - The World's Leading Online Programming Learning Platform
문제 파악
- n개의 계단이 있음
- 한 번에 1칸 또는 2칸 이동 가능
- n번째 계단에 도달하는 총 경우의 수 구하기
전형적인 dp 문제이다 (키워드 접근. 배우게 된 점에서 추가 정리 예정)
접근 방법
마지막 계단에 갈 수 있는 방법은 결국 두가지 뿐이다.
- 마지막 계단의 -1번째 계단에서 가는 방법
- 마지막 계단의 -2번째 계단에서 가는 방법
dp[i] = i번째 계단에 도달하는 방법의 갯수라 할때 아래처럼 base case 를 표현할 수 있다.
dp[i] = dp[i-1] + dp[i-2]
코드 구현
import java.util.Arrays;
class Solution {
private int[] memo;
public int climbStairs(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return dp(n);
}
private int dp(int n) {
// base case
if (n == 0 || n == 1) return 1;
// memoization: 이미 계산했으면 재사용
if (memo[n] == -1) {
memo[n] = dp(n - 1) + dp(n - 2);
}
return memo[n];
}
}
배우게 된 점
DP 문제는 애초에 출제 유형이 낮다고하니 여느 문제가 그렇듯 키워드를 보고 DP문제인지 연결하는 연습을 해두면 좋을것 같다. (응용이 되어 나오겠지만) 대표적인 문제 유형은 아래와 같다.
- 1차원 누적형 : 계단, 피보나치
- 2차원 격자형 : 최단 경로, Unique Paths
- 배낭형 : Knapsack
혹은 ‘마지막 행동 기준’을 잘 보거나, 마지막 행동 dp[i]가 ‘전 행동에 의존하는지’ 를 확인해보자.
혹은 완전탐색으로 문제를 해결한 후 최적화 시키는 방향으로 dp를 도입해보면 좋을것 같다.
'Programming > Algorithm' 카테고리의 다른 글
| LeetCode 62. Unique Paths (0) | 2026.02.21 |
|---|---|
| LeetCode 746. Min Cost Climbing Stairs (0) | 2026.02.20 |
| LeetCode 3. Longest Substring Without Repeating Characters (0) | 2026.02.18 |
| LeetCode 743. Network Delay Time (0) | 2026.02.17 |
| 감염된 폴더 문제 (0) | 2026.02.16 |