55. Jump Game ( medium ) / greedy algorithm(탐욕 알고리즘)

Jump Game

문제

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

0번 인덱스를 시작점으로, 각 인덱스의 값만큼 점프해서 마지막 인덱스까지 갈 수 있는지 판별하는 문제

풀이

먼저 접근한 방법은 길이가 nums와 같은 새로운 배열에 0을 할당한 뒤에,
nums와 같은 인덱스에서부터 인덱스의 값만큼 다음 인덱스에 1씩 더해주는 방법으로 생각했음.( 이해안돼도 상관X, 쓰레기같은 방법이였음.. )

const canJump = nums => {
    let arr = [];
    for ( let i = 0; i < nums.length; i++ ) {
        arr.push(0);
    }
    for ( let i = 0; i < nums.length-1; i++ ) {
        for ( let j = i+1; j <= i+nums[i]; j++ ) {
            arr[j]++;
        }
    }
    return arr.lastIndexOf(0) === 0 ? true :false;
};

하다가 말아서 정확히는 아니고 대충 위와같이 코드를 작성했고, 시간복잡도는 n^2이 나오는데 테스트케이스에 n^2으로는 통과할 수 없을 정도로 긴 케이스가 있어서, 고민하다가 검색해보니 Greedy Algorithm이라는 방법이 있어 코드를 보고 아래와 같이 작성하니 시간복잡도 n으로 통과.

const canJump = nums => {
    let lastPos = nums.length-1;
    for ( let i = nums.length-1; i >= 0; i-- ) {
        if ( i + nums[i] >= lastPos ) {
            lastPos = i;
        }
    }
    return lastPos === 0;
};

Greedy Algorithm이란 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

매트로이드라는 구조를 가진 문제에서는 그리디 알고리즘으로 항상 최적해를 찾을 수 있다.

위의 코드를 설명해보면

nums의 마지막 인덱스 값을 lastPos에 할당해놓고, 그 값부터 시작해서 lastPos를 0까지 도달하게 하는 것. 반복문 전체를 도는것이 아닌, 최적의 판단으로 횟수를 최대한 줄여준다.