치킨 날다

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

문제는 맞췄으나, 역시 혼자서는 맞추지를 못했습니다.

우선 어제 말한대로, 새로운 vector 선언을 최소화 한 Merge Sort를 구현하였습니다.

두 개의 subvector를 merge 할 때만 임시로 vector를 선언하였는데, 그럼에도 메모리가 부족하였습니다.

이 이상은 어떻게 줄일 방법이 없다고 판단하여 검색을 해보았습니다.

하지만 뜻밖에도, 문제는 다른 곳에 있었습니다.

대체로 다들 메모리와 시간 문제에 직면하는데,

다들 메모리 문제는 counting sort(입력값을 index로 하는 array에 갯수 저장)로 해결했습니다.

하지만 시간 문제는 알고리즘이 아니라 c스타일 array, c스타일 입출력.

그리고 입력의 최대값을 저장하여 출력 시 순회 횟수를 줄이는 것으로 시간을 줄였습니다.

대략적으로 시간복잡도를 계산하다보니 이런 부분은 신경쓰지 못한 것 같습니다.

다음에는 이런 부분까지도 항상 염두를 해두겠습니다.

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int size = 0, temp = 0, max = 0;
    int arr[10000] = { 0 };
    
    cin >> size;
    for (int i = 0; i < size; ++i)
    {
        scanf("%d", &temp);
        max = temp > max ? temp : max;
        ++arr[temp - 1];
    }

    for (int i = 0; i < max; ++i)
    {
        if (arr[i] > 0)
        {
            for (int j = 0; j < arr[i]; ++j)
            {
                printf("%d\n", i + 1);
            }
        }
    }

    return 0;
}

오늘은 Merge Sort를 구현해 보았습니다만 Memory 초과로 인해 통과하지 못했습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void MergeSort(vector<int>& List)
{
    if (List.size() < 5)
    {
        make_heap(List.begin(), List.end());
        sort_heap(List.begin(), List.end());
    }
    else
    {
        vector<int> front(List.begin(), List.begin() + List.size() / 2);
        vector<int> end(List.begin() + List.size() / 2, List.end());
        List.clear();
        MergeSort(front);
        MergeSort(end);
        for (unsigned int frontIndex = 0, endIndex = 0; frontIndex + endIndex < front.size() + end.size();)
        {
            if (frontIndex >= front.size())
            {
                List.push_back(end[endIndex++]);
            }
            else if (endIndex >= end.size())
            {
                List.push_back(front[frontIndex++]);
            }
            else
            {
                List.push_back(front[frontIndex] < end[endIndex] ? front[frontIndex++] : end[endIndex++]);
            }
        }
    }
}

int main()
{
    int size = 0, temp = 0;
    vector<int> list;
    
    cin >> size;
    for (unsigned int i = 0; i < size; ++i)
    {
        cin >> temp;
        list.push_back(temp);
    }

    MergeSort(list);
    
    for (const auto& iter : list)
    {
        cout << iter << endl;
    }
}

코드를 보면 알다싶이 재귀문에서 vector를 새로 생성하고 있습니다.

아마 이 때문에 문제가 생긴 것 같습니다.

내일은 이것을 하나의 Vector만 사용하여 Memory를 최소한으로 사용하는 Merge Sort로 고쳐보겠습니다.

Climb 상태에서 그 끝에 다다라서 상태 해제 될 때 Animation이 정상적으로 재생되지 않는 문제를 만져보았습니다.

오늘 시도한 방법은 DisableInput을 이용한 입력 제한이었습니다.

하지만 DisableInput을 해도 문제는 해결되지 않았습니다.

그러다가 문뜩 로그를 보니까, Montage 재생이 두번 출력되고,

Montage 재생 종료 이벤트도 두번 출력이 되는 것을 발견하였습니다.

Montage 재생 로그는 이동 입력 횟수에 따라 유동적이지만, 아무튼 최소 두번은 출력 되었습니다.

먼저, 두번 출력되는 것은 두 개의 Client가 모두 출력이 되서 그런 것으로 예상합니다.

그렇다면 Montage는 정상적으로 재생이 되고 있고, 정상적으로 종료 되고 있다는 결론에 도달합니다.

저는 여기서 Montage 재생이 정상적이지 못한 이유는

RootMotion을 해놓은 것이 모종의 문제가 있는 것으로 예상을 합니다.

실제 움직임도 움찔움찔 거리다가 Climb 상태가 해제 되는데,

중심을 움직이는 RootMotion이 벽에 부딛쳐서 재생이 안되는 것 같습니다.

내일은 우선 Montage가 정상 재생되는지 확인하기 위해 Montage End 로그에 

Exit Montage가 재생 중인지 조건을 걸어볼 예정입니다.

그리고 RootMotion쪽을 좀더 검색해볼 예정입니다.

당장 생각나는 방법은 Character를 teleport 하여 벽에 걸리지 않는 곳으로 보내고,

Montage가 정상 재생되는지 확인하는 것입니다.

만성 두드러기가 나서 항히스타민제를 복용하다보니 미친듯이 잠이 쏟아지고 있습니다.

게다가 최근에 여러 회사에 지원을 했고, 2곳에서 테스트를 봤으며 한곳에서 테스트를 추가로 볼 예정입니다.

아무래도 결과를 기다리는데 느낌이 좋은 곳이 있다 보니 긴장이 많이 풀어집니다.

하루에 개발에 투자하는 시간은 조금 줄어들겠지만, 그래도 빼먹는 날이 없도록 집중하겠습니다.

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

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

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

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

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

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

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

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

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

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

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

#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이었던 것 같습니다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

알고리즘에 대해서는 기본은 한다고 생각을 했는데 오늘 큰 실수를 두번 하여 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;
}

새로 구상한 FSM을 적용하려고 보았더니 이전에 적용했던 것과 완벽히 동일한 것이었습니다.

차이점이라면 Entry Point를 잘못 잡았다는 것...

테스트 해보면서 필요 없는 부분을 깎아 냈는데 여전히 원하는대로 움직이지는 않습니다.

Animation을 Loop 하지 않았음에도 정상적으로 작동하지 않는 것이 혼란스럽습니다.

내일은 Project Rebuild를 해보려 합니다.

그래도 안된다면 Enter Animation을 Montage로 적용해보려 합니다.

예전에 언리얼 커뮤니티의 한 분이 "Montage에 지원하는 기능이 많아 가능하면 Montage로 처리하는 것이 더 좋다."라고 했던 기억이 있는데, 이 부분에 대해 실제로 어떤지는 잘 모르겠습니다.

Montage를 쓰지 않아도 되는 곳에서도 Montage를 쓰는 편이 좋은지, 필요한 곳에서만 써야 하는 것인지.

Animation 부분은 유난히 깊이 있게 하는 사람이 적어 정보를 구하기 힘든 것 같습니다.

그리고 당분간 개발 시간이 줄어들 것 같습니다.

요일을 줄이는 것은 아니고, 개발 하는 날에 개발하는 시간을 조금만 줄일 예정입니다.

그 이유는 상반기 입사 지원을 했던 회사 중 한 곳에서 온라인 테스트를 보라는 메일을 받았기 때문입니다.

금주 일요일에 보는데, 아마 다른 회사들도 2주 내로 온라인 테스트를 보라는 메일이 올 것 같습니다.

이 때문에 본 프로젝트 개발 시간을 조금 줄이고 온라인 테스트 준비를 하려 합니다.

날이 더워서 개발 능률이 불과 일주일 전보다 절반 가량 떨어진 것 같습니다.

빨리 회사 붙어서 에어콘 빵빵한 곳에서 코딩하고 싶습니다.

https://redchiken.tistory.com/136

풀수 있는 문제는 다 풀었고 이 뒤로는 넘기려고 합니다.

해결법은 예측이 가는데 너무 오래 잡으니까 도저히 손이 가지를 않습니다.

앞으로는 이런 하나의 문제 세트를 풀 때는 한달 단위로 시간을 제한해야 할 것 같습니다.

못풀었던 문제 중 Party는 아직 마땅한 해결법을 찾지 못했습니다.

Dynamic Programming을 쓰면 어떻게 될 것 같은데 구조를 명확히 떠올리지 못했습니다.

Save the computer는 Dynamic Programming을 쓸 것도 없이, 반복적인 계산으로 해결이 될 것 같습니다.

다만 이 계산을 유추해내는 과정이 수학적으로 복잡한 연산을 취해줘야 합니다.

Scorched Earth는 일반적인 식 하나로는 유추가 되지를 않았습니다.

풍속이 없는 경우, 동일 고도에 있는 경우, 동일 위도에 있는 경우 등에 대해 모두 경우를 나누어서 생각해야 합니다.

그 결과 적절한 식을 구하기는 했으나, 이를 프로그래밍까지 할 기운이 남지 않았습니다.

Free Willy는 연습 문제 중 가장 어려운 문제였던 것 같습니다.

전형적인 Branch and Bound로, 제한 횟수보다 1 낮을 때에만 연산이 줄어드는 경우라 생각합니다.

이대로 구현을 한다면 정답은 구하겠지만, 제한 시간 내에 풀지는 의문입니다.

다음주에는 DP를 문제를 2개 정도 풀어보려 합니다.

문제는 역시 backjoon 사이트에서 구해올 것 같습니다.