문제 이해 단계
문제를 이해하는데 굉장히 헷갈렸다.
설명이 짧아서 이게 무슨 소리인가 싶어서 한참을 봤다.
두 개의 대문자 문자열이 주어지고,
그 두 문자열 중 공통 문자 중 가장 긴 수열을 구한다는 것인데 이런 것이다.
예제에서는 공통 문자가 'A, C, K, P' 총 4개인데,
ACAYKP 입장에서 공통된 것을 나열해 보면 ACAKP
CAPCAK 입장에서는 CAPCAK이다.
이 중에서 이 형태를 유지하면서 얻을 수 있는
가장 긴 수열은 ACAK라는 뜻이다.
P를 사용하지 못하는 이유는 P를 사용하면 배열 형태가 달라지기 때문이다.
아무튼 이런 식으로 접근하면 된다.
문제 접근 단계
해당 문제는 총 2가지의 풀이법이 존재한다.
1. 논리적 풀이
2. 수학적 풀이
풀이법을 하나하나씩 풀어보겠다.
1. 논리적 풀이
ABCFG
ABECG
두 개의 문자열이 있다고 생각해 보자.
이때, 다른 건 생각하지 않고 마지막 G에서의
최장 공통 수열을 구하는 것을 생각해 보자(즉 G일 때)
ABCFG와 ABECG 모두 끝이 G로 같기 때문에 당연히 이전의 최장 공통 수열 + 1이다.
왜냐하면 둘 다 끝이 G로 끝나기 때문에 그저 이전 결과에
G를 추가시켜주기만 하면 되기 때문이다.
이제 G 이전의 최장 공통 수열을 구하기 위해 ABCF와 ABEC를 가지고 생각해 보자.
이번에는 끝에 있는 문자가 F와 E로 서로 다르기 때문에
앞서 썼던 방법은 사용할 수 없다.
그렇다면 어떤 방법을 사용해야 할까?
그냥 둘 다 비교해 보는 수밖에 없다.
F를 사용했을 때와 E를 사용했을 때 중 더 긴 것을 결과로 하면 된다.
F를 사용했을 때 최장 공통 수열은 AB
C를 사용했을 때 최장 공통 수열은 ABC
그러므로 C를 사용했을 때를 최장공통 수열로 저장해 두면 된다.
이 같은 원리로 ABC와 ABE, AB와 AB...
이런 식으로 반복하면 된다.
정리하자면
끝 문자가 서로 같을 경우 = 이전의 최장 공통 수열 + 1
끝 문자가 서로 다를 경우 = 이전의 최장 공통 수열에 각각의 문자열을 넣었을 때 중 더 긴 것
이제 이를 DP 식으로 정리하면 되는데, 이걸 왜 갑자기 DP로 정리하느냐?
위에서 식을 보면이전의 최장 공통 수열 +1.. 이전의 최장 공통 수열...
이런 표현을 보면 이전의 결과가 다음 결과에 영향을 준다.
다른 식으로 말하면 부분의 결과가 전체의 결과가 된다는 뜻이다.
즉, 이 말이 DP를 뜻하는 말이기 때문에
해당 문제는 DP로 풀 수 있다는 의미이다.
본론으로 돌아가, 해당 문제에는 두 개의 문자열이 존재하고,
각 문자열의 문자를 하나하나씩 비교해야 한다.
끝 문자가 서로 다를 경우, 각각의 문자열을 넣었을 경우의 결과를
다르게 저장해야 하기 때문에 이를 문자에 따라 다르게 저장해야 한다.
그래서 나는 문자에 따라 다르게 저장하기 위해
DP [i][j] 이런 식으로 2차원 배열로 저장해 두기로 했다.
DP [a][b] = c
: 첫 번째 문자열에서 a번째까지 진행하고,
두 번째 문자열에서 b번째까지 진행하였을 때 최장 공통 수열은 c
라고 가정했다.
DP를 이렇게 가정하고 위에 정리를 이중 반복문을 통해
첫 번째 문자열의 문자를 첫 번째부터 하나씩, 두 번째 문자열에 비교하여 DP값을 채워 넣었다.
자세한 것은 코드에서 설명하겠다.
2. 수학적 풀이
두 번째 방식은 이런 식으로 표를 그리고,
실제로 값을 채워 넣고, DP를 작성해 보면서 점화식을 유추해 보는 것이다.
해당 표는 세로 행을 가로 행과 비교하는 것인데, 누적으로 비교하는 것이다.
예를 들어
3행 1열은 A와 C를 비교하고
3행 2열은 AC와 C,
3행 3열은 ACA와 C를 비교한다.
그렇다면 5행 3열은 CAP와 ACA를 비교하는 것이다.
이런 식으로 최장 공통 수열을 직접 계산하여 채워본다.
여기까지 채우다 보면 2가지 규칙이 보인다.
1. 해당 칸의 행과 열의 문자가 같을 경우
그 칸의 값은 왼쪽 대각선의 값 + 1
2. 다를 경우에는 해당 칸의 왼쪽,
위쪽 칸 중 더 큰 값이 해당 칸의 값이 된다.
이 성질을 점화식으로 바꾸면 된다.
문제 구현 단계
#include <iostream>
#include <string>
using namespace std;
int dp[1001][1001];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
string s1, s2;
cin >> s1 >> s2;
for(int i = 1; i <= s1.size(); i++){
for(int j = 1; j<= s2.size(); j++){
if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
cout << dp[s1.size()][s2.size()];
}코드는 굉장히 간결하게 나온다.
입력받은 두 String을 크기대로 이중 반복문을 돌린다.
바깥 반복문은 첫 번째 문자열, 안쪽 반복문은 두 번째 문자열이다.
문자를 하나씩 안쪽 문자열에 대조하는 작업을 하여 DP를 채운다.
시행착오
요즘 DP에 대한 상당한 벽을 느끼는 중이다.
2차원 DP로 넘어온 이후로는 상당히 문제를 푸는 게 어렵다.접근조차 어려운 경우도 많고,
같은 골드 5인 게 믿기지 않을 만큼 어렵다.
해당 문제도 여러 번 고민해 봤지만
이런 식으로의 접근방법은 생각지도 못했다.
2번째 방법으로는 왠지 풀기 싫은데,
그래도 2번째 방법으로도 한번 접근해 보긴 해보긴 해야 할 거 같다.