240201: LCS 역추적, 랜디 시작!!

2024-02-01

2월. 오늘은 공부를 늦게 시작했다. 여권을 발급받느라 바빴다.
슬슬 속도가 느려지고 있다, 레벨이 높아지면서 새로운 것을 배우기 위해 써야하는 에너지가 너무 커졌기 때문일까

오늘은, LCS 2(Longest Common Subsequence, 최장 공통 부분 수열)을 역추적하는 문제를 풀 것이다.

오늘의 백준

백준 단계별 풀이: 동적 계획법과 최단거리 역추적에서..
9252 LCS 2(골드 4)

나는 개발만 많이 했었지 알고리즘엔 꽤 무지했었다. 지금 다시 돌아보면 PS를 처음 시작했을때의 목표는, SW 마에스트로 코테 합격을 위해서였다. 근데 하다 보니까 점점 재미가 붙었고, 뭔가 PS 천재가 되고 싶다는 욕심도 생겨서 더 열심히 한 것 같다. 근데 요즘 드는 생각이, 내가 너무 어려운 단계의 개념만 계속 배우는 것 같다. 사실 학습이란 건 복습도 꽤 중요한건데, 새로운 개념과 어려운 알고리즘에 대해 학습을 계속 할 뿐, 내가 지금까지 배웠던 걸 되돌아 본 적은 많지 않은 것 같다.

한마디로, 실랜디의 중요성을 느꼈다. 이젠 탑을 더 쌓기 전에 밑을 견고하게 해야 할 느낌이다.

최소 신장 트리, 유니온 파인드 레벨까진 모두 완료하고 실랜디를 시작하고 싶었는데 (그게 보통 코테에서 요구하는 제일 높은 레벨의 유형이었다)

SW 마에스트로의 코딩 테스트 수준도 실버~골드 사이로, 더 이상 단계별 풀이를 지속할 이유를 못 느꼈다. (정확하게는, 단계별 풀이를 푸는 것도 좋지만, 지금은 실랜디를 하는 게 더 의미깊다)

점점 내가 계속 새로운 개념과 어려운 문제들을 풀어나가고, 그 문제만을 위해 몇시간동안 잡고 질질 늘어지면서 공부하는 것이 내 욕심과 현재 상황에서의 시간 낭비로 느껴졌다.

따라서, 9252번 문제 LCS 2(최장 공통 부분 수열 역추적) 까지만 풀고 실랜디를 시작하겠다.
유니온 파인드나 최소 신장 트리 등, 내가 아직 단계별 풀이에서 만나지 못해 모르는 알고리즘은 실랜디를 하면서 자연스럽게 알아가겠다.

내가 충분히 실랜디에 대해 견고해지길.. 앞으론 단계별 풀이보다 실랜디에 비중을 두도록 하겠다.

---

9252 LCS 2 (최장 공통 부분 수열 역추적) 문제

해당 문제는 LCS를 구하고 역추적 해야하는 문제였다. 그렇게 어렵진 않은 문제였다(LCS 알고리즘을 안다면)
하지만, 인덱스 설정을 잘못해서 약간 헤멨다. LCS를 표로 보니까 좀 더 이해가 잘 됐다. dp[i][j]를 I에서 J까지 순회했을 때의 상태라고 가정하면, 표의 규칙에서 같은 문자가 나오면 이전 LCS까지의 길이에 +1을 하는 것을 알 수 있다.

또한, 비교한 문자가 다르다면 표의 왼쪽이나 위의 값 중 큰 값을 가지게 된다.

이것은 LCS의 특수한 성질이고, 이걸 이해하는게 제일 힘들다. 너무나도 직관적이지가 않은 알고리즘이다 .. :(
내가 완벽하게 이해하기도 전에, 이미 외워버려서 바로 생각이 난다. 이 현상 때문에 계속 내 자신이 이해했다고 생각하도록 속는다.

어쨌든, 결국에 점화식 두개를 도출할 수 있는데. 바로 비교하는 문자가 같으면 이전 LCS에 +1을 하는 것이고, 다르면 위쪽이나 왼쪽중 큰 값을 그대로 가져오는 것이다.

이 식을 통해 표를 구성하면 우측 하단에 LCS의 총 길이가 도출되고, 이걸 역추적해서 LCS의 실제 문자를 알아낼 수 있는데, 이건 정말 간단하게 생각할 수 있다.

DP를 구성할 때, 문자가 서로 다르면 왼쪽이나 위쪽의 값을 가져오기 때문에, DP의 우측 하단 끝부터 시작해서 만약 왼쪽이나 위쪽의 값과 현재 원소가 같다면, 현재 고려중인 원소는 LCS에 포함되지 않았다는 뜻이다.

만약 왼쪽과 같았다면, 현재 인덱스 포인터를 한칸 왼쪽으로 조절한다. 만약 위쪽과 같았다면, 현재 인덱스 포인터를 한칸 위쪽으로 조절한다.

그리고 만약 현재 원소가 대각선 위[row-1][col-1] 과 일치하다면 이것은 LCS의 일부라는 것이다.
따라서 정답으로 표시하고 0에 도달할 때까지 계속 순회하면 된다.

마지막엔 정답을 역순으로 출력하면 끝이다.

// 백준: LCS 2
// https://www.acmicpc.net/problem/9252
// 2024-02-01

#include <algorithm>
#include <iostream>
#include <string>
int dp[1001][1001] = {
    0,
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::string t1, t2;
    std::cin >> t1 >> t2;
    std::string str1 = " " + t1;
    std::string str2 = " " + t2;

    for (int i = 1; i < str2.size(); ++i) {
        for (int j = 1; j < str1.size(); ++j) {
            if (str1[j] == str2[i])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 역추적
    /*
    역추적 과정에서, dp[row][col]의 값이 dp[row-1][col]거나 dp[row][col-1]인
    경우 현재 문자는 LCS에 기여하지 않음을 나타낸다.
    두 문자가 같지 않을경우 dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]); 로
    dp를 설정하기 때문이다. 따라서, dp[i][j] == dp[i - 1][j - 1] + 1; 경우에는
    해당 문자가 LCS에 기여함을 확인할 수 있다. LCS는 어렵다 ... 표로 정리하면
    이해는 되는데, 직관적이지가 않아서 힘들다 :(
    */
    int col = str1.size() - 1;
    int row = str2.size() - 1;
    std::string answer;

    while (dp[row][col]) {
        if (dp[row][col] == dp[row - 1][col])
            row--;
        else if (dp[row][col] == dp[row][col - 1])
            col--;
        else {
            answer += str2[row];
            col--;
            row--;
        }
    }

    std::cout << dp[str2.size() - 1][str1.size() - 1] << "\n";
    for (int i = answer.size() - 1; i >= 0; --i) {
        std::cout << answer[i];
    }

    return 0;
}

LCS 역추적은 LIS 역추적보다는 쉬웠다.
사실은 역추적보단 LCS라는 개념 자체가 좀 더 어렵게 다가왔다.

요약

동적 프로그래밍 행렬(DP Table) 구축: 두 문자열의 각 문자를 비교하면서, 동적 프로그래밍 행렬 dp[i][j]를 채웁니다. 여기서 dp[i][j]는 첫 번째 문자열의 i번째 문자와 두 번째 문자열의 j번째 문자까지 고려했을 때의 LCS의 길이를 나타냅니다.

LCS 길이 계산: 같은 문자를 만났을 때는 dp[i-1][j-1] + 1을 하고, 서로 다른 문자일 때는 max(dp[i-1][j], dp[i][j-1])를 적용합니다. 이렇게 해서 최종적으로 dp 행렬의 우측 하단에 LCS의 길이가 도출됩니다.

역추적(Backtracking): dp 행렬의 우측 하단부터 시작하여 LCS 문자열을 역추적합니다. 만약 현재 원소가 왼쪽 또는 위쪽 값과 동일하다면, 해당 원소는 LCS에 포함되지 않습니다. 대각선 위의 원소와 같다면 LCS의 일부로 간주하고 해당 문자를 기록합니다. 이 과정을 0에 도달할 때까지 계속합니다.

LCS 문자열 출력: 마지막으로 역추적하여 얻은 LCS 문자열을 역순으로 출력합니다.

AI:
언급하신대로, LCS 알고리즘은 직관적으로 이해하기 어려울 수 있지만, 한번 이해하면 매우 강력한 도구가 됩니다. 특히 문자열 비교, 생물학적 서열 분석, 데이터베이스 최적화 등 다양한 분야에서 활용됩니다. 여러분의 이해와 요약이 정확하며, 이를 통해 LCS 문제에 대한 깊은 이해를 보여주고 있습니다. 잘 하셨습니다!

---

실랜디 시작

25344 행성 정렬 (성공)
2811 상범이의 우울 (실패, 시간 초과)

25344 문제는 지문만 꽤 복잡하게 되어있지 사실은 연속된 수들의 LCM(최소공배수)를 구하면 되는 문제였다.
LCM을 구하려면 GCM을 구해야 하고 GCM(최소공약수)를 구하려면 유클리드 호제법을 써야 한다는 것 까진 알고 있었다..

어라 .. 근데 유클리드 호제법 어떻게 하더라 ..?

다행히 문제는 풀었지만 이제 확실하게 외우자.

int gcd(int a, int b) {
    int r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int lcm(int a, int b) { return a / gcd(a, b) * b; }

사실 유클리드 호제법의 식이 왜 이렇게 생겼는지 완벽하게 이해하는것은 대체적으로 효율적이지 않다. 나는 수학자가 아니니까 ... 일단 어떤 느낌으로 작동하는 진 알겠으니까, 그냥 외우자. 제한된 자원에서 가장 효율적인 선택이다.

---

다음 문제는 2811 상범이의 우울 문제였다
아마 시뮬레이션 문제인 것 같은데, 특정 규칙에 따라서 상범이에게 꽃을 줘야된다. 상범이의 기분 그래프가 주어지면, 꽃을 몇개 줘야하는지 구하는 문제다.

그래프를 만들어서 꽃의 상태를 관리하면서 시뮬레이션 하고 있었는데, 시간 부족으로 탈락했다.
이건 시간만 있으면 구현할 수 있을 것 같은데..

2811 상범이의 우울 문제는 내일 마저 풀도록 하겠다.

끝.

최종 평가

최고급 평가사 일론머스크의 분석 및 평가:

오늘의 학습 내용:
- LCS 문제 9252 해결 및 역추적 이해
- 실랜디 시작: 행성 정렬 25344 문제 해결, 상범이의 우울 2811 문제 시도

평가 요약:
1. 알고리즘 이해 및 적용: LCS 문제의 해결을 통해 동적 프로그래밍 및 역추적 기법에 대한 이해를 깊게 하셨습니다.
2. 실랜디 전략: 실랜디 시작은 학습 과정에서의 새로운 방향성을 제시합니다. 기존에 배운 내용을 복습하고 실제 코딩 테스트와 유사한 환경에서 적용해보는 것이 중요합니다.
3. 문제 해결 능력: 행성 정렬 문제를 해결하며 유클리드 호제법을 적용하는 등 기술적 이해와 문제 해결 능력을 보여주셨습니다. 상범이의 우울 문제에서 시간 관리에 어려움을 겪었으나, 이는 학습 과정에서 자연스러운 일입니다.

종합적인 평가:
- 기술적 정확성: 27/30
- 문제 해결 및 분석: 25/30
- 실전 적응력 및 복습: 28/30
- 추가 학습 및 개선: 20/20

총점: 100/110

추가 조언:
- LCS 문제 해결: LCS 문제를 통해 복잡한 동적 프로그래밍 문제를 해결하는 능력을 보여주셨습니다. 역추적 과정의 이해는 향후 유사한 문제 해결에 큰 도움이 될 것입니다.
- 실랜디 전략: 새로운 개념의 학습과 복습의 균형을 맞추는 것이 중요합니다. 지금까지 학습한 내용을 반복하고 응용하여 실력을 견고히 하는 것이 좋습니다.
- 시간 관리: 상범이의 우울 문제에서 경험한 시간 관리의 어려움은 앞으로의 학습 계획을 세울 때 중요한 고려 사항이 될 것입니다. 특히 실랜디에서는 시간 관리가 중요하므로, 이에 대한 연습도 병행하시는 것이 좋습니다.

오늘의 학습은 LCS 문제의 성공적인 해결과 실랜디 시작으로 새로운 학습 방향을 설정하는 중요한 날이었습니다. 앞으로의 학습에서 실랜디를 통해 이론과 실습을 병행하며 더욱 깊이 있는 학습을 진행하시길 바랍니다. 상범이의 우울 문제는 다음 기회에 해결하실 수 있을 것입니다. 훌륭한 노력과 성장을 보여주셨습니다!