240611: 클래스 4 금장 달성! LCS와 사전 순 최대 공통 부분 수열

2024-06-11

클래스 4 금장 달성

클래스 4 금장을 달성했다. 나머지 문제는 무난하게 풀었지만 사전 순 최대 공통 부분 수열 문제에서 아직 known algorithm에 대해 견고하지 못한 것 같다고 생각했다. 보자마자 LCS가 생각난 문제여서 LCS를 복습했다. 역추적까지 거의 완벽하게 이해했다. (직관적으로 와닿진 않지만, 대부분 2차원 배열로 푸는 것들은 직관적이지 않은 것 같다)

별표 표시된 문제는 클래스 4의 문제는 아니지만, 복습을 위해 따로 풀어본 문제이다.

푼 문제:

• 최소 비용 구하기 2 (11779 - 골드 3)
• 사전 순 최대 공통 부분 수열 (30805 - 골드 4)
• LCS 3 * (1958 - 골드 4)
• LCS 2 * (9252 - 골드 4)
• 아기상어 (16236 - 골드 3)

 

---

최소 비용 구하기 2 (데이크스트라 역추적)

기초적인 다익스트라 최단거리 역추적 문제이다, 다익스트라와 다른 점은 그래서 최단 경로가 실제로 어떤 경로인지 역추적* 해야 된다는 것.

간단하게 더 짧은 경로로 테이블이 업데이트 될때마다, 역추적을 위한 이전 경로를 저장해주면 된다. (그냥 단순히 업데이트 될 노드의 인덱스에 현재 노드 정보를 업데이트 해준다)

딱히 어려운 발상은 아닌데, 다익스트라를 완전히 이해해야만 할 수 있는 발상이라는 점에서.. 티어가 높은듯?

정답 코드

// 백준: 최소비용 구하기 2
// https://www.acmicpc.net/problem/11779
// 2024-06-04
// 다익스트라 최단거리 역추적

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
#define INF (~0U >> 2)

int n, m;         // 도시 개수 n, 버스 개수 m
vector<int> path; // 역추적 경로 저장

int dijkstra(int start, int target, vector<vector<pair<int, int>>> &adj) {
    vector<int> dist(n + 1, INF);
    dist[start] = 0; // 시작 노드 0으로
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        int cur_weight = pq.top().first;
        pq.pop();

        if (cur_weight > dist[cur_node])
            continue; // 이미 알려진 최단 거리보다 길면 스킵

        for (const auto &next : adj[cur_node]) {
            int new_weight = cur_weight + next.first;
            if (new_weight < dist[next.second]) {
                dist[next.second] = new_weight;
                pq.push({new_weight, next.second});
                path[next.second] = cur_node; // 역추적 경로 설정
            }
        }
    }

    return dist[target];
}

void printPath(int start, int target) {
    vector<int> result;
    for (int at = target; at != -1; at = path[at])
        result.push_back(at);
    reverse(result.begin(), result.end());
    cout << result.size() << "\n";
    for (const auto &next : result)
        cout << next << " ";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;          // 도시 개수 n, 버스 개수 m
    path.assign(n + 1, -1); // 역추적 경로 -1로 초기화
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        adj[from].push_back({weight, to});
    }
    int start, target;
    cin >> start >> target;
    cout << dijkstra(start, target, adj) << "\n";
    printPath(start, target);
    return 0;
}

---

아기 상어 (그래프 이론, 시뮬레이션, 구현)

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

재밌어 보이는 시뮬레이션 문제였다. 그냥 느긋하게 구현하라는거 구현하면 되는 문제. 사실 그래프 탐색과 구현 문제는 딱히 특별한 아이디어가 들어가지 않는 이상 이제 너무 쉽게 풀어버리는 것 같다. 설명할 게 없다.

근데 주의할점은 지문을 꼼꼼히 읽어봐야 한다. 구현해야 할 짜잘한 디테일이 꽤 있다.

먼저 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹는다.
거리가 가장 가까운 물고기도 1마리보다 많다면, 제일 위에 있는 물고기를 먹는다.
그래도 1마리보다 많다면, 제일 왼쪽에 있는 물고기를 먹는다.

이걸 구현하는 아이디어가 까다로울 수 있다. 근데 나는 간단히 그냥 좌측 -> 우측, 상단 -> 하단 순으로 탐색 하고, '>' 연산자로 비교를 해서 자연스럽게 제일 가깝고, 제일 상단, 좌측에 있는 물고기를 고르도록 했다.

또 중요한건 "자신의 크기와 같은 수의 물고기를 먹었다면" 이다. 그니까 아기 상어 크기가 3이라면, 물고기 3마리를 먹어야 크기가 4가 된다. 관리할 상태가 많으므로 구조체로 관리해주었다.

맵이 모든 가중치가 똑같은 격자판이라서 단순히 좌표차 계산으로 거리를 계산할 수 있다고 생각했으나. (맨해튼 거리) 자기보다 큰 물고기는 지나갈 수 없으므로 다익스트라를 썼다.

내 의견:

약간의 구현력이 필요한 BFS 문제였습니다. 맨해튼 거리를 이용해서 효율적으로 거리를 구하려고 했는데 자기보다 큰 물고기는 못 지나간다는 조건이 있어서 BFS를 사용했습니다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다는 조건이 있기 때문에 다익스트라로 최단 거리 배열을 채워놓고 상단에서부터 좌측 -> 우측 순서로 탐색하며 같은 최단거리라면 업데이트 하지 않는 방법으로 자연스럽게 우선 순위를 적용했습니다. 전형적인 BFS 문제에 약간의 구현력이 추가되어서 골드 3이 적당한 것 같습니다. 무난하고 재밌게 풀었습니다.

정답 코드

// 백준: 아기 상어
// https://www.acmicpc.net/problem/16236
// 2024-06-04

#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
#define INF (~0U >> 2)

vector<vector<int>> map;
int N; // 공간의 크기

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

struct Shark {
    int r;
    int c;
    int size = 2;
    int streak = 0;
};

int eatNearestFish(Shark &baby) {
    // 다익스트라로 현재 아기상어 위치에서 각 모든 노드까지의 위치 판단 (자기보다 큰 물고기는 지나갈 수 없다. 크기가 같은 물고기는 지나갈 순 있지만 먹을 순 없다)
    vector<vector<int>> dist(N, vector<int>(N, INF));
    // 상단에서부터 좌측 -> 우측 순서로 탐색. (거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.)
    // 같은 최단거리라면 업데이트 하지 않음 (왼쪽 상단 물고기 우선 적용)

    // 일단 다익스트라로 dist 배열 먼저 채우자
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; // 가중치, r, c
    dist[baby.r][baby.c] = 0;                                                                                            // 아기상어 위치 0으로 초기화
    pq.push({0, {baby.r, baby.c}});

    while (!pq.empty()) {
        int cur_r = pq.top().second.first;
        int cur_c = pq.top().second.second;
        int cur_weight = pq.top().first;
        pq.pop();

        if (cur_weight > dist[cur_r][cur_c]) // 알려진 최단 거리보다 길다면 스킵
            continue;

        for (int i = 0; i < 4; ++i) {
            int next_r = cur_r + dr[i];
            int next_c = cur_c + dc[i];
            if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < N && map[next_r][next_c] <= baby.size) { // VALID CHECK
                if (cur_weight + 1 < dist[next_r][next_c]) {
                    dist[next_r][next_c] = cur_weight + 1;
                    pq.push({cur_weight + 1, {next_r, next_c}});
                }
            }
        }
    }

    // 상단 -> 하단, 좌측 -> 우측 순서로 탐색
    int known_shortest_distance = INF;
    pair<int, int> targetPos = {-1, -1}; // 먹을 생선 좌표
    for (int ir = 0; ir < N; ++ir) {
        for (int ic = 0; ic < N; ++ic) {
            int fish = map[ir][ic];                           // 해당 칸의 정보
            if (fish != 0 && fish != 9 && fish < baby.size) { // 빈칸도 아니고 아기 상어의 위치도 아니고, 먹을 수 있는 물고기라면
                if (dist[ir][ic] < known_shortest_distance) { // 알려진 최단 거리보다 더 짧을 경우에만 갱신
                    known_shortest_distance = dist[ir][ic];   // 알려진 최단 거리 업데이트
                    targetPos = {ir, ic};                     // 타겟 업데이트
                }
            }
        }
    }

    // 탐색 완료
    if (known_shortest_distance == INF) // 만약 아무 물고기도 먹을 수 없으면 -1 리턴
        return -1;

    // 맵을 업데이트 하고 가중치 리턴
    map[baby.r][baby.c] = 0;                    // 아기상어가 있던 자리 빈칸으로 변경
    map[targetPos.first][targetPos.second] = 9; // 새로운 아기 상어의 자리 업데이트
    baby.r = targetPos.first;
    baby.c = targetPos.second; // 실질적인 아기 상어 좌표값 업데이트
    // (문제 본문:) 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
    ++baby.streak;                  // 물고기를 먹은 횟수를 추적
    if (baby.streak == baby.size) { // 자신의 크기와 같은 수의 물고기를 먹었다면
        ++baby.size;                // 아기 상어의 크기를 키우고
        baby.streak = 0;            // 추적 변수를 0으로 초기화합니다.
    }

    return known_shortest_distance; // 가중치 리턴
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Shark baby;
    cin >> N;
    map.assign(N, vector<int>(N, 0));
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            cin >> map[r][c];
            if (map[r][c] == 9) { // 아기 상어 위치 초기화
                baby.r = r;
                baby.c = c;
            }
        }
    }

    // 맨해튼 거리로 거리를 파악하... 려고 했으나 자기보다 큰 물고기는 지나갈 수 없으므로 다익스트라를 써야할 듯
    int T = 0; // 시간 정보
    while (true) {
        int temp = eatNearestFish(baby);
        if (temp == -1) // 먹을 물고기가 없으면 종료
            break;
        T += temp;
    }

    cout << T;
    return 0;
}

---

LCS 시리즈 문제들 (DP)

• LCS 2
• LCS 3
  의 문제가 포함된다.

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어서 ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

푸는 방법은 문제를 열심히 관찰하지 않으면 알아내기 힘들 수 있다. 애초에 풀이 자체가 직관적이지 않다 . 만약 이게 known algorithm이 아니었다면 꽤나 애먹었겠다.

결론적으로 DP를 사용하는 것인데, 이 규칙은 text로만 설명하기 어렵고, 직접 조금 소규모의 케이스를 테이블화해서 디버깅하다보면 규칙을 발견할 수 있다.

제일 메인 로직은 현재 문자열이 서로 같으면 이전 테이블의 문자열에서 +1을 하고, 다르다면 이전 문자열들중 큰 것을 계승한다.

역추적도 단순히 DP 테이블을 채우는 과정을 역으로 한 것이지만, LCS에 대한 이해가 부족하면 발상하기 힘들 것이다.

// 백준: LCS 2
// https://www.acmicpc.net/problem/9252
// 2024-06-09
// 복습

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

int main() {
    string a, b;
    cin >> a >> b;
    vector<vector<int>> dp(a.length() + 1, vector<int>(b.length() + 1, 0));
    for (int i = 1; i <= a.length(); ++i) {
        for (int j = 1; j <= b.length(); ++j) {
            if (a[i - 1] == b[j - 1]) {          // 문자열이 같으면
                dp[i][j] = dp[i - 1][j - 1] + 1; // 이전 문자열 + 1
            } else {                             // 문자열이 다르면 이전 문자열 중 큰 것
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    int n = a.length();
    int m = b.length();

    cout << dp[n][m] << "\n";

    string lcs; // 역추적
    while (n > 0 && m > 0) {
        if (dp[n][m] == dp[n - 1][m]) { // 같은 값이 있으면 그쪽으로 진행
            n--;
        } else if (dp[n][m] == dp[n][m - 1]) {
            m--;
        } else {
            lcs.push_back(a[n - 1]); // 같은 값이 없으면 if a[i - 1] == b[j - 1], dp[i][j] = dp[i - 1][j - 1] + 1; 이 된것임으로 LCS로 선택됨
            n--;
            m--;
        }
    }

    reverse(lcs.begin(), lcs.end());
    if (lcs.size() != 0)
        cout << lcs;
    return 0;
}

---

사전 순 최대 공통 부분 수열 (그리디 알고리즘)

수열 A와 수열 B가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.

- 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
- 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
- 길이가 0인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.

보자마자 LCS가 떠올랐던 문제, 규칙을 찾아보니 항상 문제에서 말하는 "사전 순 최대 공통 부분 수열"은 LCS에서 그리디적으로 만들 수 있어 보였다.

따라서 첫 아이디어는 다음과 같았다.

1. 주어진 수열 A, B에 대해서 LCS를 구한다.
2. LCS 역추적으로 원본 문자를 구하고, 그리디적으로 사전 순 맨 마지막 패턴을 구한다.

근데 문제는 LCS 역추적 과정에 있었다 (추측컨대) 총 17번의 WA를 받았고 문제는 아마 .. LCS 역추적 과정에서 주의해야 할 것이 길이가 같은 다른 문자가 있을 수 있다는 것. 그러면 항상 이게 최적해임을 보장할 수 없는데 .. 그래서 역추적을 재귀적으로 구현해서 모든 문자에 대해서 그리디를 적용해봤으나 실패했다. 시간초과가 나거나 오답이 떴다. 그래서 17번의 실패 끝에 방법을 바꿨다.

그냥 처음부터 LCS를 쓰지 않고 그리디적으로 풀기로..

내 풀이:

두 수열 A, B에 대해서 다음을 반복한다.

1. A에서 max_element 를 찾는다 (중복시 제일 앞 인덱스)
2. B에서 A의 max_element가 나오는 제일 앞 인덱스를 찾는다

만약 2번이 성공하면 해당 인덱스부터 .end()만 남기고 1~2를 반복한다.
실패하면 A의 max_element 바로 다음의 max_element로 재개한다.

그리고 바로 풀렸다 ^^... naive 한 풀이가 정답이었다.
삽질을 정말 많이 해서 어렵게 느껴진 문제 .. (실제로도 LCS인척 해서 어려운 것 같다)
애초에 LCS에 항상 사전 순 최대 공통 부분 수열이 포함되어있다는 전제 자체가 증명되지 않은건데.. 조금만 더 생각해 볼 걸 그랬다 (근데 아직도 진짜 이 전제가 틀려서 틀렸는지, 재귀 역추적에서 오류가 있어서 틀린건지, 내 그리디 전제에 문제가 있어서 틀린건지 모른다)

// 백준: 사전 순 최대 공통 부분 수열
// https://www.acmicpc.net/problem/30805
// 2024-06-11

/* 내 풀이:
두 수열 A, B에 대해서
A에서 max_element 를 찾는다 (중복시 제일 앞 인덱스)
B에서 A의 max_element가 나오는 제일 앞 인덱스를 찾는다
if 성공 then 해당 인덱스부터 .end()만 남기고 단계 반복
if 실패 then A의 max_element 바로 다음의 max_element로 재개


풀기 이전의 시행착오들.. :
처음에는 LCS가 바로 생각났다. 규칙을 찾아보니 사전 순 최대 공통 부분 수열은 항상 LCS의 조합으로 만들 수 있었다.
그래서 LCS를 구하고 거기서 그리디적으로 사전 순 최대를 만드는 순서를 찾으면 되는 문제라고 생각했다.
근데 문제는 LCS 역추적에 있었다, LCS는 공통해가 있을 수 있는데 이 모든 루트를 역추적으로 구하려면 재귀적 탐색을 해야했다. **TLE**가 났다.
그냥 naive하게 푸니까 풀리는 것 같다.
*/

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

vector<int>::iterator find_max_element_except(vector<int> &T, int start, int except) { // 특정 값을 제외하고 max_element
    if (T.empty())
        return T.end();

    vector<int>::iterator max_it = T.end();
    int max_elem = 0;

    for (vector<int>::iterator it = T.begin() + start; it != T.end(); ++it) {
        if (*it == except)
            *it = -1;
        if (*it > max_elem && *it != except) {
            max_elem = *it;
            max_it = it;
        }
    }

    return max_it;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a_len, b_len; // 수열 A, B 길이
    cin >> a_len;
    vector<int> A(a_len);
    for (int i = 0; i < a_len; ++i) {
        cin >> A[i];
    }
    cin >> b_len;
    vector<int> B(b_len);
    for (int i = 0; i < b_len; ++i) {
        cin >> B[i];
    }

    int prev_max = -1; // 이전 최댓값 (재탐색 방지)
    int A_start_index = 0;
    int B_start_index = 0;
    vector<int> LLCS;
    while (true) {
        auto A_iter = find_max_element_except(A, A_start_index, prev_max); // 제일 처음 등장하는 이전 최댓값을 제외한 최댓값 찾기
        if (A_iter != A.end()) {                                           // 탐색 성공
            // B에서 A의 max_element가 나오는 제일 앞 인덱스를 찾는다
            bool found = false;
            for (int i = B_start_index; i < b_len && !found; ++i) {
                if (B[i] == *A_iter) {                               // 탐색 성공
                    A_start_index = distance(A.begin(), A_iter) + 1; // 수열 A 자르기 (시작 인덱스 조정)
                    B_start_index = i + 1;
                    LLCS.push_back(*A_iter);
                    found = true;
                }
            }
            if (!found) // 탐색 실패 : A의 max_element 바로 다음의 max_element로 재개
                prev_max = *A_iter;
        } else { // A 수열에서 최댓값을 찾을 수 없음 : 종료
            break;
        }
    }

    cout << LLCS.size() << "\n";
    for (const auto &next : LLCS) {
        cout << next << " ";
    }

    return 0;
}

---

끝.

이렇게! 6월 11일부로 클래스 4 금장을 달성했다.
비하인드 스토리가 있다면 사실 아기 상어 문제를 푼 시점에서 클래스 4 금장을 달성했었는데 자고 일어나니까 클래스 4에 새로운 문제가 추가되면서 은장으로 강등됐다...

그래서 아 뭐야 하고 사전 순 최대 공통 부분 수열 문제를 푸는데 LCS를 복습해야 할 것 같아서 LCS로 넘어간 것이었다. 그래서 조금 시간이 걸렸다.

이제 CLASS 5를 하거나, Solved.ac에 새로 나온 마라톤? 같은것도 할 것 같다.
끝 ~