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

1. 속도 개선 아이디어

이전 코드에 추가할 수 있는 예외처리를 생각해보자.

 

• next_leaf가 destination을 넘어간다면, 더이상 진행할 필요가 없다(break)
• 피보나치 수에 destination이 있다면, 단 1번의 점프로 끝낼 수 있다
• 현재 점프 횟수가 최소 점프 횟수인지 비교(cur_jump >= min_jump)하지 말고,
  현재 점프에서 한번만 더 점프하면 최소 점프인지 확인(cur_jump + 1 >= min_jump)하는 형태로 수정하면
  q.push를 주일 수 있다
• 현재 위치가 도착지(cur_pos == destination)인지 비교하지 말고,
  현재 위치에서 도착지로 점프할 수 있는지 확인하도록 수정하면
  q.push를 줄일 수 있다
• Fib를 이용한 탐색을, Fib[2]부터 시작하면 좀 더 최적화 할 수 있다 (이전 코드에서는 Fib[0]부터 했다)

 

2. 코드 (C++)

#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)
    {
        if(n == destination) return 1;
        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 + 1 >= min_jump) continue;

            //arrived at the destination
            it = find(fib.begin() + 2, fib.end(), destination - cur_pos);
            if(it != fib.end())
            {
                min_jump = cur_jump + 1;
                continue;
            }

            //find a leaf to jump on
            for(size_t k = 2; 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(next_leaf >= destination) break;
                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. 결과