[백준 / BOJ] C++ 9252

#9252: LCS 2

문제

https://www.acmicpc.net/problem/9252

#9252: LCS 2

LCS(Longest Common Subsequence) 문제는 두 개의 시퀀스가 ​​주어졌을 때 두 시퀀스의 서브 시퀀스인 가장 긴 시퀀스를 찾는 문제입니다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 됩니다.

www.acmicpc.net

설명

9251 LCS의 향상된 버전입니다. LCS 길이를 찾는 방법은 아래 링크에 있습니다.

https://khyunx.57

(백준 / BOJ) C++ 9251 LCS

#9251: LCS 문제 https://www.acmicpc.net/problem/9251 #9251: LCS LCS(Longest Common Subsequence) 문제 문제는 가장 긴 것을 찾는 것입니다.

khyunx.tistory.com

위의 문제에 대한 추가 문제는 LCS 자체를 얻는 것입니다. 길이를 구하는 코드에서 길이가 아닌 문자열로 변경하고 문자열의 길이를 비교하면서 같은 일을 했습니다. 그렇게 했을 때 타임아웃이 주어졌습니다.

그 이유는 두 문자열의 길이가 N이라면 시간복잡도는 O(N^2)가 될 것이라고 생각했는데, 문자열로 완성하면 문자열을 비교하는데 시간이 걸리므로 O(N^3)가 된다. ).

아래는 타임아웃 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b;
  cin >> a >> b;
  int a_length = a.length();
  int b_length = b.length();
  vector<vector<string>> dp(a_length + 1, vector<string>(b_length + 1, ""));
  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) + a(i - 1);
      } else {
        if (dp(i - 1)(j).length() > dp(i)(j - 1).length())
          dp(i)(j) = dp(i - 1)(j);
        else
          dp(i)(j) = dp(i)(j - 1);
      }
  cout << dp(a_length)(b_length).length() << '\n'
       << dp(a_length)(b_length);
  return 0;
}

정답 AC를 얻은 해는 9251번 문제와 같으며 우측 하단부터 역추적하여 정답을 찾는다. 표로 설명합니다.

오른쪽 아래에서 LCS의 길이가 4임을 알 수 있습니다. 여기서 LCS의 길이가 같은지 확인하기 위해 왼쪽과 위쪽을 비교합니다.

1. 같으면 그쪽으로 이동하십시오. (왼쪽과 위쪽이 같은 경우 왼쪽 우선 순위)
2. 둘 다 다르면 해당 위치의 문자가 LCS 문자이며 왼쪽 대각선 위로 이동합니다.

위의 방법을 거친 경로는 다음과 같이 빨간색으로 표시됩니다.

두꺼운 부분에서 이 위치에 있는 문자가 LCS를 형성합니다.

암호

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b;
  cin >> a >> b;
  int a_size = a.size();
  int b_size = b.size();
  vector<vector<int>> dp(a_size + 1, vector<int>(b_size + 1, 0));
  // LCS 길이 구하기
  for (int i = 1; i <= a_size; i++)
    for (int j = 1; j <= b_size; j++)
      if (a(i - 1) == b(j - 1))
        dp(i)(j) = dp(i - 1)(j - 1) + 1;
      else
        dp(i)(j) = max(dp(i - 1)(j), dp(i)(j - 1));
  int len = dp(a_size)(b_size);
  cout << len << '\n';
  // LCS 구하기
  vector<char> LCS(len, ' ');
  int x = a_size, y = b_size; // dp 배열에서 탐색을 시작할 좌표
  while (len > 0) { // 역추적하며 모든 문자를 찾을 때까지
    if (dp(x - 1)(y) == len) { // 왼쪽이 같은 길이일 때 x좌표 이동
      x--;
    } else if (dp(x)(y - 1) == len) { // 왼쪽은 같은 길이가 아니면서 위쪽이 같을 때 y좌표 이동
      y--;
    } else { // 둘 다 아닐 때 그 위치의 문자를 배열에 추가, 대각선으로 이동
      LCS(len - 1) = a(x - 1);
      x--;
      y--;
      len--;
    }
  }
  for (char i : LCS)
    cout << i;
  return 0;
}