점프 게임(Jump Game)은 코딩 테스트와 알고리즘 학습에서 자주 등장하는 대표적인 그리디(Greedy) 기반 문제입니다. 이 글에서는 파이썬을 활용해 점프 게임 문제를 해결하는 방법을 단계별로 살펴보겠습니다.
문제 설명
음수가 아닌 정수로 이루어진 배열이 주어지며, 우리는 처음에 배열의 첫 번째 인덱스(0번 위치)에 서 있습니다. 배열의 각 요소는 해당 위치에서 최대로 점프할 수 있는 거리를 의미합니다. 즉, 값이 3이라면 한 번에 최대 3칸까지 앞으로 이동할 수 있습니다.
목표는 마지막 인덱스에 도달할 수 있는지를 판단하는 것입니다. 예를 들어 배열이 [2, 3, 1, 1, 4]라고 가정해 보겠습니다. 이 경우 출력은 True가 됩니다. 0번 위치에서 1칸 점프하여 1번 위치로 이동한 뒤, 다시 3칸 점프하면 바로 마지막 인덱스에 도달할 수 있기 때문입니다.
해결 전략: 뒤에서부터 거꾸로 탐색하기
이 문제는 앞에서부터 차례대로 확인하는 방식보다, 뒤에서부터 목표 지점을 갱신해 나가는 그리디 방식이 더 효율적입니다. 핵심 아이디어는 다음과 같습니다.
- 목표 지점(goal)을 배열의 마지막 인덱스로 설정합니다.
- 배열을 끝에서부터 시작 지점까지 역순으로 순회하면서, 현재 위치 i에서 목표 지점에 도달 가능한지 확인합니다. 즉,
A[i] + i >= goal이라면 해당 위치에서 목표에 도달할 수 있습니다. - 도달 가능하다면 목표 지점을 현재 위치 i로 갱신합니다. 이렇게 하면 목표가 점점 앞쪽으로 이동하게 됩니다.
- 모든 순회가 끝난 후 목표 지점이 0(첫 번째 인덱스)이라면 True, 그렇지 않다면 False를 반환합니다.
이 방식은 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적으로 동작합니다.
파이썬 구현 코드
아래 코드를 통해 실제 구현 과정을 더 쉽게 이해할 수 있습니다.
class Solution(object):
def canJump(self, nums):
n = len(nums) - 1
for i in range(n-1, -1, -1):
if nums[i] + i >= n:
n = i
return n == 0
ob1 = Solution()
print(ob1.canJump([2,3,1,1,4]))입력
[2,3,1,1,4]
출력
True
동작 원리 상세 분석
위 코드가 어떻게 동작하는지 단계별로 추적해 보겠습니다. 초기 목표 지점 n은 4입니다.
- i = 3일 때: nums[3] + 3 = 1 + 3 = 4 ≥ 4이므로 도달 가능 → n = 3으로 갱신
- i = 2일 때: nums[2] + 2 = 1 + 2 = 3 ≥ 3이므로 도달 가능 → n = 2로 갱신
- i = 1일 때: nums[1] + 1 = 3 + 1 = 4 ≥ 2이므로 도달 가능 → n = 1로 갱신
- i = 0일 때: nums[0] + 0 = 2 + 0 = 2 ≥ 1이므로 도달 가능 → n = 0으로 갱신
최종적으로 n이 0이 되었으므로 첫 번째 인덱스에서 출발하여 마지막 인덱스에 도달할 수 있으며, 함수는 True를 반환합니다.
마치며
점프 게임 문제는 그리디 알고리즘의 직관적인 사고방식을 익히기에 좋은 예제입니다. 뒤에서부터 목표 지점을 갱신하는 이 패턴은 유사한 경로 도달 가능성 문제에서도 널리 활용되므로, 꼭 익혀두시길 권장합니다.