치킨 날다

어제 코딩 테스트 보느라 오랜만에 커피를 마셨는데 그 때문인지 새벽에 한숨도 자지 못했습니다.

누워서 멀뚱멀뚱 거리기 애매해 새벽부터 운동 가고 조금 일찍 개발을 시작했는데,

아침 먹고 나니까 거짓말처럼 눈이 감겨서 2시간 정도 눈을 붙인 것 같습니다.

전반적으로 집중력이 좀 떨어지는 하루였습니다.

Exit Climb 부분의 Animation이 제대로 재생되지 않는 문제를 건드려보았습니다.

Animation 조건문이나 State 이동 조건 등을 만져보았는데 별 다른 소득을 얻지 못했습니다.

아무리 생각해도 조건이 틀린 것 같다는 생각이 들지 않습니다.

그래서 혹 무언가 잘못 생각한 것이 있는가 싶어 Overlap Trigger 값을 로그로 찍어보려 하는데,

Client에서만 출력을 해서 정확히 알아보고 싶은데 조건을 잘못잡고 있습니다.

또한 이전에 RPC 부분에서 실제 값과 로그가 찍히는 값의 순서 차이로 인해

명확한 값을 잡지 못하는 것도 발목을 잡는 요소 중 하나입니다.

우선 다음에는 조건문을 정확히 파악해서 제대로 된 로그를 찍어보고자 합니다.

그 뒤에 State 이동 조건이 정확한지 확인해볼 예정입니다.

만약에 조건문이 잘못 짜여졌다면 다행이지만,

조건문이 정상이라면 완전히 암흑으로 문제가 빠졌다는 것이기에 걱정이 좀 됩니다.

다음에는 좀 더 컨디션 조절을 해서 더 집중하고자 합니다.

내용에 앞서 글을 작성하는 이유를 간단히 적습니다.

몇 주 전, 여러 회사에 입사 지원서를 넣었고 그 중 한 회사의 온라인 코딩 테스트를 오늘 보게 되었습니다.

알고리즘에 대해서는 기본은 한다고 생각을 했는데 오늘 큰 실수를 두번 하여 4문제 중 2문제 밖에 맞추지 못했습니다.

이에 상당한 충격과 조금은 현실 직시를 하게 되었습니다.

원래는 화요일에 Baekjoon 사이트에서 모의 테스트를 한달에 한번 보려고 계획 했습니다만,

조금 더 시간을 투자해야 할 것 같아 월요일부터 토요일까지 하루에 한문제씩 풀어보려 합니다.

https://www.acmicpc.net/problem/11444

오늘 푼 문제는 [피보나치 수 6]입니다.

10^18 번째까지의 피보나치수를 1초 안에 연산하는 문제였습니다.

예전에 한번 풀어보려 했으나 실패하고, 그저께 다시 한번 도전 했다가 실패하고 오늘에서야 성공한 문제입니다.

처음에는 단순히 DP로 해결을 할 수 있을 줄 알았습니다.

하지만 이를 담을 수 있는 배열을 선언할 수 없어 DP를 사용할 수 없었습니다.

그 다음에는 실력 좋은 선배에게 조언을 구했습니다.

그러자 선배가 "피보나치에 메모리는 2개면 충분하다."라고 귀뜸해줬습니다.

아래차 항에서부터 윗차 항까지 연산을 하면서 덮어 쓰면 되기 때문입니다.

하지만 1초 안에 모든 연산을 할 수 없었습니다.

오늘은 위 두가지를 모두 실패하고

피보나치 수열의 윗차항에서 아랫차항으로 내려가면서 풀어내리면서 규칙을 찾아보았습니다.

그러자 한가지 규칙이 보였습니다.

피보나치 수열을 f(i)라 했을 때, 

f(n) = f(n -1) + f(n - 2) = 2f(n - 2) + f(n - 3)  = 3f(n - 3) + 2f(n - 4)..

이 때 

f(1) = f(2) = 1, f(3) = 2, f(4) = 3이므로 이를 위 식에 대입하면

f(n) = f(2)f(n - 1) + f(1)f(n - 2) = f(3)f(n - 2) + f(2)f(n - 3) = f(4)f(n - 3) + f(3)f(n - 4)...

이렇게 변합니다.

즉 f(n) = f(k + 1)f(n - k) + f(k)f(n - k - 1)이라는 식이 나옵니다.

이 때 연산을 가장 적게 할 수 있는 방법은 binary search. 즉 k = n / 2일 때입니다.

위 연산을 재귀함수로 풀고, memory로 set을 사용해 [k : f(k)]를 저장해 연산 횟수를 줄였습니다.

10^18승일 때 최대 연산이 540회만 발생하는 것입니다.

이 덕분에 오늘에서야 문제를 해결할 수 있었습니다.

코드를 보고 싶으신 분들은 아래 접은 글을 풀어서 보십시오.

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

const unsigned int FIBOLIMIT = 1000000007;

unsigned long long getFibo(map<unsigned long long, unsigned long long>& fibo, unsigned long long n)
{
    unsigned long long half = (unsigned long long)(n / 2);
    auto index = fibo.find(n);
    if (index != fibo.end())
    {
        return index->second;
    }
    else
    {
        unsigned long long a = (getFibo(fibo, half + 1) % FIBOLIMIT);
        unsigned long long b = (getFibo(fibo, n - half) % FIBOLIMIT);
        unsigned long long c = (getFibo(fibo, half) % FIBOLIMIT);
        unsigned long long d = (getFibo(fibo, n - half - 1) % FIBOLIMIT);
        fibo.insert(make_pair(n, (a * b + c * d) % FIBOLIMIT));
        return fibo[n];
    }
}

int main()
{
    unsigned long long n;
    map<unsigned long long, unsigned long long> fibo;
    fibo.insert(make_pair(0, 0));
    fibo.insert(make_pair(1, 1));
    fibo.insert(make_pair(2, 1));
    cin >> n;
    cout << getFibo(fibo, n) << endl;;
    return 0;
}

내일 온라인 코딩 테스트가 있어 오늘 하루 알고리즘 위주로 공부합니다.