240411: 로마 숫자 재배치 문제. Unity 튜토리얼 70% 완성

2024-04-11

Unity 진행상황

튜토리얼로 만든 게임을 거의 완성했다. 캐릭터가 키보드/마우스로 움직이고, 총을 발사하고. 위에서 오는 몬스터를 죽이고 코인을 먹고 점수를 올리는 시스템이다.
앞으로 남은 구현은 무기 강화와 보스전, 게임 오버 화면이다.

여러가지 시도들을 해보다가 또 새로운 토이 게임을 만들어 볼 생각 (워밍업)
아직 제대로 된 게임을 개발해서 출시할 생각은 없다. Unity를 다루는 스킬을 키우는 게 먼저인 듯..

오늘 C#에서 클래스를 다루다가 static 메서드에 대해서 조금 제대로 깨달았다.
원래는 알면서도 와닿진 않았는데. 고정 메모리 주소를 사용해서 인스턴스 종속적이지 않다는 점. 확실하게 알았다.

강의 듣다가 의문점이 들면 메모해뒀다가 GPT한테 한번에 물어보는 학습 방식이 효율적인 것 같다.
이렇게 독학하기 편한 시대가 왔다

의문점 Memo

1. ForceMode2D.Impulse란?
2. Vector2 jumpVelocity에 y와 x값을 동시에 연산하면 안되는 이유?
3. Prefabs를 관리하는 폴더 이름은 항상 Prefabs로 하도록 Unity에 명시되어 있는지?
4. Instantiate의 어원
5. 싱글톤 디자인 패턴을 사용하는 이유와, 싱글톤에서 굳이 인스턴스 하나를 경유하는 이유
6. Unity C#에서 다른 클래스간의 접근이 import 없이 자유로운 것 같은데 왜?
etc

 

 

 

 

---

푼 알고리즘 문제는:

• 로마 숫자 재배치 (실버 1 | 2915)
• 우체국 1 (실버 2 | 18442)
  

로마 숫자 재배치

1, 2, 3, 4, 5, 6, 7, 8, 9를 로마 숫자로 바꾼다면 I, II, III, IV, V, VI, VII, VIII, IX가 된다.

10, 20, 30, 40, 50, 60, 70, 80, 90은 X, XX, XXX, XL, L, LX, LXX, LXXX, XC가 된다.

100보다 작은 수를 로마 숫자로 바꾸려면, 십의 자리와 일의 자리를 따로따로 위의 방법을 이용해서 로마 숫자로 바꾼 다음, 하나로 이어 붙이면 된다.

예를 들어, 48은 XLVIII이다. 그 이유는 40을 XL로 바꾸고, 8을 VIII로 바꾼 다음, 둘을 이어 붙이면 XLVIII이기 때문이다.

로마 숫자가 주어졌을 때, 문자를 재배치했을 때 나올 수 있는 숫자 중, 가장 작은 수를 구하여 로마 숫자로 출력하는 프로그램을 작성하시오.

처음에 문제를 받고 읽을때는 단순한 문제인 줄 알았는데, 마지막 줄을 읽고 잠시 .. 당황했다.

로마 숫자가 주어졌을 때, 문자를 재배치했을 때 나올 수 있는 숫자 중, 가장 작은 수를 구하여 로마 숫자로 출력하는 프로그램을 작성하시오.

그니까 로마 문자열을 가능한 조합으로 모두 변경하고 -> 이걸 다시 숫자로 변환한 뒤 -> 제일 작은 숫자 값을 다시 로마자로 변환해야 한다.

솔직히 조금 답이 없어서 당황했는데 next_permutation이 생각났다. 사전순 순열을 순회하는 함수다.

next_permutation - 사전순 순회

순열은 순서 있게 수를 나열하는 것으로, 랜덤이 아니라 의미가 있는 순서라면 모두 순열이라고 칭할 수 있다.
next_permutation은 사전순 순열로 순회하는 함수다.

이렇게 순열 조합을 사용하는 문제에서 매우 유용하게 써왔었는데, 한번쯤은 함수 내부 구현을 알아보고 직접 구현할 필요가 있다고 생각했다.

기본적으로 next_permutation은 주어진 배열을 사전순에서 다음 위치로 변경하고, true를 반환한다.
만약 현재 배열이 사전순의 맨 끝이면, 역으로 정렬 (즉, 사전순의 맨 첫부분으로 변경)하고 false를 반환한다.

따라서 배열을 사전 오름차순으로 정렬하고 do { } while ()의 조건에 사용하는것이 모든 순열을 탐색하기 위한 next_permutation의 일반적인 사용 방법이다.

next_permutation의 내부 구현은 다음과 같다:

1. a[k] < a[k+1]인 k중 max k를 찾는다.
2. a[k] 보다 큰 값들 중 max index: m을 찾는다.
3. a[k]와 a[m]을 swap한다.
4. a[k+1]부터 배열의 끝까지 reverse 한다.

즉 배열이 1, 2, 3 이라면 다음과 같은 흐름을 따른다:

1. max k = 1(index)
2. 인덱스 1의 값인 2보다 큰 값중 가장 인덱스가 큰 값은 3이고 3의 인덱스는 2니까 m = 2.
3. a[1] 과 a[2]를 swap한다.
4. 1, 3, 2가 되고. a[2] 부터 끝까지 reverse한다.
5. 1, 3, 2

풀이

조금 복잡하게 푼 감이 있다. 랜덤 디펜스: 시간 제한 30분 으로 푼 문제라서 빠르게 구현해서 코드가 약간 복잡하다.

일의 자리 로마자와 십의 자리 로마자를 순서대로 배열에 넣고, 입력으로 주어진 로마자를 사전 오름차순으로 sort하고 다음 사전순을 끝까지 순회하면서 (즉, 사실상 가능한 모든 조합을 순회한 셈)
각 조합의 로마자에 대해 로마자 정보 배열을 순회 / 검색하면서 읽을 수 있는 수의 조합이 있는지 검사하는 코드를 구현했다.

이 과정에서 search라는 검색 함수를 급하게 구현했는데. String 클래스의 search와 비슷하지만 contain 검색이 아니라 equal 검색으로 범위를 지정해서 검색하는 로마자가 특정 위치에 완벽하게 존재하는지 확인했다.

문제의 조건에서 모든 로마자는 100 미만의 숫자이기에, 처음에 십의 자리 로마자 -> 일의 자리 로마자를 탐색하고. 그 다음으로 10 미만의 로마자, 즉 일의 자리 로마자만 탐색하는 식으로 이중 구현했다.

복잡한 문제를 C++ STL의 next_permutation 덕분에 빠르고 침착하게 구현한 것 같아서 뿌듯했다.

전체 코드

// 백준: 로마 숫자 재배치
// https://www.acmicpc.net/problem/2915
// 2024-04-09

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

string roman_units[9] = {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; // 1 ~ 9
string roman_tens[9] = {"X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};  // 1* ~ 9*
int smallest_num = (~0U >> 2);
string smallest_roman;

bool search(string text, string compare, int start, int l) {
    string new_text = text.substr(start, l);
    if (new_text.length() != compare.length())
        return false;
    for (int i = 0; i < new_text.length(); ++i) {
        if (new_text[i] != compare[i])
            return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string B;
    cin >> B;
    sort(B.begin(), B.end());
    do {
        // 십의 자리
        for (int i = 0; i < 9; ++i) {
            int index = 0;
            if (search(B, roman_tens[i], index, roman_tens[i].length())) {
                index += roman_tens[i].length();
                for (int j = 0; j < 9; ++j) {
                    if (search(B, roman_units[j], index, roman_units[j].length())) {
                        int temp = (i + 1) * 10;
                        temp += j + 1;

                        if (temp < smallest_num && roman_tens[i].length() + roman_units[j].length() == B.length()) {
                            smallest_num = temp;
                            smallest_roman = roman_tens[i] + roman_units[j];
                        }
                    }
                }
            }
        }

        // 일의 자리
        for (int j = 0; j < 9; ++j) {
            int index = 0;
            if (search(B, roman_units[j], index, roman_units[j].length())) {
                if (j + 1 < smallest_num && roman_units[j].length() == B.length()) {
                    smallest_num = j + 1;
                    smallest_roman = roman_units[j];
                }
            }
        }

    } while (next_permutation(B.begin(), B.end()));

    cout << smallest_roman;
    return 0;
}

---

우체국 1

원형으로 큰 길(순환로)이 뻗어 있고, 길 옆으로 V개의 마을이 자리잡고 있다. 큰 길의 둘레 길이는 정수 L이다. 이 문제에서 큰 길은 0 이상 L-1 이하의 정수가 늘어져 있는 원이고, 각 마을의 위치는 길 상의 정수 좌표로 표현된다. 한 위치에 여러 마을이 있을 수 있다. 좌표가 x, y인 두 마을의 거리는 min(|x - y|, L - |x - y|) 이다. 

우리는 이들 마을이 있는 곳에 우체국을 P개 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다. 전체 마을 중 몇 곳을 골라, 그 위치에 우체국을 짓게 된다. 우리는 그 때 각 마을과 그 마을과 가장 가까운 우체국 사이의 거리의 합이 최소가 되게 하고 싶다.

각 마을의 위치와 짓고자 하는 우체국 개수를 입력받아서, 각 마을과 그 마을과 가장 가까운 우체국 사이 거리의 합으로 있을 수 있는 최소값을 계산하고, 그런 결과를 낼 수 있도록 각 우체국을 지을 위치를 출력하는 프로그램을 작성하라.

처음엔 제일 효율적인 interval을 찾는 패턴과 비슷해서 이분탐색 응용인 줄 알았으나,
이 문제는 백트래킹 그리고 DFS를 이용해서 모든 조합을 탐색하는 방식으로 풀 수 있었다.
pruning(가지치기)로 최적화 할 필요도 없었다

먼저 각 마을을 연결하는 길이 원형 순환로 형태이기 때문에, 두 마을의 거리가 min(|x - y|, L - |x - y|) 임을 명심해야 한다.

먼저, DFS 탐색이 끝났을 때(즉, depth가 우체국 수와 똑같아지면) 각 마을에서 우체국까지의 최단거리의 합을 구하기 위한 함수를 작성했다.

조금 복잡해보이는데 사실 간단하다. 마을 위치와 우체국 위치를 입력받고, 둘 다 순회하면서 최단 거리를 찾아 누적하는 방식.

ll getDistances(vector<ll> &town, vector<ll> &postOffices) {
    ll sum_distance = 0;
    for (size_t i = 0; i < town.size(); ++i) {
        ll cur_pos = town[i];
        ll known_shortest = LLONG_MAX;
        for (size_t j = 0; j < postOffices.size(); ++j) {
            ll cur_compare = postOffices[j];
            ll dist = min(abs(cur_pos - cur_compare), L - abs(cur_pos - cur_compare));
            if (dist < known_shortest) {
                known_shortest = dist;
            }
        }
        sum_distance += known_shortest;
    }

    return sum_distance;
}

그리고 가능한 모든 조합을 탐색하는 DFS 코드도 재귀(Recursive)로 구현했다.
우체국 설치가 모두 끝났으면 최단 거리 누적 함수를 호출하고, 현재 알려진 값보다 더 최적의 값이면 현재 우체국 배열을 best_comb 배열에 저장한다. 이걸 모든 조합에 대해 반복한다.

void dfs(ll start, ll depth, vector<ll> &postOffices) {
    if (depth == P) {
        ll dist = getDistances(town, postOffices);
        if (dist < known_shortest_distance) {
            best_comb = postOffices;
            known_shortest_distance = dist;
        }
        return;
    }

    for (ll i = start; i < V; ++i) {
        postOffices.push_back(town[i]);
        dfs(i + 1, depth + 1, postOffices);
        postOffices.pop_back(); // 백트래킹
    }
}

마지막으로, 메인 함수에서 마을 위치 정보를 입력받고 DFS 호출 후 정답 출력하는 부분을 구현했다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> V >> P >> L;
    town.assign(V, 0);
    for (ll i = 0; i < V; ++i) {
        cin >> town[i];
    }

    vector<ll> postOffices;
    dfs(0, 0, postOffices);

    cout << known_shortest_distance << "\n";
    for (const auto next : best_comb) {
        cout << next << " ";
    }
    return 0;
}

Recursive DFS를 오랜만에 구현하는 것 같아서 약간 막혔다. 역시 복습이 제일 중요하다 !
그래서 이 문제는 두번이나 풀었다. 이 코드는 두번째로 작성한 코드다.

전체 코드

// 백준: 우체국 1
// https://www.acmicpc.net/problem/18442
// 2024-04-09
// 복습 2회차 - 실력 다지기..

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;
typedef long long ll;

vector<ll> town;
vector<ll> best_comb;
ll known_shortest_distance = LLONG_MAX;
ll V, P, L; // 마을 개수, 우체국 개수, 총 길이

ll getDistances(vector<ll> &town, vector<ll> &postOffices) {
    ll sum_distance = 0;
    for (size_t i = 0; i < town.size(); ++i) {
        ll cur_pos = town[i];
        ll known_shortest = LLONG_MAX;
        for (size_t j = 0; j < postOffices.size(); ++j) {
            ll cur_compare = postOffices[j];
            ll dist = min(abs(cur_pos - cur_compare), L - abs(cur_pos - cur_compare));
            if (dist < known_shortest) {
                known_shortest = dist;
            }
        }
        sum_distance += known_shortest;
    }

    return sum_distance;
}

void dfs(ll start, ll depth, vector<ll> &postOffices) {
    if (depth == P) {
        ll dist = getDistances(town, postOffices);
        if (dist < known_shortest_distance) {
            best_comb = postOffices;
            known_shortest_distance = dist;
        }
        return;
    }

    for (ll i = start; i < V; ++i) {
        postOffices.push_back(town[i]);
        dfs(i + 1, depth + 1, postOffices);
        postOffices.pop_back(); // 백트래킹
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> V >> P >> L;
    town.assign(V, 0);
    for (ll i = 0; i < V; ++i) {
        cin >> town[i];
    }

    vector<ll> postOffices;
    dfs(0, 0, postOffices);

    cout << known_shortest_distance << "\n";
    for (const auto next : best_comb) {
        cout << next << " ";
    }
    return 0;
}

---

nowadays
요즘 대학교 친구들한테 코딩 과외해 주느라 꽤 바쁘다. 시험 기간이라서 다들 분주한 것 같다.
가르치면서 계속 느끼는 건데, 거의 95%는 코딩을 어려워하는 것 같다.
대학생들도 이렇게 코딩을 어려워하는데, 나는 어떻게 초등학교 때부터 독학했는지 의문이긴 하다. 이럴 때마다 나는 천성이 개발자라는 게 느껴지긴 한다. (근데 또 이런 말 하기엔 알고리즘은 너무 어렵다..)

초등학교 4학년 때 C언어 구조대라는 완전 옛날 앱 다운로드해서 읽었었는데, 그때 포인터랑 다차원 배열까지 독학하고 접었었다.

그리고 aide라는 안드로이드 앱을 개발하는 안드로이드 앱(?) 을 설치해서 Android Studio와 비슷한 환경에서 앱을 개발했다. (Java + XML로 Activity 넘기고 버튼 만들고 이런 거 했던 것 같은데 자세하겐 기억 안 난다)

중학교 시절엔 학업과의 타협 때문에 개발 공부를 많이 못 한 것 같아서 아쉽다.