Jump Game
쉽지 않다.. 딱 원소 값 만큼만 점프할 수 있는게 아니라 최대 그 값 만큼 점프할 수 있는 거라서 경우의 수가 매우 많다.
백트래킹
일단은 타임아웃 나더라도 정직하게 모든 경우를 추적하는 백 트래킹 구현은 다음과 같다.
def canJump(nums: List[int]) -> bool:
def backtrack_from(pos):
if pos == len(nums) - 1:
return True
farthest = min(pos + nums[pos], len(nums) - 1)
for i in range(pos+1, furthest+1):
if backtrack_from(i):
return True
return False
return backtrack_from(0)
탑 다운 다이나믹 프로그래밍
원소 값의 모든 경우를 다 따져보기 전까지는 그 원소 값이 좋은지 안좋은지 모르기
때문에, 각 경우를 다음 세 가지로 나눈다: 아직 모름, 좋음, 나쁨.
def canJump(nums: List[int]) -> bool:
GOOD, BAD, UNKNOWN = 0, 1, 2
memo = [UNKNOWN] * len(nums)
def can_jump_from(pos):
if memo[pos] != UNKNOWN:
return memo[pos] == GOOD
farthest = min(pos + nums[pos], len(nums) - 1)
for i in range(pos+1, farthest+1):
if can_jump_from(i):
memo[pos] = GOOD
return True
# cannot reach from pos
memo[pos] = BAD
return False
memo[len(nums) - 1] = GOOD # the goal is good
return can_jump_from(0)
바텀 업 다이나믹 프로그래밍
비슷한 방법으로 태뷸레이션을 채워갈 수도 있다.
def canJump(nums: List[int]) -> bool:
n = len(nums)
GOOD, BAD, UNKNOWN = 0, 1, 2
memo = [UNKNOWN] * n
memo[n-1] = GOOD
for i in range(n-2, -1, -1):
farthest = min(i + nums[i], n-1)
for j in range(i+1, farthest+1):
if memo[j] == GOOD:
memo[i] = GOOD
break
return memo[0] == GOOD
그리디
이 문제는 탐욕법으로도 풀린다. 바텀 업 다이나믹 프로그래밍 알고리즘을 잘 보면,
어떤 주어진 위치로부터 GOOD 위치를 찾아야 하는데, 이는 그 중에서 가장 왼쪽
(break) 이다. 즉, 가장 왼쪽의 GOOD 위치들만 모아두면 될 것 같다.
따라서 오른쪽에서 왼쪽으로 거꾸로 훑어가면서, 각각의 위치에서 좋은 위치로 점프가 가능한지를 확인하면 된다.
def canJump(nums: List[int]) -> bool:
n = len(nums)
last = n - 1
for i in range(n-1, -1, -1):
if i + nums[i] >= last:
last = i
return last == 0