치킨 날다

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

피자 박스가 N * M으로 쌓여 있습니다.

이 때 정면도와 측면도가 바뀌지 않도록 피자 박스를 제거 할 때, 최대 제거되는 피자 박스의 수를 구하는 문제입니다.

제가 선택한 방식은 다음과 같습니다.

0. 입력 받을 때 모든 상자 박스 높이의 합을 더합니다.

1. row 단위에서 최대 높이인 index를 vector에 저장합니다.

2. column 단위에서 최대 높이인 index를 vector에 저장합니다.

3. 단, 1과 2의 과정에서 vector 안에 동일한 index가 존재하면 저장하지 않습니다.

4. 저장된 indices의 상자 높이 만큼 연산된 상자 높이의 합에서 감산합니다.

처음 시도에는 오답을 받았습니다.

무엇이 문제인지 살펴보니, 상자 높이가 1B까지 입력 받고, 상자 뭉치 갯수는 1M개 만큼 입력을 받을 수 있었습니다.

입력값이 많을 경우, 상자 높이의 합이 int의 범위를 넘어설 수 있습니다.

그래서 상자 높이의 합을 int에서 unsigned long long으로 변경하였고, 정답을 맞출 수 있었습니다.

문제를 다 풀고 상자 순회를 한번에 해결할 수 있나 고민을 해보았습니다.

하지만 column과 row 단위에서 비교를 해 최대값을 뽑아야 하는 만큼,

둘 중 하나는 그 크기 만큼 최대값을 동시에 관리해야 했습니다.

이를 판단하는 것보다 차라리 순회를 두번 하는 것이 덜 복잡할 것 같습니다.

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

using namespace std;

int main()
{
    int column = 0, row = 0, input = 0;
    unsigned long long output = 0;
    vector<vector<int>> tower;
    vector<vector<int>> LiveIndex;
    cin >> column >> row;
    for (int i = 0; i < column; ++i)
    {
        tower.push_back(vector<int>(row));
        for (int j = 0; j < row; ++j)
        {
            cin >> input;
            tower[i][j] = input;
            output += input;
        }
    }

    for (int i = 0; i < column; ++i)
    {
        int max = 0, cIndex = 0, rIndex = 0;
        for (int j = 0; j < row; ++j)
        {
            if (max < tower[i][j])
            {
                cIndex = i;
                rIndex = j;
                max = tower[i][j];
            }
        }
        auto temp = vector<int>{ cIndex, rIndex };
        if (find(LiveIndex.begin(), LiveIndex.end(), temp) == LiveIndex.end())
        {
            LiveIndex.push_back(temp);
        }
    }
    for (int i = 0; i < row; ++i)
    {
        int max = 0, cIndex = 0, rIndex = 0;
        for (int j = 0; j < column; ++j)
        {
            if (max < tower[j][i])
            {
                cIndex = j;
                rIndex = i;
                max = tower[j][i];
            }
        }
        auto temp = vector<int>{ cIndex, rIndex };
        if (find(LiveIndex.begin(), LiveIndex.end(), temp) == LiveIndex.end())
        {
            LiveIndex.push_back(temp);
        }
    }
    for (const auto& iter : LiveIndex)
    {
        output -= tower[iter[0]][iter[1]];
    }

    cout << output << endl;
    return 0;
}

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

입력된 n개의 논문들의 인용 횟수를 받고 k | N(q(i) ≥ k) ≥ k, N(q(i) ≤ k) ≤ k (0 ≤ i ≤ n)인 k를 구하는 문제입니다.

제가 처음 선택한 풀이법은 다음과 같습니다.

1. 입력받은 리스트를 오름차순으로 정렬한다.

2. index를 순회하면서 q(i) ≥ i && q(i) ≤ n - i인지 확인을 한다.

3. 2의 조건이 만족할 경우, i 값을 저장한다.

4. 순회를 모두 마친 후 최후의 저장된 i값을 출력한다.

하지만 이 문제에는 몇가지 큰 문제점이 있었습니다.

1) Q-index 값이 입력된 논문의 인용 횟수 내로 제한된다.

2) 논문 인용 횟수가 논문 갯수보다 월등히 높으면 Q-index가 0으로 연산된다.

하지만 적은 것과 다르게 이를 알아내는데에는 6차례의 추가 시도가 필요했습니다.

그리고 결국 수정한 방안은 다음과 같습니다.

1. 입력받은 리스트를 오름차순으로 정렬한다.

2. 임의의 qindex를 Max(q(i))까지 순회한다.

3. 2의 순회에서 qindex보다 크거나 같은 q(i)를 갖는 index를 구한다.

4. index ≤ qindex && n - index ≥ qindex인 qindex를 저장한다.

5. 순회를 마치고 최종적으로 저장된 qindex를 출력한다.

문제 성격상 내림차순으로 정렬하여 qindex를 내림차순으로 순회하면 조금 더 빠르게 풀 수 있겠지만, 

이대로도 충분히 해결이 되기에 따로 수정을 하지는 않았습니다.

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

using namespace std;

int main()
{
    int size = 0, input = 0, output = 0, max = 0;
    vector<int> report;
    cin >> size;
    for (int i = 0; i < size; ++i)
    {
        cin >> input;
        report.push_back(input);
    }

    sort(report.begin(), report.end());
    max = report[size - 1];

    for (int qIndex = 0; qIndex < max; ++qIndex)
    {
        int index = 0;
        while (report[index] < qIndex)
        {
            ++index;
        }
        if ((index <= qIndex) && (size - index >= qIndex))
        {
            output = qIndex;
        }
    }

    cout << output << endl;

    return 0;
}

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

a / b 분수가 입력 되었을 때 x(i) = {x | a/b >= 1 / x 중 가장 큰 x}일 때 가장 마지막 x(i)를 출력하는 문제입니다.

처음에는 gcd와 lcm으로 연산을 하였으나, 시간이 너무 오래 걸렸습니다.

그 다음에 연산한 것은 a와 b의 각 차수 별 항에서 규칙성을 찾아서 적용하는 것입니다

min(i) = b(i) / a(i) + 1일 때, a(i + 1) = a(i) * min(i) - b(i), b(i + 1) = b(i) * min(i)를 적용하였습니다.

하지만 이 역시 시간 초과가 걸렸습니다.

솔직히 이보다 더 빠르게 만들 자신이 없었습니다.

입력을 c스타일 입력으로 바꾸기도 했으나, 여전히 문제가 해결되지 않았습니다.

그러다가 정답을 찾아 보는데, 어이 없는 문제점이 두개가 있었습니다.

하나는 반복문을 do-while이 아니라 그냥 while문으로 하는 것.

이렇게 되면 처음부터 분자가 1일 때는 자기 자신이 출력이 되는데 왜 성립하는지 몰랐습니다.

하지만 곧, 제가 문제를 잘못 읽었다는 것을 깨달았습니다.

이 문제는 자기 자신이 답이 될 수 있었습니다.

이 부분이 조금 뼈아팠습니다.

다른 하나의 문제는 연산이 다 끝나면 항상 gcd로 나누어 주는 것.

서로소를 곱하고 더하는데 최대공약수가 1보다 큰 경우가 발생을 하는가 싶었습니다.

이를 확인하기 위해 값을 최대로 올려보았더니, 곧바로 확인이 가능했습니다.

1에 근접하고 분모가 매우 큰 경우에는 종종 최대공약수가 1보다 큰 경우가 발생하기도 하였습니다.

문제의 해결법은 곧잘 찾아내지만, 아직은 세세하게 런타임을 줄이지는 못하는 것 같습니다.

매일 한문제씩 풀어나가면서 이런 실수를 최대한 줄이고, 문제 푸는 속도도 키우도록 하겠습니다.

#include <iostream>

using namespace std;

int GCD(const int& a, const int& b)
{
    return (b == 0) ? a : GCD(b, a % b);
}

int main()
{
    int testcase = 0, a = 0, b = 0, min = 0, gcd = 0;
    
    cin >> testcase;

    while (testcase-- > 0)
    {
        cin >> a >> b;        
        while (a != 1)
        {
            min = (b + a - 1) / a;
            a = a * min - b;
            b *= min;
            gcd = GCD(a, b);
            a /= gcd;
            b /= gcd;
        } 
        cout << b << endl;
    }

    return 0;
}

괄호가 지워진 길이 50 이하의 덧셈과 뺄셈만 존재하는 식의 최소값을 구하는 문제입니다.

숫자는 99999 이하이며, 0부터 시작 할 수 있습니다.

식은 숫자로 시작하고 숫자로 끝나며, 연산자가 두개 이상 연속으로 입력되지 않습니다.

최소가 나오는 방법은 간단합니다.

- 연산자를 기점으로 괄호를 쳐서 그 안의 연산을 우선적으로 해주면 됩니다.

구현 방법으로는 입력되는 식을 -로 split 해주고, 각 substring을 다시 +로 split한 뒤 연산을 해줍니다.

그리고 그 결과물을 다시 - 연산을 해주면 됩니다.

이 간단한 문제를 저는 처음 시작하는 substring에도

+ 연산이 포함될 수 있다는 것을 간과하여 3번이나 실패를 했습니다.

정답율도 50% 언저리였는데 참 슬펐습니다.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

const int StringToInt(const string& str)
{
    int ret = 0;
    for (unsigned int i = 0; i < str.size(); ++i)
    {
        ret *= 10;
        ret += str[i] - '0';
    }
    return ret;
}

const long long StringToList(const string& list)
{
    long long ret = 0;
    string temp;
    vector<string> pParse;
    stringstream ss(list);
    
    while (getline(ss, temp, '+'))
    {
        pParse.push_back(temp);
    }
    for (const auto& iter : pParse)
    {
        ret += StringToInt(iter);
    }
    return ret;
}

int main()
{
    long long ret = 0;
    string input, temp;
    vector<string> mParse;
    vector<int> mParseNum;

    cin >> input;
    stringstream ss(input);
    while (getline(ss, temp, '-'))
    {
        mParse.push_back(temp);
    }
    ret = StringToList(mParse[0]);
    for (unsigned int i = 1; i < mParse.size(); ++i)
    {
        ret -= StringToList(mParse[i]);
    }
    cout << ret << endl;

    return 0;
}

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

문제가 워낙 쉬워 보여 하나 더 풀어보았습니다.

S = {<x:y> | x = S % M, y = S % N}라고 했을 때 S를 구하라는 문제입니다.

간단히 두 Modular 연산 결과를 보고 원래 수를 구하라는 문제인데,

간단하게 하나씩 더해보았는데 정답을 맞출 수 있었습니다. 

단, x와 y중 하나를 기준으로 M과 N의 최소공배수 이상 더했음에도 답이 나오지 않으면

나올 수 없는 결과 값이므로 -1을 출력합니다.

사실 귀찮아서 최소공배수가 아니라 M * N까지 연산을 하였는데 아슬아슬하게 통과할 수 있었습니다.

이 문제를 언제 왜 못풀었나 살펴보니 4년 전이었습니다.

아마 대충 도전 했다가 놀았거나,

다국어로 되어 있는 걸로 보아 영어로 적힌 것을 해석하지 못하고 포기했던 것 같습니다.

#include <iostream>

using namespace std;

int main()
{
    int testcase = 0, M = 0, N = 0, x = 0, y = 0;
    cin >> testcase;
    while (testcase-- > 0)
    {
        int sum = 0;
        cin >> M >> N >> x >> y;
        while ((x != y) && (sum < (M * N)))
        {
            if (x > y)
            {
                y += N;
                sum += N;
            }
            else
            {
                x += M;
            }
        }
        if (sum >= (M * N))
        {
            cout << -1 << endl;
        }
        else
        {
            cout << x << endl;
        }
    }
}

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;
}

youtu.be/a8x3YHP0Rtk

다행히 오늘 안에 Teleport로 유의미한 결과를 이끌어낼 수 있었습니다.

다만, 항상 되는 것은 아니었습니다.

어떨 때에는 Teleport를 먼저 하고, 어떨 때에는 PlayMontage를 먼저 하는 것 같습니다.

또한 보는 것과 같이 너무 위쪽으로 Teleport 하는 것도 문제라고 생각합니다.

우선 RopeExitTop부터 Teleport 수치를 조정하고, 항상 Teleport가 발생한 뒤 Montage가 재생되도록 하려 합니다.

그 뒤에는 RopeExitBottom이 정삭작동 하도록 하고, 그 뒤에는 RopeEnterBottom.

마지막으로 RopeEnterTop이 작동되도록 하려 합니다.

만약 이 부분이 해결 된다면, Wall과 Ladder는 그대로 수정하면 될 것입니다.

다만 몇가지 문제점도 있었습니다.

먼저, Jump로 Exit 할 때 Climb와의 범위에서 벗어나면 Walk Animation이 재생되지 않는 경우가 발생했습니다.

또한 꼭대기에서 Climb Exit 한 이후에도 같은 현상이 발생했습니다.

마지막으로 정면으로 이동하면서 Jump 하는 도중에

Climb 하면 Climb Move Animation이 재생되지 않는 경우도 발생했습니다.

이런 버그적인 요소 외에, Animation이 재생되게 하기 위해 불필요한 부분도 구현된 점이 있습니다. 

하지만 우선은 기능 구현을 먼저 하고, 더 나은 코드로 수정을 할 계획입니다.

아직 오늘 개발이 끝난 것은 아니지만

더 이상 유의미한 진행 사항이 오늘 안에 나오지 않을것이라 판단하여 미리 일지를 적습니다.

Montage에 여차여차하여 Client에서만 Log가 출력되게 조정을 해보았습니다.

또한 Montage 하나하나에 조건을 달아 ExitClimb Montage가 재생되는지도 확인을 해보았습니다.

그 결과 ExitClimb가 호출이 되기는 하였으나, 재생은 이동 입력에 따라 여러 차례 발생하기도 했습니다.

그리고 그 횟수 만큼 Montage 재생 종료 이벤트가 발생했습니다.

제대로 작동하지 않는 이유는 Montage 재생 이벤트가 여러번 호출되어 반복적으로 Montage 앞부분이 재생 되다가, 

첫 Montage 종료 이벤트로 인해 Climb 상태가 해제가 되는 것으로 예상됩니다.

이에 대해 DisableInput을 해보았으나, 유의미한 결과를 얻지는 못했습니다.

두번째로, Montage가 재생될 때 Character를 Teleport 해보았습니다.

그런데 Montage가 여러번 재생되는 만큼, Teleport도 여러번 발생했습니다.

그리고 이 때마다 Character가 진동을 하는 것을 확인했습니다.

정면으로 100만큼 이동시킨다면 3번 발생 시 300을 이동하는 것이 아니라 0과 100을 3번 왕복합니다.

그리고 Character가 이동해 있기도 하고, 떨어지기도 합니다.

그나마 다행인 점은, 이 덕분에 Montage가 제대로 재생되고, 작동을 할 수 있다는 희망을 보기는 했습니다.

그러다가 Climb System 구현 영상을 하나 찾아 보았습니다.

https://www.youtube.com/watch?v=BKiSTM-G9pQ

길이가 길고, BP 위주로 하느라 정확히 파악은 못했으나, 

Notify를 통해 Event를 발생해서 진행하는 것 같습니다.

이에 영감을 받고 새로운 구조를 한번 시도해볼까 합니다.

그래서 현재 branch와 새로운 branch를 두고 왔다갔다 하면서 진행하고자 합니다.

마지막으로 한가지 버그를 발견했습니다.

Climb 상태에서 Exit 할 때 떨어지면서 이동을 하여 Climb로부터 완전히 벗어나면,

Animation이 정상 재생되지 않습니다.

요즘 이 프로젝트에 얼마나 시간을 할애해야 할지 고민이 생겼습니다.

Unreal 하나만을 바라보고 가기에는 방향을 잘못 잡았나 싶기도 하고, 

Unreal이 아닌 게임 개발에도 유용한 인재라는 것을 보이기 위해서는

Windows Programming과 DirectX를 사용한 것을 보여줘야 하지 않나 싶기도 합니다.

그래서 가능하면 현재 리팩토링을 끝내고 난 뒤에는,

Unreal 개발을 주 4회에서 2회로 줄이는 대신 Windows Programming을 적극적으로 해볼까 싶습니다.

오늘은 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곳에서 테스트를 봤으며 한곳에서 테스트를 추가로 볼 예정입니다.

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

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