[Algorithm][LeetCode][Medium][Python] 55. Jump Game

문제는 여기서 볼 수 있다.

 

 

Dynamic Programming을 사용하도록 만든 문제인데,

 

Solution 작성을 정말 잘 해놨다.

 

 

이 글은 해당 Solution을 한글로 풀어 작성했으며,

 

Solution 페이지에는 Java 코드만 있기 때문에

 

참고하여 Python 코드를 작성했다.

 

---

 

문제

입력 값으로 음수가 아닌 정수로 구성된

 

nums 라는 배열이 들어온다.

 

 

문제에서 요구하는 것은,

 

배열의 가장 첫 번째 인덱스부터 시작하여

 

배열의 가장 끝 인덱스까지 도달할 수 있는지의

 

여부를 return 하면 된다.

 

 

얼마만큼의 인덱스를 이동하는 지에 대한 것은,

 

최대 현재 위치한 인덱스의 원소만큼

 

오른쪽으로 인덱스를 움직일 수 있다.

 

 

예를 들어, [2, 3, 1, 1, 4]라는 배열이 있을 때,

 

0번째 인덱스(2)에서 1번째 인덱스(3)으로 이동 후,

 

1번째 인덱스(3)에서 4번째 인덱스(4)로 이동하면

 

배열의 가장 끝 인덱스로 이동이 가능하다.

 

 

하지만 [3, 2, 1, 0, 4]의 경우,

 

0번째 인덱스(3)에서 1번째, 2번째, 3번째 등

 

어디로 이동하더라도

 

절대 배열의 마지막 인덱스에는 도달할 수 없다.

 

 

nums 배열의 길이는 최대 3 * 10^4이며

 

각 원소는 최대 10^5기 때문에

 

효율적인 알고리즘이 필요하다.

 

 

풀이 소개

아래에서 나올 풀이에서

 

"good index", "bad index"와 같은 단어가 자주 나올텐데,

 

 

"good index"는 배열의 마지막 인덱스에 도달할 수 있는 인덱스,

 

"bad index"는 배열의 마지막 인덱스에 도달할 수 없는 인덱스다.

 

 

즉, 배열의 첫번째 인덱스가 "good index"라면

 

결과적으로 True를 return 하면 될 것이다.

 

 

아래의 네 가지 풀이를 소개할 예정이며,

 

풀이 과정이 점점 진화되며 더 나은 퍼포먼스를 볼 수 있다.

 

(1) Backtracking - Using Recursion

말이 Backtracking이지, 거의 노가다 해결법이다.

 

 

배열의 첫번째 인덱스부터 시작하여

 

모든 경우의 수를 따져본다.

 

 

이해하기 어려운 코드는 아니기에 바로 아래의 코드를 소개한다.

 

 

실행해보면 테스트 케이스 중 하나에서 시간 초과가 발생하여

 

좋은 방법은 아니다.

 

class Solution:
    def canJumpFromPosition(self, position: int, nums: List[int]) -> bool:
        if position == len(nums) - 1:
            return True
        
        furthestJump = min(position + nums[position], len(nums) - 1)
        # Old Way
        #for nextPosition in range(position+1, furthestJump + 1):
        # New Way
        for nextPosition in range(furthestJump, position, -1):
            if self.canJumpFromPosition(nextPosition, nums):
                return True
        return False
        
    def canJump(self, nums: List[int]) -> bool:
        return self.canJumpFromPosition(0, nums)
                

 

입력 배열의 길이를 N이라 했을 때,

 

시간 복잡도는 O(2^N)이며,

 

증명 방법은 Solution 페이지의 Appendix A를 참고하면 된다.

 

 

공간 복잡도는

 

재귀 때문에 stack 메모리를 사용하게 되어 O(N)이다.

 

(2) Top-down Dynamic Programming - Using Memoization Table

보통 Top-down DP는

 

Backtracking 방법을 optimize한 방법이라 여겨진다.

 

 

Backtracking 방법의 코드를 잘 보면,

 

우리가 특정 인덱스를 good 혹은 bad index라고 결정 지었을 때

 

그 결과는 절대 바뀌지 않는다는 것을 알 수 있다.

 

 

만약 그러한 결과들을 어딘가에 저장해 둔다면,

 

재귀 혹은 반복문을 돌면서 다시 계산할 필요가 없이

 

저장해둔 곳에서 쇽 가져오기만 하면 된다.

 

 

그렇기 때문에 Top-down DP는

 

Memoization Table,

 

즉, 메모 테이블을 사용하는 방법으로 소개되기도 한다.

 

 

이와 같은 Memoization 방법을 적용하기 위해서

 

"memo"라는 배열을 하나 두고,

 

입력 배열의 각 인덱스가 good인지 bad인지

 

판단하여 저장한다.

 

 

이때 저장 방식은 아래의 세 가지 중 하나로 한다.

 

 

- GOOD

 

- BAD

 

- UNKNOWN

 

 

알고리즘은 아래와 같다.

 

 

(a) memo 배열을 모두 UNKNOWN으로 초기화 시킨다,

 

  ; 단 마지막 인덱스는 언제나 본인에게 도달 가능하기 때문에 GOOD으로 저장한다.

 

 

(b) Backtracking 방법의 첫 번째 단계를 수정한다

 

  ; 파라미터로 넘어온 position 인덱스에 해당하는 memo 배열의 값을 확인한다.

 

  ; 만약 GOOD이면 True를, 아니라면 False를 return 한다.

 

  ; 나머지 단계는 Backtracking 방법과 같다.

 

 

(c) 현재 인덱스의 good / bad 인덱스 여부를 결정했다면, memo 배열에 저장한다.

 

 

코드는 아래와 같으며,

 

이 방법 역시 긴 테스트 케이스에서 시간 초과가 발생한다.

 

class Solution:
    def canJumpFromPosition(self, position: int, nums: List[int], memo: List[str]) -> bool:
        if memo[position] != 'UNKNOWN':
            return True if memo[position] == 'GOOD' else False
        
        furthestJump = min(position + nums[position], len(nums) - 1)
        for nextPosition in range(position+1, furthestJump + 1):
            if self.canJumpFromPosition(nextPosition, nums, memo):
                memo[position] = 'GOOD'
                return True
        
        memo[position] = 'BAD'
        return False
        
    def canJump(self, nums: List[int]) -> bool:
        memo = ['UNKNOWN'] * len(nums)
        memo[-1] = 'GOOD'
        return self.canJumpFromPosition(0, nums, memo)
                

 

시간 복잡도는 O(N^2) 이다.

 

만약 nums 배열을 순회하며

 

i번째 인덱스의 nums[i]가 'GOOD'인 원소를 찾기 위해

 

오른쪽으로 이동한다고 하면,

 

nums[i]는 최대 N(nums 배열의 길이)이 될 수 있기 때문이다.

 

 

공간 복잡도는 O(2N) = O(N)이다.

 

재귀를 사용하며 N을 사용하고,

 

memo 배열을 사용하며 N을 사용하기 때문이다.

 

(3) Bottom-up Dynamic Programming - Remove Recursion

Top-down DP에서 Bottom-up DP로 변환하려면

 

재귀를 제거하면 된다.

 

 

재귀를 제거하게 되면,

 

method stack의 오버헤드도 사라지고

 

caching의 효과도 얻을 수 있어서

 

대체로 더 나은 퍼포먼스를 보여준다.

 

 

더 나아가, 다음에서 소개할 네 번째 방법을 적용하기 위해

 

혹은 다른 문제에서도 더 나은 방법을 적용하기 위해

 

이러한 Bottom-up 방식의 해결 방법이 필요하다.

 

 

그럼 어떻게 재귀를 제거할까?

 

 

보통 Top-down DP 단계를 거꾸로 해나가면

 

재귀를 제거할 수 있다.

 

 

이 문제의 경우에서는

 

배열의 첫번째 인덱스부터 시작하는 것이 아닌,

 

배열의 가장 끝 인덱스부터 시작하는 것이다.

 

 

아래 코드를 보면 좀 더 명확하게 이해가 가능하다.

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        memo = ['UNKNOWN'] * len(nums)
        memo[-1] = 'GOOD'
        
        for position in range(len(nums) - 2, -1, -1):
            furthestJump = min(position + nums[position], len(nums) - 1)
            for nextPosition in range(position+1, furthestJump + 1):
                if memo[nextPosition] == 'GOOD':
                    memo[position] = 'GOOD'
                    break
        
        return memo[0] == 'GOOD'

 

하지만 아직까지도 타임 아웃이 발생한다.

 

 

여전히 (2)번 방법과 같은 이유로

 

시간 복잡도가 O(N^2)이기 때문이다.

 

 

공간 복잡도 역시,

 

(2)번 방법과 마찬가지의 이유로 O(N)이다.

 

(4) Greedy

대체 뭘 더 줄여야 할까?

 

 

Botttom-up DP 구현 코드를 다시 자세히 보자.

 

 

여전히 우리는 2중 for 문을 사용하고 있는 것을 볼 수 있는데,

 

안에 있는 for 문을 없앨 수 있다면

 

퍼포먼스가 굉장히 좋아질 것 같다.

 

 

안에 있는 for 문의 역할은

 

현재 위치한 index(position)의 다음 index(nextPosition)부터

 

조사를 시작하여 memo 배열의 nextPosition index 값이

 

'GOOD'인 것을 찾는다.

 

 

그럼 아예 'GOOD'인 index 값을

 

배열이 아닌, 단순 변수에 저장해두면

 

시간 뿐만 아니라 공간까지 줄일 수 있지 않을까?

 

 

그런 생각에서 탄생하는 코드가 바로 아래 코드이다.

 

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        lastPos = len(nums) - 1
        for idx in range(len(nums)-1, -1, -1):
            if idx + nums[idx] >= lastPos:
                lastPos = idx
        return lastPos == 0

 

'GOOD'인 index를 저장할 lastPos라는 변수 선언 후,

 

입력 배열의 가장 끝 인덱스를 저장해둔다.

 

 

가장 끝 인덱스는 언제나 가장 끝 인덱스,

 

즉, 본인에게 도달할 수 있기 때문에

 

'GOOD' index기 때문이다.

 

 

그 후, 입력 배열의 가장 오른쪽부터 시작하여

 

현재 index(idx)부터 nums[idx]만큼 더한 값이

 

lastPos보다 크다면,

 

'GOOD' index인 lastPos에 충분히 도달할 수 있다는 뜻이므로

 

idx 역시 'GOOD' index가 되기 때문에

 

lastPos를 idx로 최신화 시켜준다.

 

 

이런 식으로 배열의 첫 번째 원소까지 진행하면

 

우리가 원하던,

 

 

입력 배열의 첫 번째 원소부터 시작하여

 

입력 배열의 가장 끝 원소까지 도달할 수 있는지에 대한

 

결과를 알 수 있다.

 

---

 

DP 문제들은 볼 때마다 뜬구름 잡는 소리 같기도 하지만,

 

이런 훌륭한 풀이가 있는 것을 보면

 

정말 감탄이 나온다.

 

 

끝!