[LeetCode 45] Jump Game II - 최소 점프 횟수 찾기 (탐욕법 + DP)

[LeetCode] Jump Game II - 최소 점프 횟수 찾기 (탐욕법 + DP)

문제 설명

LeetCode의 "Jump Game II" 문제는 배열의 시작점에서 끝점까지 최소한의 점프로 도달하는 문제입니다.

• nums[i]는 i번째 인덱스에서 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.
• nums[0]에서 nums[n-1]까지 도달하는 최소 점프 횟수를 구해야 합니다.
• 항상 도달 가능하다고 가정됩니다.

---

📌 문제를 풀면서 생각한 과정

처음에는 "모든 경우를 탐색하면서 최소 점프 횟수를 찾는 방법이 있을까?" 라고 고민했습니다.
먼저 동적 계획법(DP) 방식으로 접근했지만 O(N^2)의 시간 복잡도로 인해 비효율적이었습니다.
이후 **탐욕법(Greedy Algorithm)**을 적용하면 O(N)으로 해결할 수 있음을 발견했습니다.

---

📌 DP (동적 계획법) 풀이 - 초기 접근 방법

✅ 핵심 아이디어

1. 각 인덱스까지 최소 점프 횟수를 저장하는 dp 배열을 사용
2. dp[i]는 인덱스 i에 도달하는 최소 점프 횟수를 의미
3. dp[i] = min(dp[i], dp[j] + 1)
   • j에서 i로 이동할 수 있는 경우 (j + nums[j] >= i)
   • dp[i]는 dp[j] + 1 (즉, j에서 한 번 점프해서 가는 방법이 기존보다 더 작다면 업데이트)

---

📌 DP 코드

export function jumpDP(nums: number[]): number {
  const dp = new Array(nums.length).fill(Infinity);
  dp[0] = 0; // 시작점은 점프 0번

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
      dp[j] = Math.min(dp[j], dp[i] + 1);
    }
  }

  return dp[nums.length - 1]; // 마지막 인덱스까지의 최소 점프 횟수 반환
}

📌 실행 예제 분석

nums = [2,3,1,1,4]

초기 dp 배열:

[0, ∞, ∞, ∞, ∞]

i nums[i] dp 배열 변경

0	2	[0, 1, 1, ∞, ∞]
1	3	[0, 1, 1, 2, 2]
2	1	[0, 1, 1, 2, 2]
3	1	[0, 1, 1, 2, 2]
4	4	[0, 1, 1, 2, 2]

✅ 최소 점프 횟수: dp[4] = 2

📌 DP의 문제점

• 시간 복잡도: O(N^2) (이중 반복문)
• 공간 복잡도: O(N) (dp 배열 사용)
• 비효율적이며, 최적화 필요

---

📌 탐욕법(Greedy) 풀이 - 최적해 도출 과정

✅ 핵심 아이디어

1. 최대한 멀리 갈 수 있는 곳(farthest)을 계속 갱신한다.
2. 현재 점프 내에서 최대 도달 가능 위치(currentEnd)를 확인한다.
3. 현재 위치가 currentEnd를 넘어서면 점프 횟수를 증가시키고 새로운 currentEnd를 설정한다.
4. 이 과정을 반복하면 최소 점프 횟수로 마지막 위치에 도달할 수 있다.

---

📌 탐욕법(Greedy) 코드

export function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }

  return jumps;
}

📌 실행 예제 분석

nums = [2,3,1,1,4]

i nums[i] farthest currentEnd jumps 설명

0	2	2	0	0	0번 인덱스에서 최대 2번 인덱스까지 이동 가능
1	3	4	2	1	1번 인덱스에서 최대 4번 인덱스까지 이동 가능 (점프!)
4	4	8	4	2	마지막 인덱스 도달 (점프 완료)

✅ 최소 점프 횟수: 2

---

📌 탐욕법 vs DP 비교

방법 시간 복잡도 공간 복잡도 특징

DP (비효율적)	O(N^2)	O(N)	dp 배열을 활용하여 최소 점프 횟수 저장 (비효율적)
탐욕법 (Greedy)	O(N)	O(1)	최적의 방법, 빠름

✅ 탐욕법(Greedy)이 최적의 해결법! 🚀

---

📌 최종 정리

• DP는 직관적이지만, O(N^2) 복잡도로 비효율적
• 탐욕법(Greedy)은 O(N)으로 최적화 가능
• "현재 점프 내에서 가장 멀리 갈 수 있는 곳"을 선택하는 것이 최적의 해
• 추가 배열 없이 O(1) 공간복잡도로 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀