문제 개요
모든 요소가 양수인 정수 배열이 하나 주어진다고 가정해 봅시다. 시작 지점은 배열의 첫 번째 위치(인덱스 0)이며, 각 요소는 해당 위치에서 점프할 수 있는 최대 점프 길이를 의미합니다. 우리의 목표는 가장 적은 점프 횟수로 배열의 마지막 칸에 도달하는 것입니다.
예를 들어 배열이 [2,3,1,1,4]라고 한다면 정답은 2입니다. 인덱스 0에서 인덱스 1로 점프한 뒤, 다시 인덱스 4(마지막 인덱스)로 점프하면 총 2번의 점프만으로 목표에 도달할 수 있기 때문입니다.
풀이 전략: 그리디 알고리즘
이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재 점프로 도달 가능한 범위 내에서 가장 멀리 갈 수 있는 위치(farthest)를 계속 추적하고, 현재 위치가 점프 구간의 끝(end)에 도달할 때마다 점프 횟수를 늘려가는 것입니다.
구체적인 단계는 다음과 같습니다.
end := 0, jumps := 0, farthest := 0으로 초기화합니다.
i를 0부터 (nums의 길이 − 1)까지 반복합니다.
farthest := max(farthest, nums[i] + i)로 갱신하여 도달 가능한 최원거리를 추적합니다.
만약 i == end이고, i가 마지막 인덱스가 아니라면:
jumps를 1 증가시킵니다.
end := farthest로 갱신하여 다음 점프 구간을 설정합니다.
최종적으로 jumps를 반환합니다.
예제 코드
다음 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
class Solution(object): def jump(self, nums): end = 0 jumps = 0 farthest = 0 for i in range(len(nums)): farthest = max(farthest,nums[i]+i) if i == end and i != len(nums)-1: jumps+=1 end = farthest return jumps ob = Solution() print(ob.jump([2,3,1,1,4]))
입력
[2,3,1,1,4]
출력
2
동작 원리와 복잡도 분석
위 코드는 배열을 한 번만 순회하면서 각 위치에서 도달할 수 있는 최대 거리를 갱신합니다. 현재 인덱스가 이전 점프 구간의 끝(end)에 도달하면, 그 시점까지 계산된 최원거리(farthest)가 다음 점프 구간의 끝이 됩니다. 이 과정을 반복하면 자연스럽게 최소 점프 횟수가 누적됩니다.
시간 복잡도는 배열을 한 번만 탐색하므로 O(n)이며, 추가 공간 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 동적 계획법(DP)을 사용하는 O(n²) 풀이보다 훨씬 효율적이기 때문에, 실제 코딩 테스트에서도 이 그리디 접근법이 널리 권장됩니다.