Lesson 13. Fibonacci numbers - FibFrog #4 (속도 개선)

1. 속도 개선 아이디어

이전까지 점프 가능한 잎들만 따로 모아뒀었다. (leave)

leave는 특정 케이스에서는 탐색 횟수가 줄어든다는 장점을 가지지만, 극단적인 경우에서는 단점으로 작용한다.

예를들어 테스트 케이스가 다음과 같다면? {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

leave만드는 것이 의미 없어진다.

 

leave를 만들지 않고, vector A를 그대로 사용한다면 탐색에 대해서도 다시 생각해 볼 수 있다.

 

현재 탐색

IF leave[i] \( - \) leave[cur_pos] \( = \) fibonacci number THEN
    jump
END IF

 

수정 탐색

next_leaf = i + Fib[K]
IF A[next_leaf] = 1 THEN
    jump
END IF

 

현재 매개변수 조건을 보면, Vector A의 최대 크기는 100,000 이다.

Fib(26) = 121,393 이므로, 현재 위치에서 최대 25회만 탐색하면, 현재 위치에서의 탐색이 종료된다.

 

2. 코드 (C++)

leaves를 새롭게 정의하면서 세부적인 내용(Queue push 조건, 목적지 도착 확인 등)들이 조금씩 수정 됐다.

탐색 코드도 Fibonacci Vector로 반복문을 수행하게끔 수정했다.

#include <queue>

int solution(vector<int> &A) {

    int destination = A.size() + 1;

    //generate fibonacci numbers
    vector<int> fib = {};
    fib.emplace_back(0);
    fib.emplace_back(1);
    int M = 2;
    int n = fib[1] + fib[0];
    while(n <= destination)
    {
        fib.emplace_back(n);
        M++;
        n = fib[M - 1] + fib[M - 2];
    }

    //generate a leaves vector that contains the starting point
    vector<int> leaves = A;
    leaves.insert(leaves.begin(), 1);
    leaves.emplace_back(1);
    
    //Count the minimum number of jumps to the other side of a river
    queue<pair<int, int>> q = {}; // queue<current position, current jump>
    int min_jump = numeric_limits<int>::max();
    for(size_t i = 1; i < leaves.size(); i++)
    {
        if(leaves[i] == 0) continue;

        auto it = find(fib.begin() + 2, fib.end(), i);
        if(it == fib.end()) continue;

        q.push({i, 1});
        while(!q.empty())
        {
            int cur_pos = q.front().first;
            int cur_jump = q.front().second;
            q.pop();

            if(cur_jump >= min_jump) continue;

            //arrived at the destination
            if(cur_pos == destination)
            {
                if(cur_jump < min_jump) min_jump = cur_jump;
                continue;
            }

            //find a leaf to jump on
            for(size_t k = 0; k < fib.size(); k++)
            {
                //The leaf to jump on should be at a distance of a Fibonacci number
                int next_leaf = cur_pos + fib[k];
                if(leaves[next_leaf] == 0) continue;

                q.push({next_leaf, cur_jump + 1});
            }
        }
    }

    if(min_jump == numeric_limits<int>::max()) return -1;
    return min_jump;
}

 

3. 결과

이전(Killed. Hard limit reached)과 다른 TIMEOUT ERROR가 발생했다. 

또한 bad_alloc이 발생하는 것을 볼 수 있다.

아마도 Queue에 너무 많은 데이타를 넣어서, 메모리 할당 실패가 발생하는 것 같다.