45. Jump Game II (LeetCode)

🔗 문제 링크 → LeetCode 45. Jump Game II

🧩 문제 설명

정수 배열 nums가 주어집니다. 각 요소 nums[i]는 현재 인덱스 i에서 최대로 점프할 수 있는 거리입니다. 배열의 첫 번째 인덱스에서 시작해 마지막 인덱스에 도달하기 위해 가장 적은 점프 횟수를 구하세요.

• 항상 도달할 수 있는 입력만 주어집니다.

예시

Input: nums = [2, 3, 1, 1, 4]
Output: 2
// 첫 번째 위치에서 2칸 점프 → 인덱스 1 (값 3)
// 인덱스 1에서 3칸 점프 → 인덱스 4 (도착)

💡 아이디어

이 문제는 최소 점프 횟수를 구하는 것이므로, DP (Dynamic Programming) 혹은 Greedy 방식으로 접근할 수 있습니다.

✅ 방법 1: Bottom-up DP

• dp[i]를 인덱스 i에서 끝까지 가는 최소 점프 횟수라고 정의합니다.
• 배열의 끝에서부터 거꾸로 계산하면서, i에서 도달 가능한 다음 위치들의 최소값을 참조하여 dp[i]를 갱신합니다.
• 마지막 인덱스는 도달한 상태이므로 dp[n-1] = 0으로 초기화합니다.

✅ 방법 2: Greedy

• 현재 탐색 구간 내에서 도달 가능한 가장 먼 위치를 계산하고, 그 범위를 벗어나면 점프를 추가합니다.
• 항상 가장 멀리 갈 수 있는 위치를 탐색하기 때문에 O(n) 시간에 해결할 수 있습니다.

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
}

✅ TypeScript 코드 (DP 방식)

function jump(nums: number[]): number {
  const n = nums.length
  const dp = Array(n).fill(Number.MAX_SAFE_INTEGER)
  dp[n - 1] = 0

  for (let i = n - 2; i >= 0; i--) {
    const maxJump = nums[i]
    for (let j = 1; j <= maxJump && i + j < n; j++) {
      dp[i] = Math.min(dp[i], dp[i + j] + 1)
    }
  }

  return dp[0]
}

🛠️ 코드 동작 원리

DP 방식

1. dp[n-1] = 0으로 마지막 위치는 점프가 필요 없음을 설정
2. i를 배열의 끝에서부터 시작해 0까지 이동
3. 각 위치에서 점프 가능한 거리(nums[i])만큼 다음 위치들을 탐색
4. 도달 가능한 다음 위치들의 dp값 중 최소에 +1 하여 dp[i] 갱신
5. dp[0]에 최소 점프 횟수가 저장되어 반환

Greedy 방식

1. i를 0부터 끝까지 순회하면서 i + nums[i]로 가장 멀리 갈 수 있는 지점(farthest) 갱신
2. 현재 탐색 범위가 끝나는 지점(currentEnd)에 도달하면 점프 수 증가 후, 탐색 범위를 farthest로 갱신
3. 마지막 인덱스를 포함할 때까지 반복

📊 시간 복잡도 & 공간 복잡도 분석

방식	시간 복잡도	공간 복잡도
DP	O(n^2)	O(n)
Greedy	O(n)	O(1)

🔄 다른 풀이 방법과 비교

• Greedy 방법: 매번 도달할 수 있는 최대 범위를 업데이트하면서 점프 횟수를 세는 방식. 시간 복잡도 O(n) 으로 가장 효율적입니다.
• DP 방법: 직관적이며 구조화된 접근이지만, 비효율적인 중복 계산이 발생할 수 있어 속도 면에서 불리합니다.

📝 핵심 내용 요약

• 문제 유형: 최소 횟수로 도달하는 경로 → 최적화 문제 → DP 또는 Greedy
• DP 방식: dp[i] = i에서 끝까지 가는 최소 점프 수
• Greedy 방식: 매 탐색 구간마다 가장 멀리 도달 가능한 위치를 선택
• 효율성 면에서는 Greedy 방식이 최적 (O(n))