240213: Union-find, MST, 크루스칼(Kruskal), 그리디 끝.

2024-02-13

오늘은

• 프로그래머스 탐욕법(Greedy) 나머지 풀이
• 업랜디 1판
• SQL 강의 듣기
• 동적계획법 일부 풀기
• Union-find를 배웠다

오늘의 업랜디

23293 아주 서바이벌 (시간초과 실패 후 해결 - 시뮬레이션)

오늘의 프로그래머스

큰 수 만들기 (Lv. 2)
구명보트 (Lv. 2)
섬 연결하기 (Lv. 3) - Union find, Kruskal Algorithm, MST.
단속카메라 (Lv. 3)

- 동적계획법 (Dynamic Programming)
N으로 표현 (Lv. 3)

큰 수 만들기

어떤 숫자에서 k개의 수를 제거했을 때 만들 수 있는 가장 큰 수를 구하는 문제.
얼핏보면 간단해보이지만, 단순히 조합을 생각하는 게 아니라 순서대로 읽는데, k개를 안 읽으면서 만들 수 있는 가장 큰 수를 구하는 문제다.

순서대로 큰 수라면 그리디하게 이전 수보다 현재 수가 크면 이전 수를 없앤다 고 생각할 수 있다.
그러면 문제의 조건을 모두 충족한다.

stack을 활용해서 구현했다.

string solution(string number, int k) {
    stack<int> stack;
    string answer = "";
    stack.push(number[0] - '0');
    for (int i=1;i<number.size();++i) {
            int next_num = number[i] - '0';
            while (!stack.empty() && stack.top() < next_num && k > 0) {
                stack.pop();
                --k;
            }
            stack.push(next_num);
    }

    while (k--) {
        stack.pop();
    }

    vector<int> v;
    while (!stack.empty()) {
        v.push_back(stack.top());
        stack.pop();
    }

    for (int i=v.size()-1; i>=0; --i) {
        answer += to_string(v[i]);
    }
    return answer;
}

---

구명보트

구명보트에 무게 제한이 있고, 최대한 적은 개수로 모든 사람을 태워야하는 전형적인 그리디 문제였다.
최대 두명을 태울 수 있다. 이건 보자마자 해법이 떠올랐다.
오름차순으로 정렬해서 첫번째 인덱스에는 제일 가벼운 사람, 마지막 인덱스에는 제일 무거운 사람이 오도록 하고.
제일 무거운 사람 + 제일 가벼운 사람 <= limit이면 둘 다 태우고, 아니면 제일 무거운 사람만 태운다.

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int i=0, j=people.size()-1;
    while (i <= j) {
        if (people[i] + people[j] <= limit) {
            ++i;
        }
        --j;
        ++answer;
    }
    return answer;
}

---

섬 연결하기

섬 연결하기 문제는 섬을 연결하는 다리의 최소 비용을 구하는 문제다.
이런 유형의 문제는 처음 봤는데, Union-find라는 알고리즘을 이용해서 아주 쿨하게 처리할 수 있다.
Union-find 알고리즘의 주요 연산이 두 정점을 집합으로 묶는 Union 연산과, 두 정점이 한 집합인지 반환하는 <bool>find 연산이 있어서 Union-find라고 불리는 것 같다.

먼저 그리디하게 섬 다리의 비용을 최소 오름차순으로 정렬하고, 아래에서부터 사이클이 발생하지 않게 (다른 집합끼리의 Union 연산) 하면서 연결하면 된다.

Union-find의 주요 테크닉은 아래와 같다

1. 경로 압축
   return parents[x] = getParents(parents, parents[x]); 가 이 부분이다.
   원래 같으면, Union 연산을 할 때 정점 A나 정점 B의 노드중 하나가 서로를 가리키면서 인덱스가 연결된다. 따라서 정점이 많아지고 트리가 복잡해지면 특정 노드의 루트 노드를 탐색하기 위해 여러개의 노드를 탐색해야 할 수 있고, 최악의 경우 마치 선형 자료구조처럼 작동해 O(n)의 시간이 걸릴수도 있다. 따라서, find 연산을 할 때, 아래와 같이 무조건 루트 노드를 찾아 나가지 않는다.

   int find(vector<int>& parent, int x) {
    while (x != parent[x]) {
        x = parent[x];
    }
    return x;
   }

대신, 아래와 같이 루트 노드를 찾아 나가면서 거친 경로의 모든 노드를 최종 루트 노드가 되도록 반환하면서 간다.

int getParent(vector<int>& parents, int x) {
    if (parents[x] == x) return x;
    return parents[x] = getParent(parents, parents[x]);
}

이렇게 하면 반복된 작업에 대해서 불필요한 연산 낭비를 효율적으로 줄일 수 있다.

2. 랭크 기반 합치기
   Union 연산에서 무조건 루트 노드로 인덱스가 연결되도록 하면 트리가 비효율적으로 길고 좁은 형태가 될 수 있다. 따라서 이 방법도 최악의 경우 트리의 높이가 선형적으로 증가할 수 있다.
   랭크 기반 합치기는 rank라는 가상의 int 배열을 만들고, 두 트리의 rank를 비교해서 더 낮은 rank를 가진 트리를 더 높은 rank를 가진 트리에 연결한다. 만약 두 트리의 rank가 같다면, 아무거나 연결하고 rank를 1 올린다.

이 방법으로 트리의 높이가 비효율적으로 증가하는 것을 막을 수 있다.

전체 코드:

int getParent(vector<int>& parents, int x) {
    if (parents[x] == x) return x;
    return parents[x] = getParent(parents, parents[x]);
}

void unionParent(vector<int>& parents, vector<int>& rank, int a, int b) {
    a = getParent(parents, a);
    b = getParent(parents, b);
    if (rank[a] > rank[b]) parents[b] = a;
    else if (rank[a] < rank[b]) parents[a] = b;
    else {
        parents[b] = a;
        rank[a]+=1;
    }
}

bool findParent(vector<int>& parents, int a, int b) {
    a = getParent(parents, a);
    b = getParent(parents, b);
    return a==b;
}



int solution(int n, vector<vector<int>> costs) {
    // Union-find
    int answer = 0;
    vector<int> parents(n);
    vector<int> rank(n, 0);

    for (int i=0;i<n;++i) {
        parents[i] = i;
    }

    sort(costs.begin(), costs.end(), [](vector<int>& a, vector<int>& b){
       return a[2] < b[2]; 
    });

    for (int i=0;i<costs.size();++i) {
        int a = costs[i][0];
        int b = costs[i][1];
        int cost = costs[i][2];
        if (!findParent(parents, a, b)) {
            unionParent(parents, rank, a, b);
            answer += cost;
        }
    }

    return answer;
}

Union-find라는 새로운 개념을 배우게 된 재밌는 문제였다.
이렇게 푸는 방법이 Union-find, 크루스칼(Kruskal) 알고리즘을 이용한 최소 신장 트리(Minimum Spanning Tree, MST) 라고한다. 그리디하게 풀 수 있다.

---

아주 서바이벌

아주 서바이벌에는 1번부터 53번 지역까지 총 53개의 지역이 존재하며, 모든 플레이어가 1번 지역(정문)에 모인 채로 게임이 시작된다.

플레이어들은 이동, 획득, 조합, 공격 총 네 가지 종류의 행동을 할 수 있다.

이동 : 플레이어가 현재 위치한 지역에서 다른 지역으로 이동한다. 즉, 현재 위치한 지역으로는 이동하지 않는다.
획득 : 플레이어가 현재 위치한 지역에서만 획득할 수 있는 소재 아이템 1개를 획득한다. 즉, x번 지역에서는 x번 소재 아이템을 획득한다. 아이템의 수량은 충분해 부족할 일이 없으며, 한 플레이어가 같은 아이템을 여러 번 획득할 수 있다.
조합 : 플레이어가 가지고 있는 서로 다른 종류의 두 소재 아이템을 1개씩 사용해 장비를 만든다.
공격 : 플레이어가 다른 플레이어 한 명을 공격한다. 오직 같은 지역에 있는 플레이어만 공격할 수 있다.
위 행동들에서 상민이는 아래 세 가지 경우를 부정행위라고 판단했다.

플레이어가 현재 위치한 지역에서 얻을 수 없는 소재 아이템을 획득한 경우
플레이어가 가지고 있지 않은 소재 아이템을 사용해 조합하는 경우
플레이어가 다른 지역에 있는 상대 플레이어를 공격하는 경우
상민: 부정행위로 보이는 모든 로그를 기록할 거야. 하지만, 공격할 때 위치를 속이는 것은 참을 수 없어. 그런 플레이어는 차단할 거야!

부정행위로 획득한 소재 아이템 역시 획득한 것으로 인정되며, 부정행위로 조합 시 가지고 있는 소재 아이템만이 사용된다.

위 로그를 예로 들면, 11번 플레이어는 13번 지역으로 이동하여(1) 13번 소재 아이템을 획득하고(3), 이후 3번 지역으로 이동하여(4) 3번 소재 아이템을 획득해(5) 3번과 13번 소재 아이템을 조합했다(6). 모두 정상적인 행동이다.

13번 플레이어는 15번 지역으로 이동한 후(2), 3번 지역에 있는 11번 플레이어를 공격했다(7). 다른 지역에 있는 플레이어를 공격하는 것은 부정행위이기 때문에 7번 로그를 기록하고, 공격 부정행위이기 때문에 13번 플레이어는 차단해야 한다. 이어서, 15번 소재 아이템을 획득하고(8), 16번 소재 아이템을 획득 후에(9), 15번과 16번 소재 아이템을 조합했다(10). 15번 지역에서 16번 소재 아이템을 획득하는 것은 부정행위이기 때문에 9번 로그를 기록한다. 하지만, 16번 소재 아이템을 획득한 것은 인정되기 때문에 10번 로그는 부정행위가 아니다.

상민이를 위해 게임의 로그를 분석하고, 기록된 부정행위와 차단할 플레이어를 상민에게 알려주자.

아주 서바이벌은 요약해서, 게임 내에서 가능한 정상 상호작용의 정보와 로그 정보가 주어졌을 때, 정상적인 범위를 벗어난 상호작용을 한 로그를(치트) 잡는 문제였다.

시뮬레이션 문제로, 난이도는 쉬웠지만 시간 제한이 30분으로 꽤 촉박했다.
안타깝게도 시간을 5분 넘기고 풀었다. 시간 초과
조금 더 급하게 풀 걸 그랬다, 근데 급하게 풀면 무엇이든 실수를 하기 마련이니까,, 계속 전 코드를 복기하는 과정에서 시간이 좀 더 소요된 것 같다.

모든 게 완벽했는데 시간만 좀 더 있었더라면 ... :(
아 ,, 문제를 풀다가 state 구조체를 만들고 map을 관리하는 과정에서, 이렇게 구조체가 유연하게 작동되는지 처음 알았다. (어 이렇게 해도 되나? 되나? 되네?)

예를 들면 player[pid].inv를 참조자 인자로 넘기고 조작하는 식이 가능했다
예전에 switch문은 char에 대해 작동하지 않는 걸 들은 것 같아서 switch를 쓰지 않았다.

// 백준: 아주 서바이벌
// https://www.acmicpc.net/problem/23293
// 2024-02-13

#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>

using namespace std;

struct state {
    int pid;
    int pos = 1;
    vector<int> inv;
};

unordered_map<int, state> player;
vector<int> cheated_log;
set<int> blocked_pid;

bool del_item(vector<int> &inv, int item_id) {
    auto it = find(inv.begin(), inv.end(), item_id);
    bool found = (it != inv.end());
    if (found) {
        inv.erase(it);
    }
    return found;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T, N;
    cin >> T >> N;
    // 플레이어 상태 map
    for (int i = 0; i < T; ++i) {
        int uid, pid, arg;
        char action;
        cin >> uid >> pid >> action >> arg;
        if (action == 'M') { // 이동
            player[pid].pos = arg;
        }
        if (action == 'F') { // 획득
            player[pid].inv.push_back(arg);
            if (player[pid].pos != arg) {
                cheated_log.push_back(uid);
            }
        }
        if (action == 'C') { // 조합
            int comb_item;
            cin >> comb_item;
            bool temp_a = del_item(player[pid].inv, arg);
            bool temp_b = del_item(player[pid].inv, comb_item);
            if (!(temp_a && temp_b)) {
                cheated_log.push_back(uid);
            }
        }
        if (action == 'A') { // 공격
            if (player[pid].pos != player[arg].pos) {
                cheated_log.push_back(uid);
                blocked_pid.insert(pid);
            }
        }
    }

    // 출력
    cout << cheated_log.size() << "\n";
    for (int i = 0; i < cheated_log.size(); ++i) {
        cout << cheated_log[i] << " ";
    }
    if (!cheated_log.empty())
        cout << "\n";
    cout << blocked_pid.size() << "\n";
    for (const int &pid : blocked_pid) {
        cout << pid << " ";
    }
    return 0;
}

---

단속카메라

단속카메라 문제는 차량의 진입 시점과 진출 시점이 주어지면, 모든 차량을 단속하기 위한 최소 과속카메라 설치 개수를 구하는 문제였다.
처음에 그리디 해결법이 떠오르지 않아서, 선형 1차원 벡터를 만들고 차량의 동선을 추적한 뒤 제일 동선이 겹치는 부분에 설치하는 방법을 떠올렸는데, 이렇게 하면 무조건 TLE (차량의 수 1만대 * 도로 60000블럭)가 났다.

Idea는 차량 배열을 진출 시점으로 오름차순 정렬하고, 현재 카메라가 동선에 없으면 진출 시점에 카메라를 설치하는 매우 간단한 로직이었다.

그리디는 모르겠으면 일단 정렬해놓고 시작하자. 그리디는 거의 무조건 정렬로 시작한다.

int solution(vector<vector<int>> routes) {
    int answer = 0;
    int last_camera_pos = -30001;
    sort(routes.begin(), routes.end(), [](vector<int>& a, vector<int>& b){
        return a[1] < b[1];
    });
    for (int i=0;i<routes.size();++i) {
        int start = routes[i][0];
        int end = routes[i][1];
        if (last_camera_pos >= start && last_camera_pos <= end) continue;
        else {
            ++answer;
            last_camera_pos = end;
        }
    }
    return answer;
}

---

N으로 표현 (동적계획법)

N으로 표현 문제는 N과 목표 숫자 number가 주어지면, N을 k번 이용해 사칙연산 식을 만들어서 number을 만드는데. k가 최소로 하는 방법을 구하는 DP 문제다.

dp[1] = N으로 두고 (자기자신 하나로 유일하니까)
dp[2]부터 이전 dp를 사칙연산으로 조합해 가능한 모든 경우를 추가한다.
이때 주의할점은 vector에 추가하면 안된다. 중복 조합이 있을 수 있기에 set으로 해야한다.

DP문제는 정말 어렵다. 무조건 옆에 노트가 있어야 풀 수 있을 듯....

int solution(int N, int number) {
    if (N==number) return 1;
    vector<set<int>> dp(9);
    dp[1].insert(N);
    for (int i=2;i<=8;++i) {
        int repeatedN = stoi(string(i, '0' + N));
        dp[i].insert(repeatedN);
        for (int j=1;j<i;++j) {
            for (int a : dp[j]) {
                for (int b : dp[i - j]) {
                    dp[i].insert(a + b);
                    dp[i].insert(a - b);
                    dp[i].insert(a * b);
                    if (b != 0) dp[i].insert(a / b); // zero-division
                }
            }
        }

        if (dp[i].find(number) != dp[i].end()) return i;
    }
    return -1;
}

for문을 구성할 때, dp[3]의 경우 1 + 1 + 1, 1 + 2 를 모두 확인해야 된다고 생각해서 어려웠는데.
잘 생각해보면 어차피 (1 + 1) 은 dp[2]에 포함되어 있어서 1 + 2만 확인하면 된다.
똑같이 dp[4]의 경우도 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3 이 아니라, dp[3]에 모든 경우가 포함되어 있기 때문에 dp[2] + dp[2] 혹은 dp[3] + dp[1] 이다.

현재 시간 밤 11시 11분인데 너무 피곤하다. 어제 너무 늦게 자고 일찍 일어난 탓인 것 같다.
지금 공부해도 더 이상 유의미한 효율이 안 나올 것 같다. 오늘은 여기까지 하고 내일 나머지 DP문제와 SQL강의를 듣는걸로. 시간이 남으면 복습까지 :)

최종 평가

[스터디 노트 평가: 2024-02-13]

1. **프로그래머스 탐욕법(Greedy) 문제 해결 및 업랜디 활동**
   - 탐욕법 문제를 성공적으로 해결하며 알고리즘 적용 능력을 보여주었습니다. 특히, '큰 수 만들기', '구명보트', '섬 연결하기' 문제에서의 접근 방식은 문제 해결력의 깊이를 보여줍니다.
   - 업랜디 활동을 통해 시뮬레이션 문제 해결 능력을 입증하였습니다. '아주 서바이벌' 문제의 해결 과정에서는 시간 관리에 어려움을 겪었으나, 결국 문제를 해결하여 인내심과 끈기를 보여주었습니다.

2. **Union-find 알고리즘 및 동적계획법(DP) 활용**
   - '섬 연결하기' 문제를 통해 Union-find 알고리즘을 학습하고 적용한 점은 알고리즘 지식의 확장을 보여줍니다. 이 알고리즘의 이해와 적용은 복잡한 문제를 효율적으로 해결하는 데 큰 도움이 됩니다.
   - 동적계획법을 이용한 'N으로 표현' 문제 해결 능력은 알고리즘에 대한 이해도와 문제 해결 능력의 높은 수준을 보여줍니다. DP 문제에 대한 접근 방식과 해결 과정은 알고리즘적 사고의 깊이를 더합니다.

3. **평가 및 조언**
   - 오늘의 학습 활동을 종합적으로 평가할 때, 95점을 부여합니다. 프로그래머스 탐욕법 문제 해결, 업랜디 활동, 그리고 Union-find와 동적계획법(DP) 문제 해결을 통해 보여준 능력은 매우 인상적입니다. SQL 학습 계획에 따라 학습하지 못한 점은 아쉽지만, 전반적으로 높은 수준의 알고리즘 이해와 적용 능력을 보여주었습니다.
   - 앞으로도 다양한 유형의 문제를 꾸준히 해결하면서, 문제 해결 능력을 더욱 키워나가시길 바랍니다. 또한, 계획한 학습 목표를 체계적으로 수행하기 위한 시간 관리와 학습 계획에 대한 지속적인 점검이 필요합니다.

[피드백 요약]
- 다양한 알고리즘 문제 해결 능력과 학습 목표 달성을 위한 노력이 돋보입니다.
- Union-find 알고리즘과 동적계획법(DP) 문제 해결 능력은 알고리즘 학습의 깊이를 보여줍니다.
- 시간 관리와 학습 계획의 체계적인 수행을 위한 더 많은 노력이 필요합니다.

[조언]
- 다양한 알고리즘 문제에 대한 지속적인 도전을 통해 문제 해결 능력을 향상시키시길 바랍니다.
- 알고리즘 학습과 더불어, SQL과 같은 데이터 관리 기술에 대한 학습도 중요합니다. 계획에 따라 균형 잡힌 학습을 실천하시길 권장합니다.
- 학습과 휴식의 균형을 잘 유지하면서, 건강한 생활 습관을 통해 지속 가능한 학습 효율을 높이시길 바랍니다.

오늘의 학습 활동에 대한 평가와 함께 여러분의 노력과 성장이 돋보이는 하루였습니다. 탐욕법 문제 해결을 통해 보여준 그리디 알고리즘 적용 능력, 업랜디 활동에서의 시뮬레이션 문제 해결 능력, 그리고 Union-find 알고리즘 및 동적계획법(DP)에 대한 이해와 적용은 앞으로의 프로그래밍 활동에 있어 중요한 기반이 될 것입니다. 내일 해결할 문제에 대한 준비와 계획을 잘 세워, 지속적인 성장을 이루시길 바랍니다. 데이터 관리와 분석 능력 개발에 대한 SQL 학습도 중요하니, 균형 잡힌 학습 계획을 실천해 나가시기 바랍니다.