algo-wiki

Appearance

45. Jump Game II (LeetCode) ​

문제 링크 → LeetCode 45. Jump Game II

문제 설명 ​

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

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

예시 ​

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

아이디어 ​

최소 점프 횟수를 구하는 문제로, DP 또는 Greedy 방식으로 접근 가능.

방법 1: Bottom-up DP ​

  • dp[i]를 인덱스 i에서 끝까지 가는 최소 점프 횟수로 정의
  • 배열의 끝에서부터 거꾸로 계산
  • dp[n-1] = 0으로 초기화

방법 2: Greedy ​

  • 현재 탐색 구간 내에서 도달 가능한 가장 먼 위치를 계산하고, 범위를 벗어나면 점프 추가
  • O(n) 시간에 해결 가능
ts
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 방식) ​

ts
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. 각 위치에서 점프 가능한 거리만큼 다음 위치들을 탐색
  4. 도달 가능한 다음 위치들의 dp값 중 최소 + 1로 dp[i] 갱신

Greedy 방식 ​

  1. i + nums[i]로 가장 먼 위치(farthest) 갱신
  2. 현재 탐색 범위 끝(currentEnd)에 도달하면 점프 수 증가, 범위를 farthest로 갱신

시간/공간 복잡도 ​

방식시간 복잡도공간 복잡도
DPO(n^2)O(n)
GreedyO(n)O(1)

다른 풀이 방법과 비교 ​

  • Greedy: 매번 최대 범위를 업데이트하며 점프 횟수를 세는 방식. O(n)으로 가장 효율적.
  • DP: 직관적이지만 중복 계산이 발생하여 속도 면에서 불리.

핵심 요약 ​

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