๐ฃ ๋ฌธ์ ์ดํด
๋ง์ด ์๋ ค์ง Longest Common Sequence(LCS) ๋ฌธ์ ์ด๋ค.
๋ ๋ฌธ์์ด์ด ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ๋, ์ด ๋ ๋ฌธ์์ด์ ๊ณตํต๋๋ ๋ถ๋ถ ์ค ๊ฐ์ฅ ๊ธด ๋ฌธ์์ด์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
์ด ์ธ๊ตญ ์ ํ๋ฒ์ ํ์ด ๋ฅผ ์ฐธ๊ณ ํ๋ฉฐ 3๊ฐ์ง ํ์ด๋ก ์ ๊ทผํด๋ณด์๋ค.
1. ์ฌ๊ท (Recursion)
2. ๋ฉ๋ชจ์ด์ ์ด์ (Memoization)
3. ๋์ ๊ณํ๋ฒ (Dynamic Programming)
๐ญ ํ์ด ๊ณผ์
1. ์ฌ๊ท ๋ฐฉ์์ ํ์ด
์์ฑ ์ธ์ด: C++
#include <cstdio> // c ํ์ค ์
์ถ๋ ฅ
#include <algorithm> // std::max
char str1[1001], str2[1001];
int LCS_recurs(int index1, int index2){
if (str1[index1] == '\0' || str2[index2] == '\0') {
return 0;
}else if (str1[index1] == str2[index2]) {
return 1 + LCS(index1 + 1, index2 + 1);
}else {
return std::max(LCS(index1 + 1, index2), LCS(index1, index2 + 1));
}
}
int main(){
scanf(" %s %s", str1, str2); // ์
์ถ๋ ฅ๋ฒํผ์ '\n'์ ๋จ๊ธฐ์ง ์๊ธฐ ์ํด %s ์์ ๊ณต๋ฐฑ์ ๋
printf("%d\n", LCS_recurs(0, 0));
return 0;
}
LCS_recurs ํจ์์์ ๋ณด์ด๋ ๊ฒ ์ฒ๋ผ, ์ฒซ ๋น๊ต์ ์์์ ๋ ๋ฌธ์์ด์ 0๋ฒ ์ธ๋ฑ์ค์ด๋ค.
๋ง์ฝ ๋ ๋ฌธ์๊ฐ ๊ฐ๋ค๋ฉด, ๋ฆฌํด ๊ฐ์ 1์ ๋ํ๊ณ ๋ ๋ฌธ์์ด์ ๋ค์ ์ธ๋ฑ์ค๋ฅผ ๋น๊ตํ๋ค.
๋ ๋ฌธ์๊ฐ ๋ค๋ฅด๋ค๋ฉด, ํ ๋ฌธ์์ด์ ์ธ๋ฑ์ค๋ฅผ ์ฆ๊ฐํ ๊ฒ๊ณผ ๋ค๋ฅธ ๋ฌธ์์ด์ ์ธ๋ฑ์ค๋ฅผ ์ฆ๊ฐํ ๊ฒ ์ค ๋ฆฌํด ๊ฐ์ด ๋ ํฐ ๊ฒ์ ๋ฐํํ๋ค.
๋ ๋ฌธ์ ์ค ํ๋๋ผ๋ '\0' ์ด๋ผ๋ฉด (๋ฌธ์์ด์ ๋) 0 ์ ๋ฆฌํดํ๊ฒ ๋๋ค.
๊ทธ๋ฌ๋, ์ด ํ์ด๋ ์ง์์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ฏ๋ก ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ ๊ธธ์ด์ง๋ฉด ๊ธฐํ ๊ธ์์ ์ธ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
2. ๋ฉ๋ชจ์ด์ ์ด์
์์ฑ ์ธ์ด: C++
#include <cstdio> // c ํ์ค ์
์ถ๋ ฅ
#include <algorithm> // std::max
int memo[1001][1001] = {0, };
char str1[1001], str2[1001];
int LCS(int index1, int index2){
if (memo[index1][index2] != 0) {
return memo[index1][index2];
}else {
if (str1[index1] == '\0' || str2[index2] == '\0') {
return 0;
}else if (str1[index1] == str2[index2]) {
return memo[index1][index2] = 1 + LCS(index1 + 1, index2 + 1);
}else {
return memo[index1][index2] = std::max(LCS(index1 + 1, index2), LCS(index1, index2 + 1));
}
}
}
int main(){
scanf(" %s %s", str1, str2); // ์
์ถ๋ ฅ๋ฒํผ์ '\n'์ ๋จ๊ธฐ์ง ์๊ธฐ ์ํด %s ์์ ๊ณต๋ฐฑ์ ๋
printf("%d\n", LCS(0, 0));
return 0;
}
์ด๋ฏธ ์ํํ ์ฐ์ฐ์ memo ๋ฐฐ์ด์ ์ ์ฅ๋์ด์์ด์ ์ค๋ณต๋๋ ์ฐ์ฐ์ด ํธ์ถ๋๋ฉด ๋ฐฐ์ด์ ์ ์ฅ๋ ๊ฐ์ ๋ฆฌํดํ๋ค.
๊ฒฐ๊ตญ ์ด ๋ฐฉ์์ memo ๋ฐฐ์ด์ ํฌ๊ธฐ๋งํผ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค๊ณ ๋ณผ ์ ์๋ค. => O(M*N)
3. ๋์ ๊ณํ๋ฒ
์์ฑ ์ธ์ด: C++
#include <cstdio> // c ํ์ค ์
์ถ๋ ฅ
#include <algorithm> // std::max
int dp[1001][1001] = {0, };
char str1[1001], str2[1001];
int LCS_dp(int row, int col){
for (int i = 1; i <= row; ++i) {
for (int j = 1; j <= col; ++j) {
if (str1[i-1] != str2[j-1]) {
dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
}else {
dp[i][j] = 1 + dp[i-1][j-1];
}
}
}
return dp[row][col];
}
int main(){
int result;
scanf(" %s %s", str1, str2);
result = LCS_dp((int)strlen(str1), (int)strlen(str2));
printf("%d\n", result);
return 0;
}
์ ๋ ฅ๋ฐ์ดํฐ์ธ "ACAYKP" ์ "CAPCAK" ์ ์๋ก ํ์ด๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
C | A | P | C | A | K | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | |
A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
C | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
A | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
Y | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
K | 0 | 1 | 2 | 2 | 2 | 3 | 4 |
P | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
ACAYKP ์ 'A' ์ CAPCAK ๋ฅผ ๋จผ์ ๋น๊ตํ๋ค.
๋ค๋ฅธ ๋ฌธ์๋ผ๋ฉด dp[i-1][j] ์ dp[i][j-1] ์ค ๋ ํฐ ๊ฐ์ผ๋ก ์ฑ์ฐ๊ณ , ๊ฐ์ ๋ฌธ์๋ผ๋ฉด dp[i-1][j-1] ์ ํ๋ ๋ ์ฆ๊ฐํ ๊ฐ์ผ๋ก ์ฑ์ด๋ค.
๋ค์ ACAYKP ์ 'C' ์ CAPCAK ๋ฅผ ๋น๊ตํ๋ ์์๋ก ์งํ๋๋ค.
๋ฐฐ์ด ๊ฐ์ฅ ์ฐ์ธกํ๋จ ํญ ๊ฐ์ด ์ต๋ ๊ณตํต ๋ถ๋ถ ์์ด์ ๊ธธ์ด๊ฐ ๋๋ค.
๋ํ ๊ฐ์ ์ถ์ ํ๋ฉด ๊ทธ ๊ณตํต ์์ด์ด "ACAK" ๋ผ๋ ๊ฒ๋ ์ฐพ์ ์ ์๋ค.
๋ฐฑ์ค ์ฑ์ ์์คํ ์์ ๋ฉ๋ชจ์ด์ ์ด์ ์ 288ms, ๋์ ๊ณํ๋ฒ์ 4ms ์ด๋ผ๋ ์คํ์๊ฐ์ด ๋์๋ค.
๐ ๋ฐฐ์ด ์
์ ์๋ ค์ง LCS (Longest Common Sequence) ๋ฌธ์ ํ์ด๋ฅผ ์ธ ๊ฐ์ง ํ์ด๋ก ์ ๊ทผํ๋ฉด์
๊ฐ ๊ธฐ๋ฒ์ ์ข ๋ ์ ์ดํดํ๊ฒ ๋์๊ณ ,
์คํ์๊ฐ์ผ๋ก ์์นํ๋ ๊ฒฐ๊ณผ๋ฅผ ํตํด ๋น๊ตํ๋ฉด์ ํจ์จ์ฑ์ ๋ ๋ช ํํ ์ ์ ์์ด ์ ์ตํ ํ์ด์๋ค.