240629: 클래스 5 달성. 알고리즘 14문제 정리

2024-06-29

클래스 5 달성

6월 13일부터 클래스 5를 시작했다. 클래스 5에서 주로 다루는 개념은: 투 포인터, 분리 집합, 위상 정렬, 최소 스패닝 트리, 기하학, 비트마스킹이다.
참고로 클래스 4에서는: 백트래킹, 트리, 최단 거리 알고리즘(데이크스트라 등), LIS, LCS, 배낭 문제였다.

6월 28일 클래스 5를 달성했다. 이제 차례대로 은장과 금장을 딸 예정! 플래티넘까지 정말 조금 남았다.

---

푼 문제들

• 다각형의 면적 (2166)
• 용액 (2467)
• 트리와 쿼리 (15681)
• 수 나누기 게임 (27172)
• 최소 스패닝 트리 (1197)
• 도시 분할 계획 (1647)
• 스도쿠 (2239)
• 팰린드롬? (10942)
• RGB 거리 2 (17404)
• 사이클 게임 (20040)
• ACM Craft (1005)
• 두 배열의 합 (2143)
• 줄 세우기 (2252)
• 세 용액 (2473)

문제 평균 티어: 골드 4

서론

13일부터 하루에 한 문제씩 풀었다. 블로그에 정리하는 것이 늦었다. 지금 위의 14문제를 모두 정리하고자 한다.
남는 시간에는 듀오 링고로 영어 공부도 하고 영상 편집도 조금 했다. Final Cut Pro를 배우는 중이다. Premiere Pro와 After Effects를 다룰 줄 알지만 Final Cut Pro로 iPad에서 편하게 컷편집을 하고 싶었다.

맥북을 정리할 겸 homebrew로 brewfile을 dump하고 필요한 패키지만 정리해서 맥북을 초기화하고 재설정했다.

---

다각형의 면적 (기하학)

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

간단명료한 문제지만 기하학을 잘 몰랐다.
이 문제는 신발끈의 공식을 < 알면 > 쉬운 문제다.

신발끈의 공식은 좌표평면 상에서 꼭짓점의 좌표를 알 때 다각형의 면적을 구할 수 있는 방법이다
기본 원리는 꼭짓점 좌표간의 차이로 길이를 구하고 서로 곱하면 직사각형의 면적을 알 수 있는데, 직사각형의 면적에서 나머지 삼각형의 면적을 빼는 식의 계산을 누적해서 총 다각형의 면적을 구하는 방법이라고 생각하면 쉽다.
(사실, 나는 수학을 아직 잘 못하기도 하고 기하학엔 더더욱 관심이 없다 보니까 정확한 식의 유도 방법은 모르겠다. 하지만 기초 원리는 이것이라고 생각하기로 했다. 때로는 그냥 외우고 넘어가는 것이 좋을때도 있다.)

꼭지점의 좌표가 차례대로 (2, 4), (3, -8), (1, 2)라면 다음과 같이 행렬의 꼴로 나타낼 수 있다

행렬의 마지막에 첫번째 좌표를 다시 적어준다. 다각형의 닫힌 경로를 보장하기 위해서라는데.. 구체적인 건 모르겠지만 일단 그냥 외우기로 했다. 어느정도 다각형을 닫아주는 게 직관적이기도 하고..

이런식으로 선으로 연결된 두 숫자를 곱해서 모두 더하고, 마찬가지로 y도 아래처럼 곱해서 모두 더한다.

그리고 각 더한 값의 차의 절댓값에 1/2 를 곱하면 다각형의 넓이가 된다.

생김새가 신발끈을 묶는 모양과 비슷해서(매우 합당한 이름이네 ...) 신발끈의 공식이라고 한다.

정말로 신발끈의 공식을 < 안다 > 면 쉽게 풀 수 있는 문제였다. 나는 몰랐었고, 따로 검색해서 알아봤다.
수학 공부를 더 열심히 해야겠다.

// 다각형의 면적
// https://www.acmicpc.net/problem/2166
// 2024-06-13

/*
신발끈 공식(shoelace formula)가 필요하다
*/

#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

struct Point {
    double x;
    double y;
};

int main() {
    int N;
    cin >> N;
    vector<Point> points(N);
    for (int i = 0; i < N; ++i) {
        double x, y;
        cin >> x >> y;
        points[i] = {x, y};
    }

    // 신발끈의 공식
    double sum1 = 0, sum2 = 0;
    for (int i = 1; i < N; ++i) {
        sum1 += points[i - 1].x * points[i].y;
        sum2 += points[i - 1].y * points[i].x;
    }

    // 처음 좌표와 다시 묶기
    sum1 += points[0].y * points[N - 1].x;
    sum2 += points[0].x * points[N - 1].y;

    double answer = (sum1 - sum2) / 2;
    cout << fixed << setprecision(1) << abs(answer);
    return 0;
}

---

용액 (투 포인터)

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

기본적인 투 포인터 문제다.
주어지는 용액의 특성값을 오름차순으로 정렬한 다음에, 인덱스를 가리키는 포인터 두개를 선언하고 인덱스가 가리키는 요소의 값을 합한 뒤(용액을 섞는다) 값을 보고 인덱스를 적절히 조절하면서 최선의 값을 찾아나가면 된다!

발상이 어렵지 않은 투 포인터 문제였다.
abs를 적용하지 않은 용액값의 합이 양수면 좀 더 낮은 수치의 산성 용액을 사용해야
함을, 음수면 좀 더 낮은 수치의 알칼리성 용액을 사용해야 함을 의미한다.

// 백준: 용액
// https://www.acmicpc.net/problem/2467
// 2024-06-13

/*
투 포인터 접근법: 두 인덱스를 적절히 바꿔가며 탐색
abs를 적용하지 않은 용액값의 합이 양수면 좀 더 낮은 수치의 산성 용액을 사용해야 함을, 음수면 좀 더 낮은 수치의 알칼리성 용액을 사용해야 함을 의미한다.
*/
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> liquid(N);
    for (int i = 0; i < N; ++i) {
        cin >> liquid[i];
    }

    int i = 0, j = N - 1; // 인덱스
    int ans_i = i, ans_j = j;
    int known_small_value = abs(liquid[i] + liquid[j]);
    while (i < j) {
        int cur_value = liquid[i] + liquid[j];
        if (abs(cur_value) < known_small_value) {
            ans_i = i;
            ans_j = j;
            known_small_value = abs(cur_value);
        }
        if (cur_value > 0)
            --j;
        else
            ++i;
    }

    cout << liquid[ans_i] << " " << liquid[ans_j];
    return 0;
}

---

트리와 쿼리 (DP, 그래프, 트리)

간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때
정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력하는 문제.

서브트리란 부모와 연결된 간선을 끊었을 때 생기는 트리, 즉 부모 밑의 모든 정점의 수를 구하는 문제이다.
입력에서 루트 번호 R이 주어졌기 때문에, 주어지는 간선에 맞춰서 트리를 구성하고 DFS로 하위에 있는 노드 수를 모두 저장해주면 된다.

문제를 처음 보면 막막할 수 있지만, 막상 구현은 어렵지 않았던 문제였다.

int dfs(int node) {
    visited[node] = true;
    int size = 1; // 자기 자신 포함
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            size += dfs(neighbor);
        }
    }
    subtree_size[node] = size;
    return size;
}

모든 서브트리는 최소 정점 수가 1이기 때문에 1로 초기화한다. (자기 자신이 있기 때문)
현재 루트 노드에서 연결되어 있는 모든 정점을 방문하고, 재귀적 DFS로 해당 정점에 연결되어 있는 모든 정점을 또 방문하고 subtree_size에 memoization하는 식으로 해결했다.

// 백준: 트리와 쿼리
// https://www.acmicpc.net/problem/15681
// 2024-06-13

/*
루트에 대해서 DFS를 돌리며 재귀적으로 서브트리 사이즈를 메모이제이션하기
*/

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<int> subtree_size;
vector<bool> visited;

int dfs(int node) {
    visited[node] = true;
    int size = 1; // 자기 자신 포함
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            size += dfs(neighbor);
        }
    }
    subtree_size[node] = size;
    return size;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, R, Q; // 정점, 루트, 쿼리 수
    cin >> N >> R >> Q;
    adj.assign(N + 1, vector<int>());
    subtree_size.assign(N + 1, 0);
    visited.assign(N + 1, false);
    for (int i = 0; i < N - 1; ++i) {
        int U, V;
        cin >> U >> V;
        adj[U].push_back(V);
        adj[V].push_back(U); // 양방향 그래프
    }

    dfs(R); // 루트부터 DFS 시작

    for (int i = 0; i < Q; ++i) {
        int U;
        cin >> U;
        cout << subtree_size[U] << "\n";
    }
    return 0;
}

---

수 나누기 게임 (수학, 정수론, 소수 판정)

《수 나누기 게임》의 규칙은 다음과 같습니다.

게임을 시작하기 전 각 플레이어는 
1부터 1,000,000사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.
매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.
결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 0이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.
승리한 플레이어는 1점을 획득하고, 패배한 플레이어는 1점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다.
《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

중복된 카드가 없다는 점을 이용해서 효율적으로 풀 수 있는 문제다. 특정 값의 카드 존재 여부를 배열에 기록해놓고 각 카드의 배수 값을 가지는 카드가 존재하면 그 값의 score을 변경하는 방법으로 풀었다.

// 백준: 수 나누기 게임
// https://www.acmicpc.net/problem/27172
// 2024-06-13

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<int> cards;
    vector<int> check(1'000'001, 0);
    for (int i = 0; i < N; ++i) {
        int t;
        cin >> t;
        cards.push_back(t);
        check[t] = 1; // 누군가가 해당 카드를 가지고 있다고 체크
    }

    vector<int> scores(1'000'001, 0);
    // 각 플레이어의 카드 넘버의 배수를 각각 체크하면서 해당 카드가 있다면, 결투
    for (int i = 0; i < N; ++i) {
        for (int j = cards[i] * 2; j < 1'000'001; j += cards[i]) {
            if (check[j] == 1) {    // 누군가 카드를 가지고 있음
                scores[cards[i]]++; // 이 카드 갖고 있는 사람의 점수 +1
                scores[j]--;        // 나눠진 카드 갖고 있는 사람의 점수 -1
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << scores[cards[i]] << " ";
    }

    return 0;
}

---

최소 스패닝 트리 (MST)

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

최소 스패닝 트리는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서, 그 가중치의 합이 최소인 트리를 말한다. 즉 최소의 가중치를 가지면서 모든 정점을 있는 그래프를 구하는 것.

사이클이 없는 그래프는 통신 네트워크 구축에 주로 쓰인다.

MST는 그리디하게 구할 수 있다. 생각보다 직관적이고 어렵지 않다

1. 간선 정보를 저장해놓고, 제일 가중치가 적은 간선부터 잇는다.
2. union-find를 사용해서 이미 간선 정보의 두 정점이 이어져 있다면 잇지 않는다. (사이클이 생기므로 신장 트리가 아니게 된다)

// 백준: 최소 스패닝 트리
// https://www.acmicpc.net/problem/1197
// 2024-06-13

/* Spanning Tree (신장 트리) 란?
모든 정점이 연결되어 있고, 사이클이 없는 그래프 (통신 네트워크 구축에 주로 쓰임)
Minimum Spanning Tree (최소 신장 트리) 는 그 중에서도 최소 가중치를 가지는 신장 트리

Spanning Tree 구하는 법: 단순히 탐색 도중에 사용된 간선을 모아서 만들 수 있음
MST 구하는 법: 탐욕적(Greedy method)으로 구함. 가중치 간선을 오름차순 정렬하고 이음. union-find로 루트 체크하고 사이클이 생기면 건너 뜀.
*/

// 의아한 사항: 신장 트리가 성립하려면 간선이 최소 V-1개어야 하지 않나? 본 문제에 이러한 조건은 명시되어 있지 않다.

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

// union-find 먼저 구현
int find(int node, vector<int> &parents) {
    if (parents[node] != node)
        parents[node] = find(parents[node], parents);
    return parents[node];
}

void unionSets(int u, int v, vector<int> &parents, vector<int> &rank) {
    int rootU = find(u, parents);
    int rootV = find(v, parents);

    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV]) {
            parents[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parents[rootU] = rootV;
        } else {
            parents[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, E; // 정점의 개수 V, 간선의 개수 E
    cin >> V >> E;
    vector<pair<int, pair<int, int>>> edges; // 간선 리스트
    vector<int> parents(V + 1, 0);
    vector<int> rank(V + 1, 0);
    for (int i = 1; i <= V; ++i) {
        parents[i] = i; // 부모 초기화
    }

    for (int i = 0; i < E; ++i) {
        int A, B, W;
        cin >> A >> B >> W;
        edges.push_back({W, {A, B}}); // A-B, W
    }

    sort(edges.begin(), edges.end());

    // 그리디하게 제일 가중치가 적은 간선부터 선택
    int weight_sum = 0;
    for (const auto &edge : edges) {
        int A = edge.second.first;
        int B = edge.second.second;
        if (find(A, parents) != find(B, parents)) { // 각 정점의 루트가 같으면 안됨
            weight_sum += edge.first;               // 가중치 합산
            unionSets(A, B, parents, rank);
        }
    }

    cout << weight_sum;

    return 0;
}

---

도시 분할 계획 (MST)

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

직관적이다,

1. 주어지는 그래프의 MST를 구하고 (본문: 유지비의 합을 최소로 하고 싶다)
2. MST에서 가장 큰 가중치 간선을 하나 제거한다. (본문: 두 개의 분리된 마을로 분할)

딱히 설명할 게 없다. MST 기본 문제.

// 백준: 도시 분할 계획
// https://www.acmicpc.net/problem/1647
// 2024-06-13

/*
딱 봐도, 최소 스패닝 트리(MST)의 응용 문제이다.
MST를 구하고 최대 간선 하나를 지우면 되는 문제.
*/

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

// union-find 구현
int find(int node, vector<int> &parents) {
    if (parents[node] != node)
        parents[node] = find(parents[node], parents);
    return parents[node];
}

void unionSets(int u, int v, vector<int> &parents, vector<int> &rank) {
    int rootU = find(u, parents);
    int rootV = find(v, parents);

    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV]) {
            parents[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parents[rootU] = rootV;
        } else {
            parents[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; // 집의 개수 N, 길의 개수 M
    cin >> N >> M;
    vector<pair<int, pair<int, int>>> edges;
    vector<int> parents(N + 1, 0);
    vector<int> rank(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        parents[i] = i;
    }
    for (int i = 0; i < M; ++i) {
        int A, B, W;
        cin >> A >> B >> W;
        edges.push_back({W, {A, B}}); // 간선 정보 추가
    }

    sort(edges.begin(), edges.end()); // 오름차순으로 정렬 (그리디)

    int weight_sum = 0;
    int max_edge = 0;
    for (const auto &edge : edges) {
        int A = edge.second.first;
        int B = edge.second.second;
        if (find(A, parents) != find(B, parents)) { // 사이클이 아닐 경우만
            unionSets(A, B, parents, rank);
            weight_sum += edge.first; // 가중치 합산
            max_edge = max(max_edge, edge.first);
        }
    }

    cout << weight_sum - max_edge;
    return 0;
}

---

스도쿠 (백트래킹, 구현)

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
단, 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 스도쿠를 숫자라고 가정하고 나열했을 때 81자리의 숫자가 제일 작은 경우를 출력한다.

올바른 스도쿠인지 판단하는 함수를 하나 작성하고, DFS로 valid한 값을 찾으면서 채워 나가는 간단한 스도쿠 문제였다. 유의해야 할 것은 특정 DFS 루트에서 이미 답을 발견했지만, 모두 백트래킹 되어서 끝까지 탐색하는 것을 막기 위해 solved라는 bool flag를 하나 만들고 답을 발견했다면 solved 를 true로 바꾸고 모두 가지치기 하는 것으로 해결했다.

문제에서 주어진 조건에서 답이 여러개라면 사전식으로 가장 앞서는 것을 출력하라고 했는데, 이것은 단순히 DFS탐색에서 브루트포스 - 백트래킹 하는 값을 오름차순으로 넣으면 해결 될 문제였다.

내 Solved.ac 의견:

일반적인 백트래킹 문제는 복수 해중 아무거나 출력해도 정답 처리해 줘서 비교적 널널한데,
여기선 '사전순' 조건이 붙어서 해당 조건을 구현하는 방식이 전혀 어렵진 않더라도 로직 구성에 있어서
조금의 실수라도 하면 (제 경우에는 적절하지 않은 return 타이밍)
제일 앞 사전 해가 아닌 스도쿠의 조건은 만족하지만 문제의 요구와는 다른 복수해가 나올 수 있기 때문에
정확하게 로직을 짜는 게 중요했습니다.

어렵지 않은 백트래킹 DFS 문제였지만 실수하기 쉬운 문제였다.

// 백준: 스도쿠
// https://www.acmicpc.net/problem/2239
// 2024-06-15

/*
문제 지문에 약간의 오해가 있다. 9개의 줄에 9개의 숫자로 답을 출력하는데 이것을 '사전순'으로 출력하라고 한다.
즉, 81자리의 수가 제일 작은 경우: 스도쿠를 왼쪽 위에서부터 쭉 나열했을 때 나오는 81자리의 숫자가 작은 순서대로.
그니까 좌측 위에서부터 우측으로 탐색을 한다고 했을 때 제일 작은 숫자부터 넣어보며 가능성을 탐색해야 한다.
*/

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

bool solved = false; // 해답이 발견되는 순간 true로 변경한다.
// 백트래킹 이전에 solved 여부를 체크함으로써 해답이 발견되면 모두 백트래킹 없이 return; 되도록 한다

// VALID CHECK 함수부터 만들자
bool lineCheck(int N, int r, int c, vector<vector<int>> &map) {
    for (int i = 1; i <= 9; ++i) {
        if (map[r][i] == N || map[i][c] == N) // 현재 위치의 직선 위치에 넣고자 하는 값이 있다면
            return false;
    }
    return true;
}

bool squareCheck(int N, int r, int c, vector<vector<int>> &map) {
    int start_r = ((r - 1) / 3) * 3 + 1;
    int start_c = ((c - 1) / 3) * 3 + 1;

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (map[start_r + i][start_c + j] == N)
                return false;
        }
    }

    return true;
}

bool check(int N, int r, int c, vector<vector<int>> &map) { return (lineCheck(N, r, c, map) && squareCheck(N, r, c, map)); }

void solution(int cur_r, int cur_c, vector<vector<int>> &map) {
    // 탐색 완료: 종료
    if (solved)
        return;
    if (cur_r == 10) {
        solved = true;
        return;
    }

    // 현재 위치가 비어있지 않으면 다음으로 넘기기
    if (map[cur_r][cur_c] != 0) {
        if (cur_c != 9) // 마지막 열이 아니라면 +1 탐색
            solution(cur_r, cur_c + 1, map);
        else // 마지막 열이라면 다음 행으로
            solution(cur_r + 1, 1, map);
        return;
    }

    // 현재 위치가 비어있다면:
    for (int n = 1; n <= 9; ++n) {
        if (check(n, cur_r, cur_c, map)) { // 넣어도 괜찮은 값 발견
            map[cur_r][cur_c] = n;         // 맵 업데이트
            // 재귀적으로 DFS 가지 생성
            if (cur_c != 9) // 다음 열
                solution(cur_r, cur_c + 1, map);
            else // 다음 행
                solution(cur_r + 1, 1, map);
            if (solved) // 만약 DFS의 제일 끝에서 해답이 나왔으면, solved 변수를 true로 바꾸는데. 백트래킹 이전에 가지치기를 해줘야 해답 데이터를 가져올 수 있음에 주의. 백트래킹 이후에 return하면 모든
                        // 데이터가 원본으로 돌아온다.
                return;
            map[cur_r][cur_c] = 0; // 답이 안나오면 백트래킹
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    vector<vector<int>> map(10, vector<int>(10)); // 1-based index
    for (int r = 1; r <= 9; ++r) {
        string line;
        cin >> line;
        for (int c = 1; c <= 9; ++c) {
            map[r][c] = line[c - 1] - '0';
        }
    }

    solution(1, 1, map);

    for (int r = 1; r <= 9; ++r) {
        for (int c = 1; c <= 9; ++c) {
            cout << map[r][c];
        }
        cout << '\n';
    }

    return 0;
}

---

팰린드롬? (DP)

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
S = 3, E = 3인 경우 1은 팰린드롬이다.
S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

발상이 어렵진 않았던 DP 문제, 길이가 3이상인 부분 문자열에 대해

차분하게 TC를 생각하다보면 팰린드롬의 규칙성을 찾을 수 있는 문제였고, DP의 점화식 구성이 어렵지 않았다.

아래의 세가지 규칙을 추론해서 풀었다:

1. 길이가 1인 부분 문자열은 모두 팰린드롬이다.
2. 길이가 2인 부분 문자열은 두 문자가 같을 때 팰린드롬이다.
3. 길이가 3 이상인 부분 문자열에 대해, dp[a][b] 는 dp[a+1][b-1]이 팰린드롬이고 str[a] == str[b] 일때 팰린드롬이다.

// 백준: 팰린드롬
// https://www.acmicpc.net/problem/10942
// 2024-06-17

/*
DP를 이용한 문제같다.
dp[a][b] = a~b 는 팰린드롬인지 여부
그러면 일단 base case 자기자신은 무조건 팰린드롬
// 문자열 배열: 1 2 1 3 1 2 1
dp[0][0] = true (1)
dp[1][1] = true (2) ...
dp[0][1] = (str[0] == str[1])
dp[1][2] = (str[1] == str[2])
dp[0][2] = (str[0] == str[2])
dp[1][3] = (str[1] == str[3])

정리:
길이가 1인 부분 문자열은 모두 팰린드롬이다.
길이가 2인 부분 문자열은 두 문자가 같을 때 팰린드롬이다.
길이가 3이상인 부분 문자열에 대해, dp[a][b] 는 dp[a+1][b-1]이 팰린드롬이고 str[a] == str[b] 일때 팰린드롬이다.
*/

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N; // 수열의 크기 N
    cin >> N;
    vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    // Generate DP table
    vector<vector<bool>> dp(N, vector<bool>(N, false));
    // CASE 1. 길이가 1인 부분 문자열은 모두 팰린드롬이다.
    for (int i = 0; i < N; ++i) {
        dp[i][i] = true;
    }
    // CASE 2. 길이가 2인 부분 문자열은 두 문자가 같을 때 팰린드롬이다.
    for (int i = 0; i < N - 1; ++i) {
        if (arr[i] == arr[i + 1]) {
            dp[i][i + 1] = true;
        }
    }
    // CASE 3. 길이가 3 이상인 부분 문자열에 대해, dp[a][b] 는 dp[a+1][b-1]이 팰린드롬이고 str[a] == str[b] 일때 팰린드롬이다.
    for (int len = 2; len < N; ++len) {
        for (int i = 0; i < N - len; ++i) {
            int j = i + len;
            if (dp[i + 1][j - 1] && arr[i] == arr[j]) {
                dp[i][j] = true;
            }
        }
    }

    int M; // 질문의 개수 M
    cin >> M;
    for (int i = 0; i < M; ++i) {
        int S, E;
        cin >> S >> E;
        cout << (dp[S - 1][E - 1] ? "1" : "0") << "\n";
    }

    return 0;
}

DP문제를 원래 이렇게 쉽게 풀진 않았는데, 이제 나름 DP 실력이 오른 것 같아서 문제를 풀고 기분이 좋았다!

---

RGB 거리 2 (DP)

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력하시오.

RGB 거리 1 문제와 유사하게, 간단한 DP 문제였지만 이번엔 집이 원형 구조로 이루어져있다. (실제론 그렇지 않지만, 1번 집과 N번 집이 인접한 것 처럼 영향받기 때문에 원형 구조라고 생각해도 된다.)

따라서 Memoization을 하는데 3D Vector을 선언해서 세번째 인덱스를 첫 집을 칠한 색으로 나눠서 분기별로 (첫 번째 집을 R로 칠했을 때, G로 칠했을 때, B로 칠했을 때) 나눠서 DP 배열을 채워 나갔다.

원형 구조임에 포커싱했지만 생각보단 단순했던 문제 ..
처음엔 3차 배열을 선언하면 MLE를 받을 줄 알았다.

// 백준: RGB거리 2
// https://www.acmicpc.net/problem/17404
// 2024-06-18

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; // 집의 수
    cin >> N;
    vector<vector<int>> prices(N, vector<int>(3));
    /*
    0. R
    1. G
    2. B
    */
    for (int i = 0; i < N; ++i) { // 0-based index
        int R, G, B;              // 각 비용
        cin >> R >> G >> B;
        prices[i][0] = R;
        prices[i][1] = G;
        prices[i][2] = B;
    }
    // dp[i][c][s] = k
    // 첫 집을 s로 칠하고, i번째 집을 c로 칠한 값까지 고려했을때의 최댓값 k
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(3, vector<int>(3, (~0U >> 2))));
    /* BASE CASE
        dp[0][0][0] = 첫번째 집을 RED로 칠하는 비용
        dp[0][1][1] = 첫번째 집을 GREEN으로 칠하는 비용
        dp[0][2][2] = 첫번째 집을 BLUE로 칠하는 비용
    */
    for (int i = 0; i < 3; ++i) {
        dp[0][i][i] = prices[0][i];
    }

    // 일단 첫번째 집을 어떤 색으로 칠했느냐에 따라 분기를 나눠야 한다.
    for (int st = 0; st < 3; ++st) {
        for (int i = 1; i < N; ++i) {
            dp[i][0][st] = min(dp[i - 1][1][st], dp[i - 1][2][st]) + prices[i][0];
            dp[i][1][st] = min(dp[i - 1][0][st], dp[i - 1][2][st]) + prices[i][1];
            dp[i][2][st] = min(dp[i - 1][0][st], dp[i - 1][1][st]) + prices[i][2];
        }
    }

    int min_price = (~0U >> 2);
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (i == j)
                continue;
            min_price = min(min_price, dp[N - 1][i][j]);
        }
    }

    cout << min_price;

    return 0;
}

---

사이클 게임 (분리 집합)

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

Union-find를 이용해서 사이클 판단을 하면되는 간단한 문제.
분리 집합 개념을 안다면 더 할 것이 없는 문제.

// 사이클 게임
// https://www.acmicpc.net/problem/20040
// 2024-06-20

/*
union-find를 사용해서 두 정점이 이미 같은 집합에 속하는지 확인한다.
속한다면 사이클을 이루는 것.
*/

#include <iostream>
#include <vector>
using namespace std;

int find(int v, vector<int> &parents) {
    if (parents[v] != v)
        parents[v] = find(parents[v], parents);
    return parents[v];
}

void unionSets(int u, int v, vector<int> &parents, vector<int> &rank) {
    int rootU = find(u, parents);
    int rootV = find(v, parents);

    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV]) {
            parents[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parents[rootU] = rootV;
        } else {
            parents[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; // 점의 개수 n
    int m; // 차례의 수 m
    cin >> n >> m;
    vector<int> parents(n);
    vector<int> rank(n, 0);
    for (int i = 0; i < n; ++i) {
        parents[i] = i;
    }

    // 게임 시작
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        if (find(u, parents) == find(v, parents)) { // 사이클
            cout << i;
            return 0; // 종료
        }
        unionSets(u, v, parents, rank);
    }
    cout << "0";
    return 0;
}

---

ACM Craft (위상 정렬)

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.

이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.
이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

정리하자면, 건물 W를 건설 완료 하는데에 드는 최소 시간을 출력해야 하는데, 건물 W를 건설 완료하려면 W로 진입하는 간선을 가지는 모든 노드가 건설 완료 되어야 한다.

즉 위상 정렬을 사용하는 문제

위상 정렬이란

위상 정렬이란 특정 작업에 순서가 정해져 있는 경우 (A 작업을 하려면 B 작업을 끝내야 함)
그 순서를 결정하기 위해 사용하는 정렬 알고리즘이다.

위상 정렬은 DAG(방향이 있는 비순환 그래프)에서만 사용할 수 있다. 왜냐하면 순서라는 것은 무조건 방향이 있는 것이고, 모든 순서의 처음엔 시작점이 있을텐데 그래프에 사이클이 있다면 시작점조차 특정할 수 없기 때문이다.

진입 차수와 진출 차수

진입 차수란 특정 노드로 들어오는 간선의 개수,
진출 차수란 노드에서 나가는 간선의 개수이다. 진입 차수와 진출 차수를 알아야 위상 정렬을 할 수 있다.

위상 정렬 방식은 다음과 같다. (이 알고리즘도 꽤나 직관적이다)

1. 진입 차수가 0인 노드를 큐에 삽입한다. (해당 노드를 수행하기 위해 선행 되어야 할 노드가 없는 것이므로. 시작점 이다)
2. 큐가 빌때까지 다음 작업을 반복한다:
   1. 큐에서 원소를 꺼내고, 해당 원소에서 나가는 간선을 모두 제거한다 (도착 노드의 진입 차수를 차감한다)
   2. 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다.

이를 다음과 같이 깔끔하게 구현할 수 있다:

 while (!q.empty()) { // 큐가 빌때까지 반복
            int cur_node = q.front();
            q.pop();

            for (const int &next : adj[cur_node]) {
                dist[next] = max(dist[next], dist[cur_node] + build_time[next]);
                if (--in_degree[next] == 0) {
                    q.push(next);
                }
            }
        }

그러면 이제 위상 정렬로 차례대로 탐색하면서, dist 값을 업데이트 하는 방법으로 ACM Craft 문제를 쉽게 해결할 수 있다.

// 백준: ACM Craft
// https://www.acmicpc.net/problem/1005
// 2024-06-20

/*
위상 정렬을 이용해야 한다. 위상 정렬은 사이클이 없는 방향그래프에서만 사용할 수 있고.
순서가 정해져있는 일련의 작업을 수행해야 할 때 사용할 수 있다.

* 진입 차수와 진출 차수
: 진입 차수는 특정한 노드로 들어오는 간선의 수, 진출 차수는 특정한 노드에서 나가는 간선의 수.
진입 차수가 0인 노드를 큐에 넣는다 (현재 노드를 실행하기 위해 선행해야 할 노드가 없다 (즉, 부모))
큐가 빌떄까지 다음을 반복한다:
1. 큐에서 원소를 꺼내서, 해당 노드에서 나가는 간선을 그래프에서 제거한다.
2. 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다.
*/

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC;
    cin >> TC;
    while (TC--) {
        int N; // 건물의 개수 N
        int K; // 건물간의 건설순서 규칙 개수 K
        cin >> N >> K;
        vector<int> build_time(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            cin >> build_time[i];
        }

        vector<int> in_degree(N + 1, 0);
        vector<vector<int>> adj(N + 1, vector<int>());
        for (int i = 0; i < K; ++i) {
            int X, Y; //  건설 순서 X -> Y
            cin >> X >> Y;
            adj[X].push_back(Y);
            ++in_degree[Y]; // Y의 진입 차수 증가
        }

        int W;
        cin >> W; // W 입력

        queue<int> q;
        vector<int> dist(N + 1, 0);
        // 진입 차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= N; ++i) {
            if (in_degree[i] == 0) {
                q.push(i);
                dist[i] = build_time[i];
            }
        }

        while (!q.empty()) { // 큐가 빌때까지 반복
            int cur_node = q.front();
            q.pop();

            for (const int &next : adj[cur_node]) {
                dist[next] = max(dist[next], dist[cur_node] + build_time[next]);
                if (--in_degree[next] == 0) {
                    q.push(next);
                }
            }
        }

        cout << dist[W] << "\n";
    }
    return 0;
}

---

두 배열의 합 (누적 합, 해시를 사용한 맵)

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

솔직히 말해서 문제를 보자마자 풀기 싫어졌다. 너무 복잡해 보였기 때문이다.
실제로 쉽진 않았지만, 나름 풀만 했다.

두 배열의 부분 합이 T가 되는 쌍을 구하는 문제다.

사고 과정:

메모리 제한이 64MB이기 때문에 vector을 사용하면 안되고, unordered_map을 사용해야 할 것 같다.
unordered_map에 key를 배열의 구간 합으로 만들 수 있는 값으로, value를 그 값의 출현 빈도로 해야겠다.
0부터 T까지 반복을 돌리면서(i) a_map[i]의 값이 있을때 b_map[T-i]의 값도 있다면 두 값을 곱한 값을 정답에 누적할 수 있다.

최적화 포인트:

1. unordered_map으로 빈도 수 저장
2. 부분 배열의 합을 매번 계산하지 않고, 누적합 배열로 계산

제일 처음에 아이디어가 생각나지 않아서 naive하게 풀었고, 그 뒤로 누적합을 사용하면 훨씬 최적화 할 수 있겠다는 생각이 들었다.

또, a_map[i]의 값이 존재하는 지 판단하는 과정을 for문으로 무작정 브루트포스 탐색했는데, 이렇게 10억번의 연산을 하는 것은 너무 비효율적이었고. 대신 map의 iterator을 사용해서 키가 존재하는 값만 찾아가도록 최적화 했다.

만약 배열 A의 맵에 현재 인덱스 키가 존재한다면, B의 맵에 T-index 키가 있는지 체크하고 있다면 두 value의 곱을 정답에 누적할 수 있다 (쌍의 개수이기 때문)

// 백준: 두 배열의 합
// https://www.acmicpc.net/problem/2143
// 2024-06-27

/* 사고 과정:
각 배열에서 특정 구간의 합으로 만들 수 있는 숫자를 저장하기.
메모리 제한이 64MB이기 때문에 vector을 사용하면 안되고, unordered_map을 사용해야 할 것 같다.
unordered_map에 key를 배열의 구간 합으로 만들 수 있는 값으로, value를 그 값의 출현 빈도로 해야겠다.
1,000,000,000
0부터 T까지 반복을 돌리면서(i) a_map[i]의 값이 있을때 b_map[T-i]의 값도 있다면 두 값을 곱한 값을 정답에 누적할 수 있다.

최적화 포인트:
1. unordered_map으로 빈도 수 저장
2. 부분 배열의 합을 매번 계산하지 않고, 누적합 배열로 계산
*/

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    // 입력
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    int a_size, b_size;
    cin >> a_size;
    int a[a_size];
    int prefix = 0; // 누적합
    for (int i = 0; i < a_size; ++i) {
        cin >> a[i];
        a[i] += prefix;
        prefix = a[i];
    }

    cin >> b_size;
    int b[b_size];
    prefix = 0; // 초기화
    for (int i = 0; i < b_size; ++i) {
        cin >> b[i];
        b[i] += prefix;
        prefix = b[i];
    }

    // 효율적으로 빈도 수를 저장하기 위해 map 선언
    unordered_map<int, int> map_b;
    unordered_map<int, int> map_a;

    for (int len = 0; len < a_size; ++len) {
        for (int start = 0; start < a_size - len; ++start) {
            int end = start + len;
            if (start == 0) // edge case
                map_a[a[end]]++;
            else
                map_a[a[end] - a[start - 1]]++;
        }
    }

    for (int len = 0; len < b_size; ++len) {
        for (int start = 0; start < b_size - len; ++start) {
            int end = start + len;
            if (start == 0) // edge case
                map_b[b[end]]++;
            else
                map_b[b[end] - b[start - 1]]++;
        }
    }

    // 해시함수의 오버헤드때문에 생각하는 것보다 10억번 탐색은 훨씬 오래 걸린다.
    // int answer = 0;
    // for (int i = 0; i < 1'000'000'000; ++i) {
    //     answer += map_a[i] * map_b[1'000'000'000 - i];
    // }

    // unordered_map<int, int>::iterator을 이용해서 효율적으로 탐색

    long long answer = 0; // 배열이 모두 0일때 answer가 int 범위를 벗어날 수 있다.
    for (const auto &pair_a : map_a) {
        int key_a = pair_a.first;
        int value_a = pair_a.second;
        int target_b = T - key_a;
        if (map_b.find(target_b) != map_b.end()) {
            answer += static_cast<long long>(value_a) * map_b[target_b];
        }
    }

    cout << answer;

    return 0;
}

---

줄 세우기 (DAG, 위상 정렬)

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

줄을 세우는 순서가 중요한 문제다. DAG(방향 비순환 그래프) 에서 차례대로 정렬하는 알고리즘인 위상 정렬을 사용해서 쉽게 처리할 수 있었다.

그래프 간선 정보 A -> B가 A가 B보다 앞에 와야함을 의미한다고 할 때,
위상 정렬의 진입 차수가 0인 노드는 키가 제일 크다고 할 수 있다 (제일 앞에 와야 함)
그리고 그 노드의 간선을 모두 제거했을 때 새롭게 진입 차수가 0인 노드가 그 다음으로 온다고 할 수 있다.

비교 정보가 A B로 주어지는데, A가 B의 앞에 서야한다는 정보이다.
이를 그래프 상에서 A -> B로 표현하자. 그러면 진입차수가 0개인 노드가 제일 키가 크다고 할 수 있다.

위상 정렬을 이용해서 풀어야 한다.
진입차수와 진출차수. 진입차수가 0인 노드를 큐에 넣고 다음을 반복한다
1. 큐에서 원소를 꺼내서, 해당 노드가 나가는 간선을 제거한다(진입차수를 -1한다).
2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

// 백준: 줄 세우기
// https://www.acmicpc.net/problem/2252
// 2024-06-28

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    /*
    비교 정보가 A B로 주어지는데, A가 B의 앞에 서야한다는 정보이다.
    이를 그래프 상에서 A -> B로 표현하자. 그러면 진입차수가 0개인 노드가 제일 키가 크다고 할 수 있다.

    위상 정렬을 이용해서 풀어야 한다.
    진입차수와 진출차수. 진입차수가 0인 노드를 큐에 넣고 다음을 반복한다
    1. 큐에서 원소를 꺼내서, 해당 노드가 나가는 간선을 제거한다(진입차수를 -1한다).
    2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
    */

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N; // 학생 수 N (1번부터 N번까지)
    int M; // 비교 회수 M
    cin >> N >> M;
    vector<vector<int>> adj(N + 1, vector<int>());
    vector<int> in_degree(N+1, 0);
    for (int i=0;i<M;++i) {
        int A, B;
        cin >> A >> B;
        adj[A].push_back(B);
        ++in_degree[B];
    }

    queue<int> q;
    for (int i=1;i<=N;++i) {
        // 진입차수가 0인 노드를 큐에 삽입
        if (in_degree[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int cur_i = q.front();
        q.pop();
        cout << cur_i << " ";
        for (const auto& next : adj[cur_i]) {
            if (--in_degree[next] == 0) { // 해당 노드가 나가는 간선 제거
                q.push(next); // 새롭게 진입차수가 0이 된 노드 큐에 삽입
            }
        }
    }


    return 0;
} 

---

세 용액 (투 포인터, 정렬)

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.

두 용액 문제에서 하나의 용액이 더 추가된, 즉 투 포인터가 아니라 Three Pointer을 써야 하는 문제다.
처음엔 extra pointer의 인덱스를 어떻게 관리할지 고민이 많았고, 아예 투 포인터 문제가 아니라 다른 유형인지도 생각했다.

하지만 전체 용액의 수 N의 크기가 작다는 점에서(5000 이하) 그냥 첫번째 포인터를 고정 시켜놓고, 투 포인터 탐색을 N번 하면 되겠다고 생각했다.

즉, 첫번째 포인터를 1로 하고 돌리고,, 2으로하고 돌리고 .. 3으로 하고 돌리는 식으로.
모든 분기마다 계산을 해보는 식으로 최적값을 찾는 방법을 사용했다.

포인터 인덱스 i, j, k를 선언하고
i를 1부터 N-2까지 각 분기별로 순회하도록 했다. (가능한 모든 i의 위치에 대해 계산을 하기 위함)
j는 항상 i+1로 (i 이전은 탐색할 필요가 없다, 이미 이전 분기에서 계산된 값이기 때문이다.)
k는 항상 N-1로 (마지막 용액 인덱스를 가리키도록 한다)

로 설정한 뒤 투 포인터 탐색으로 최적값을 찾고, 도출한 값이 0일 경우 더 이상의 최적해가 없음을 확신할 수 있음으로 조기에 루프를 탈출하도록 했다.

구현은 쉽지만, i를 고정시키고 그냥 N번 돌리자는 발상은 무식하면서도 떠올리기 어려운 아이디어였다.
등잔 밑이 어둡다.

// 백준: 세 용액
// https://www.acmicpc.net/problem/2473
// 2024-06-29

/*
전형적인 투 포인터 문제의 변형
세개의 포인터를 선언: i, j, k
i를 고정시켜 놓고 j와 k를 이용해서 투 포인터 탐색.
*/

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N; // 용액의 수
    cin >> N;
    vector<ll> liquid(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> liquid[i];
    }

    sort(liquid.begin(), liquid.end());

    bool stop = false; // 플래그
    ll known_answer = LLONG_MAX;
    tuple<ll, ll, ll> ans_liquid;

    for (ll i = 0; i < N - 2 && !stop; ++i) {
        ll j = i + 1; // i의 바로 다음
        ll k = N - 1; // 마지막 용액
        while (j < k) {
            ll mix_value = liquid[i] + liquid[j] + liquid[k];

            // 정답 갱신
            if (known_answer > abs(mix_value)) { // mix_value가 알려진 정답보다 0에 가깝다면
                ans_liquid = tie(liquid[i], liquid[j], liquid[k]);
                known_answer = abs(mix_value);
            }

            if (mix_value > 0) {
                --k;
            } else {
                ++j;
            }
        }

        if (known_answer == 0) {
            stop = true;
            break;
        }
    }

    cout << get<0>(ans_liquid) << " " << get<1>(ans_liquid) << " " << get<2>(ans_liquid);

    return 0;
}

---

끝.

이렇게 6월 13일부터 오늘까지의 알고리즘 공부 기록을 정리했다.
앞으로의 계획은 다음과 같다:

1. 알고리즘 공부
2. 영어 공부
3. Final Cut Pro 공부
4. 수학 공부 (이산수학)