치킨 날다

컨디션 관리를 못하여 중간에 뻗어버린 관계로 오늘은 부득이하게 쉬고 가겠습니다.

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

10M의 숫자를 3초 안에 오름차순으로 sorting 하는 문제입니다.

처음에는 간단하게 Insertion Sort를 시도 했으나, 시간이 초과되었습니다.

그 다음은 STL에서 제공하는 heap Sort를 시도 했으나, 이번에는 메모리가 초과하였습니다.

세번째는 입력 값이 10K 이하 자연수이기에 10K 사이즈의 Array를 두고, Array 값에 들어온 횟수를 저장해보았습니다.

Insertion Sort보다는 더 오래 갔지만 결국 시간이 초과되었습니다.

아마 Sort를 직접 구현하게 하려는 문제인 것 같습니다.

그래서 내일은 Merge Sort를 직접 구현해보려 합니다.

오늘은 Rope의 FSM 부분에 Blend by Bool로 분기를 나누어
Montage로 만든 ExitFromRope Animation들을 적용해보았습니다.

아직 완전히 정상적으로 작동하지는 않지만, 몇가지 공유할 사항들을 적어보고자 합니다.

우선 제가 한동안 Montage를 건들지 않는 사이에 Montage의 UI가 바뀌었습니다.

대체로 예전보다 더 한 눈에 잘 들어오지만, 예시를 보면서 따라하기에는 조금 불편했습니다.

FSM의 Cache 생성은 Animation Node 가장 밖에서만 가능하다는 것도 배웠습니다.

내부에서는 Cache 생성이 안떠서 원래 했던 것과 비교하기 위해 시도를 해보았는데,

가장 밖에서만 가능하다는 것을 발견하였습니다.

구현 방식은 Notify를 사용할까 하다가 Animation당 Montage를 따로 만들었습니다.

그리고 Montage의 종료를 AnimInstance의 OnMontageEnded에서 판단을 하였습니다.

해당 함수는 Montage가 종료 될 때마다 호출이 되는 함수이기에 불가피하게 if문으로 기능 여부를 판단하고 있습니다.

ExitClimbMontage인 경우, 기존에 호출되던 트리거 일괄 변경 함수인 ExitClimb가 호출이 됩니다.

그리고 기존의 ExitClimb가 호출되는 곳에서는 IdleType에 맞춰 적절한 ExitClimbMontage가 재생되도록 하였습니다.

하지만 현재 Montage 재생과 종료 시 함수는 호출이 되고 있는데, 애니메이션은 제대로 작동하지 않고 있습니다.

몇가지 예상되는 원인은 있습니다.

입력이 연속덕으로 들어가 재생이 연속적으로 되는 경우.

조건문이 잘못된 경우.

다음에는 입력을 제한해보려 합니다.

어제 필기시험을 연장 5시간정도 보고 곧바로 운동 하다 보니까 무언가를 할 시간이 없어서 따로 바로 쉬었습니다.

그러다보니 일지를 적지 못했습니다.

오늘은 Animation FSM을 살펴보며 Notify를 사용하지 않거나,

사용하더라도 Animation을 사용하는 방법이 있는지 찾아보았습니다.

결과적으로, Exit from Climb Animation은 Montage로 제작하여 Notify Event를 받아야 할 것 같습니다.

우선, FSM 변경으로 문제가 해결이 가능한지 고려를 해보았는데,

현재 Sub-FSM으로 묶여 있는 FullBodyMotion 밖에 복잡한 조건문을 받아 Blending 해야 했습니다.

그리고 이런 와중에서도 Animation 종료 시점은 확인해야 하기에 Notify 문제를 해결하지 못했습니다.

그 다음은 Animation에서 Notify Event를 받을 수 있는지 확인하는 것이었습니다만, 

이 역시 불가능 한 것 같습니다.

결국 이러나 저러나 Notify는 써야 하는데, 이걸 쓰려면 Montage를 써야 할 것 같습니다.

Climb 종류별로 Sub-FSM을 받는데, 이를 blend by bool로 분류하는 것을 생각 중입니다.

한가지 걱정인 것은 예전에 Blend by -를 여러개 중첩해서 쓰면 문제가 발생할 수 있다고 예전에 본 기억이 있습니다.

그리고 Montage와 Notify를 사용한지 굉장히 오래되어서 좀 걱정입니다.

오늘은 이왕 이렇게 된거 좀 더 쉬고, 월요일에 참고자료 보면서 만들어보려 합니다.

여러 테스트케이스를 추출해보고 값을 비교해 보았으나, 틀린 점을 발견하지 못했습니다.

물론 제출 시 계속 통과도 하지 못했습니다.

그래서 다른 사람의 답안을 보고 다시 작성하였습니다.

#include <iostream>
#include <array>
#include <algorithm>

using namespace std;

int main()
{
    int N = 0, temp = 0;
    array<int, 1000> Series;
    array<int, 1000> Sublength;
    Series.fill(-1);
    Sublength.fill(1);

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> temp;
        Series[i] = temp;
    }

    int sol = 1;
    for (int i = 0; i < N; ++i)
    {
        Sublength[i] = 1;
        for (int j = 0; j < i; ++j)
        {
            if (Series[i] > Series[j])
            {
                Sublength[i] = (Sublength[i] > Sublength[j] + 1) ? Sublength[i] : (Sublength[j] + 1);
            }
        }
        sol = (sol > Sublength[i]) ? sol : Sublength[i];
    }

    cout << sol << endl;

    return 0;
}

자신보다 앞의 있는 숫자가 자신보다 작을 경우,

그 숫자의 sublength + 1과 자신의 현재 sublength중 큰 수를 저장합니다.

그리고 현재의 solution과 비교하여 solution보다 클 경우, 그 값을 solution으로 저장합니다.

정석적인 DP 풀이인데, 이걸 보니까 제가 짰던 것이 DP가 아니라 Greedy Algorithm이었던 것 같습니다.

그 와중에 예외를 찾지 못했다는 점이 한탄스러울 뿐입니다.

오늘도 문제가 해결되지는 않았지만, 몇가지 확인해볼 수는 있었습니다.

1. State 이동 조건을 변경하였습니다.

원래는 ClimbTrigger의 Overlap 여하에 따라 이동 여부를 확인했는데,

생각해보니 이에 따라 Climb 상태에서 탈출할 때 발생하는 몇몇 trigger 값의 변경이 있었습니다.

그래서 이들 중 하나를 조건으로 잡았습니다.

2. 결국은 조건의 문제였습니다.

Exit State에 하나의 Animation만 붙여보기도 했고, Exit 발생 시 Pawn을 teleport 시켜보기도 했습니다만

Animation이 정상적으로 재생되지 않고 있습니다.

State 안 조건문 문제는 아닌 것 같습니다.

이렇게 적어두고 잠깐 생각을 해보니, Climb 상태에서 빠져나오는 순간 Climb 상태에서 빠져나옵니다.

이 때 FullBodyMotion도 false가 되는데, 이 때문에 뒤에 붙은 Animation이 재생되지 않는 것일 수도 있겠습니다.

금요일에 다른 회사 온라인 테스트가 있는 관계로, 내일은 개발을 하지 못할 것 같습니다.

토요일에 Notify를 사용하거나 하여 Animation 재생이 끝난 후에 ExitClimb가 발생하도록 구상을 해볼 예정입니다.

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

주어진 예시와 따로 작성한 예시가 모두 통과 했는데 런타임 에러가 발생했습니다. 

내일 예시를 몇개 더 적어보면서 문제점을 찾아볼까 합니다.

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

문제 항목이 Dynamic Programming이라 어떻게 연산을 할까 고민하다가 뒤에서부터 연산하는 방식을 생각했습니다.

먼저 각 index는 부여된 값과 더불어 index와 sublength를 가지고 있습니다.

index는 해당 위치 다음에 올 index, sublength는 자신 뒤의 수열의 길이를 뜻합니다.

index와 sublength는 기존 수열의 역순으로 연산을 합니다.

자신의 뒤 숫자의 값이 자신보다 크거나 같을 때, sublength와 index 값을 저장합니다.

단, 같은 조건에서는 숫자의 값이 작은 것이 우선권을 가집니다. 

이런 식으로 구현을 하는데 제시된 예시는 해결하나 추가로 생각한 예시를 해결하지 못했습니다.

뒷 숫자와 이어지지 않는 경우를 먼저 탐색하지 못 해서 문제가 생기는 것으로 예상되며,

내일 이 문제를 해결해보려 합니다.

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

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

아침 먹고 나니까 거짓말처럼 눈이 감겨서 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;
}