240407: Unity + C# 현황, 알고리즘 디펜스는 덤

2024-04-07

TL;DR:

• 대학교를 중퇴했다.
• 학점은행제를 시작했다.
• Unity 공부를 했다.
• PS 알고리즘 현상유지를 했다.

오늘은(지금까지는)

오늘은(지금까지는) 알고리즘 공부보다는 현상 유지를 위해서 PS 업다운 랜덤 디펜스를 하루에 한판정도 했다.
그리고, Unity 공부에 집중했다. 인터넷에 무료로 풀린 오픈 강의가 많아서 큰 도움이 됐다.

C# 이라는 언어가 Java와 C++의 영향을 받은 언어인만큼, C++과 Java에 익숙한 나에겐 접근하기 쉬웠다.

Unity 공부를 시작한 이유는 단순히 인디 게임 개발을 하고 싶어서도 있고, 곧 우리의 세계를 덮쳐올 AI가 게임 업계 진출은 그나마(조금이라도) 늦을 것 같다고 생각해서다. (정답이 있는 SW 개발보다는, 정답이 없고 개발과 구현 방향이 창의력 + 인간 지능 위주로 돌아가는 게임이 유리하다고 생각했다)

만약 게임 업계 취업을 위해서라면 Unreal Engine을 공부해야겠지만, 취업보단 당장 만들고 싶은 게임을 만들면서 흥미를 느끼고 싶어 인디 개발 위주인 Unity를 선택했다.

Unity 에서는...

• Unity 플랫폼의 기초 조작, 기능들을 배웠다.
• 각 Object에 Components를 자유롭게 추가해서 기능을 넣을 수 있는 게 인상 깊었다.
• Rigidbody component로 이미 구현된 물리법칙을 쉽게 적용할 수 있다.
• Collider로 말 그대로 '히트박스'를 설정할 수 있다.
• Unity에서 제공하는 Prefabs로 Object를 저장해놓고 필요할때마다 코드로 소환할 수 있다.
• Multiple Sprites를 slice하고 관리하는 방법에 대해서 배웠다.
• Unity에서 C#에 제공하는 [SerializeField] 로 Unity UI에서 private 변수에 접근할 수 있음을 배웠다.
• 키보드 제어, 마우스 제어를 코드로 설정하는 방법과 transform.position으로 오브젝트의 위치를 관리할 수 있음을 배웠다.
• 3차원 공간에서의 오브젝트를 Vector3 구조체에 관리함을 배웠다.
• Unity에서 제공하는 Quaternion.identity 을 알아보다가 쿼터니언에 대해서도 알게 되었는데...

Quaternion 이란?
 - 유니티에서 사용되는 각도의 단위이자 회전을 표현하기 위해 사용되는 구조체(Struct)  
 - 수학적인 용어로 복소수 4차원 벡터(Four-Deminsional Complex Number)  

각도를 4개의 원소(x, y, z, w)로 표현한다.
 - 우리가 90도, 45도 등의 표현은 오일러 각(Euler Angle)이다.

Quaternion을 사용하는 이유
 - 오일러 각은 회전 시킬 때 X, Y, Z 축을 차례대로 회전 시키는데 X, Y, Z 축 중 2개의 축이 겹쳐 졌을 때 어느 축으로도 회전되지 않고 잠기는 현상이 발생한다. (Gimbal Lock)
 - 유니티에서는 이 짐벌락 현상을 해결하기 위해 세 축을 차례대로 회전시키는 것이 아닌, 세 축을 동시에 회전시키는 방식을 사용하고 있다(Quaternion)
 - 따라서 Unity에서 Object를 Rotate할 때 내부에서 Quaternion으로 자동 변형된다.

이외에도 많은 것을 배웠는데 인상 깊었던 건 이 정도.

지금은 2D에서 드래곤 플라이트와 비슷한 류의 연습 게임을 만들어보고 있다. 키보드/마우스 조작으로 총알을 발사하면서 위에서 내려오는 Enemy를 없애는 게임.

비록 지금은 초급 수준이지만 머릿속에 있는 아이디어를 그대로 시각화해서 보여주고, 재밌게도 만들 수 있는게 게임 개발의 묘미가 아닐까 한다. 그리고 코딩을 많이 했어서 그런지 개발에 딱히 어려운 부분이 없고 필요한건 바로 찾아나가면 되는거라서 막막함도 느껴지지 않는다. (아직까진, 나중에 게임 기획하고 DB 설계하려면 머리 좀 아프겠다..)

 

Unity 게임 개발 화면

---

백준 업랜디

알고리즘 업다운 랜덤 디펜스는 하루를 시작하는 느낌 정도로 가볍게 한판씩 했다.
업다운 랜덤 디펜스의 규칙은 임의 티어의 문제가 나오고, 맞추면 그 문제의 티어보다 한 단계 높은 문제가 나온다. 반대로 틀리면 틀린 문제보다 한 단계 낮은 문제가 나온다. 이렇게 계속 반복하는 규칙의 알고리즘 게임이다 (내가 nextcord.py로 개발했고, 현재 디스코드 봇으로 운용중이다.)

계속 해보니까 실버 1쯤에서 자꾸 미끄러진다.
최근 3문제를 복기해보겠다.

이친수 (실버 3 | 2193)

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

이친수 문제는 딱 봐도 Dynamic Programming을 이용한 문제였다. 랜덤으로 이 문제를 받자마자 그동안 갈고 닦았던 기초 DP.. 를 보여줄 수 있나 ?! 라고 생각했는데. 정말 다행히도 지금까지의 공부는 헛되진 않았던 것 같다.

dp[i][j] = c 를 길이가 i고, 마지막 수가 j인 이친수의 개수 c로 두고 풀었다.
이친수는 0으로 시작하지 않기 때문에 먼저 기저 사례를 다음과 같이 설정할 수 있다.

    // BASE CASE
    dp[1][0] = 0;
    dp[1][1] = 1;

길이가 1이면서, 마지막 숫자가 1인 이친수는 1 그 자체밖에 없기 때문에 1로 기저 사례를 설정하고. 0으로 시작하는 것은 불가능하기 때문에 마지막 숫자가 0인 이친수는 0으로 설정했다.

나아가서 손코딩으로 길이가 2일때의 기저 사례도 다음과 같이 설정해주었다.

    if (N >= 2)
        dp[2][0] = 1;
    if (N >= 2)
        dp[2][1] = 0;

여기서 포인트는 N이 2미만이라서 선언된 Vector 공간을 초과하는 인덱스 접근을 방지하기 위해. (엣지 케이스 방지) DP 배열의 기저 사례를 설정하기 전에 if문으로 체크를 해주는 것. 매우 중요하다. 진짜 매우 중요하다

사실 기초 DP 문제여서 기저 사례만 제대로 설정해도 반절은 맞았다.

현재 길이에서 마지막 숫자가 0인 애들은, 이전 길이에서 마지막 숫자가 1인 애들 + 0인 애들 모두가 될 수 있다.
왜냐하면 마지막에 0을 붙이는 것엔 어떤 제약도 따르지 않기에, 이전 길이의 마지막 수가 0으로 끝났든 1로 끝났든 그냥 아무거나 붙여서 가져올 수 있기 때문이다.

현재 길이에서 마지막 숫자가 1인 애들은, 이전 길이에서 0인 애들만 가져올 수 있다.
왜냐하면 이전 길이에서 마지막 숫자가 1일때는 1을 붙여서 가져올 수 없기 때문이다.

따라서 점화식은 다음과 같다:

    for (int i = 3; i <= N; ++i) {
        dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
        dp[i][1] = dp[i - 1][0];
    }

전체 코드:

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<vector<ll>> dp(N + 1, vector<ll>(2));

    // BASE CASE
    dp[1][0] = 0;
    dp[1][1] = 1;
    if (N >= 2)
        dp[2][0] = 1;
    if (N >= 2)
        dp[2][1] = 0;

    for (int i = 3; i <= N; ++i) {
        dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
        dp[i][1] = dp[i - 1][0];
    }

    cout << dp[N][0] + dp[N][1];
    return 0;
}

---

아이들과 선물 상자 (실버 2 | 23757)

상훈이는 N개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.
선물을 받을 아이들이 M명 있다. 아이들은 각자 1에서 M까지의 서로 다른 번호를 하나씩 부여받았다.

1번 아이부터 M번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이 때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.

하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.
상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다.

이 문제는 항상 '현재 선물이 가장 많이 담겨있는 상자' 에서 가져간다는 조건이 포함되어 있고, 각 분기에서 항상 최적의 선택을 하면. 즉 부분 최적해가 전체 최적해라는 점을 이용해서 그리디 방식으로 풀 수 있다.

현재 선물이 가장 많이 담겨있는 상자를 구별하기 위해 처음에는 Vector로 자료를 담고 std::sort하는 방식으로 생각했으나, 분기마다 선물이 가장 많이 담겨있는 상자가 계속 바뀐다는 점을 고려해서 Priority Queue로 변경했다.

Priority Queue는 heap을 사용해서 내부적으로 원소를 관리하고, 삽입/삭제에 대해 O(log n). 최대 원소 접근에 대해 O(1)의 시간 복잡도를 가지기에 매번 vector을 정렬하는 것보다 pq.pop() / pq.push()로 관리하는 것이 훨씬 빠르다.

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M; // 선물 상자 N, 아이들 수 M
    cin >> N >> M;

    priority_queue<int, vector<int>, less<int>> pq;

    for (int i = 0; i < N; ++i) {
        int present_count;
        cin >> present_count;
        pq.push(present_count);
    }

    for (int i = 0; i < M; ++i) {
        int children_wants;
        cin >> children_wants;

        // 선물 상자가 이미 비어있다면 0 출력 후 종료
        if (pq.empty()) {
            cout << "0";
            return 0;
        }

        int present_left = pq.top();
        pq.pop();

        // 아이가 원하는 양보다 크거나 같은지 확인
        if (present_left > children_wants) {
            pq.push(present_left - children_wants);
        } else if (present_left < children_wants) {
            // 아이가 원하는 양보다 선물의 개수가 작으면 0 출력 후 종료
            cout << "0";
            return 0;
        }
    }

    // 모든 검사가 끝나면
    cout << "1";

    return 0;
}

---

최대공약수 (실버 1 | 1850)

이 문제는 참신한 수학 기믹을 알아내야만 풀 수 있는 문제였다.

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

이 문제의 포인트는 유클리드 호제법을 이용해서, 그니까 numeric의 gcd를 이용해서 구할 순 없다는 것이다.
왜냐하면 구해야 할 수의 자리수가 무려 최대 2^63 이라서 무언가 수학 기믹이 필요하다.

정답은 이거였다.
1로만 이루어진 숫자들의 최대 공약수도 항상 1로만 이루어진다. 1이 n개와 m개 연속된 두 수의 최대공약수는, 그 길이가 n과 m의 최대공약수(gcd(n, m))인 수다. 왜냐하면, 두 수 A와 B가 있을 때, A를 B로 나누는 것은 사실상 10진법에서 A의 길이에서 B의 길이를 빼는 것과 같고, 이는 유클리드 호제법의 과정과 동일하게 길이에 대한 최대공약수를 찾는 과정과 같기 때문이다.

즉, 111과 111111의 최대 공약수(GCD)의 자리수는 최대 공약수를 구하려는 수의 각 자리수 3, 6의 GCD와 같다.
gcd(3, 6) = 3. 즉 111과 111111의 최대 공약수는 111.
1로 이루어진 수의 자리수가 500000000000000000인 수와 500000000000000002인 수의 GCD는
gcd(500000000000000000, 500000000000000002) = 2. 즉 11이다.

이런 수학 기믹을 활용하는 문제는 평소의 수학적 접근법으로는 시간 초과(TLE)가 뜨는 문제여서 무조건 기믹이 있어야 풀 수 있다는 직감이 오게 만든다. 따라서 무슨 유형의 문제인지 파악하는 건 쉬운데.. 어떻게 접근하는지 파악하는 게 쉽지 않다.

내가 수학자도 아니고.. 이런 문제를 만났을 땐 최대한 뇌 안에서 브루트포스 접근법마냥 여러 케이스를 시도해보면서 기믹을 즉석으로 찾는 것 밖에 답이 없다.

/*
포인트는, 숫자 자체에 초점을 맞추는 게 아니라 1의 개수에 초점을 맞추는 것
두 수 A와 B가 모두 1로만 이루어져 있으므로, 최대공약수도 1로만 이루어진 수가 된다.
A와 B의 최대공약수는 A와 B의 길이(1의 개수)의 최대공약수와 같다.
따라서 '1'을 gcd(a, b)번 반복한게 답이 된다.
*/

#include <iostream>
#include <numeric>
using namespace std;
typedef long long ll;

int main() {
    ll a, b;
    cin >> a >> b;
    ll loop = gcd(a, b);
    while (loop--) {
        cout << "1";
    }
    return 0;
}

---

휴식이 조금 길었는데, 나름대로 느긋하게 여러 공부를 하고 있었다.
속도는 느리더라도 어제보다는 성장했음에 집중했다.

PS. 이제 AI 일론머스크 평가 시스템은 연속 100일을 달성하고 끝났다. 재밌는 프로젝트였다.