반응형
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
💡 LCS
✅ 문제 풀이
- 문자열에서 최장 부분 수열의 크기를 찾는 문제
- DP를 이용하여 풀 수 있다.
- dp 배열의 크기는 두 문자열 각각의 크기에 +1 한 만큼으로 행과 열 크기를 배정해준다.
- 행 열 인덱스 0은 모두 0으로 초기화하여 사용할 것이다.
- 그리고 dp 크기만큼 2중 for문을 순회하는데, 각 칸의 값은 해당 칸의 행과 열 알파벳이 동일하면 왼쪽 대각선 위 값에 +1 한 값이고, 다르면 왼쪽과 위에서 오는 값 중 더 큰 값으로 가지게 된다.
=> 이는 표를 그려보면 규칙을 통해 발견할 수 있다. - 따라서 이를 점화식으로 나타내면 다음과 같다.
dp[i + 1][j + 1] = dp[i][j] + 1 (행 알파벳=열 알파벳)
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) (행 알파벳 =/= 열 알파벳) - 그리고 dp[r][c] 즉, 가장 오른쪽 아래에 있는 값이 최종 답이 된다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string str1, str2;
cin >> str1 >> str2;
int r = str1.length();
int c = str2.length();
vector<vector<int>> dp(r+1, vector<int>(c+1,0));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int m = max(dp[i][j + 1], dp[i + 1][j]);
if (str1[i] == str2[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else {
dp[i + 1][j + 1] = m;
}
}
}
cout << dp[r][c];
return 0;
}반응형
'CO-TE > 백준' 카테고리의 다른 글
| [백준] 1011번 C++ "Fly me to the Alpha Centauri" 풀이 / 수학 (1) | 2024.02.05 |
|---|---|
| [백준] 15686번 C++ "치킨 배달" 풀이 / 완전 탐색, 조합 / 삼성 sw역량테스트 기출문제 (1) | 2024.02.02 |
| [백준] 7569번 C++ "토마토" 풀이 / bfs, 3차원 벡터 (1) | 2024.01.29 |
| [백준] 10026번 C++ "적록색약" 풀이 / dfs, 너비 우선 탐색 (0) | 2024.01.27 |
| [백준] 2447번 C++ "별 찍기 -10" 풀이 / 재귀, 분할정복, 프렉탈 (0) | 2024.01.24 |
