LCS๋ Longest Common Subsequence์ ์ฝ์๋ก, ๋ ๋ฌธ์์ด์์ ์ต๋๋ก ๊ณตํต๋๋ ๋ถ๋ถ ์ค ์ ์ผ ๊ธด ๊ฒ์ ์ฐพ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ํ๋ฒํ ์ธ ๋ํ DP ์ ํ์ด์ง๋ง, ๊ตฌํ ๋์ด๋๊ฐ ์ด์ง ๊น๋ค๋กญ๊ธฐ ๋๋ฌธ์, ์ ๋ฆฌํด๋ณธ๋ค.
์๋ ์ฝ๋๋ ํํ ์๊ธฐํ๋ LCS
๋ ์๋๊ณ , Longest Common Substring์ ๊ตฌํ๋ ์ฝ๋์ธ๋ฐ, ์ต์ข
์ ์ผ๋ก ๊ตฌํ๋ ค๊ณ ํ๋ Longest Common Subsequence๋ณด๋ค ๊ตฌํ์ด ๊ฐ๋จํ๊ธฐ ๋๋ฌธ์ ์ง๊ณ ๋์ด๊ฐ๋ค.
for(int a = 1; a <= lena; ++a) {for(int b = 1; b <= lenb; ++b) {if (A[a] == B[b]) DP[a][b] = DP[a-1][b-1] + 1;else DP[i][j] = 0;}}
์ฌ์ค ์ด ๊ฒฝ์ฐ์๋ ๊ตณ์ด 2์ฐจ์ DP
๋ฐฐ์ด์ ์ธ ํ์๋ ์๋ค. 1์ฐจ์์ผ๋ก๋ ์ถฉ๋ถํ๊ธฐ ๋๋ฌธ์.. ๋ค๋ง, ๊ตณ์ด 2์ฐจ์์ผ๋ก ๋ง๋ ์ด์ ๋ ๊ด์ฐฐ์ ์ํด์์ด๋ค. ์ด DP ํ
์ด๋ธ์ ๊ฒฐ๊ณผ๋ฅผ ๋ณด๊ฒ ๋๋ฉด, ์ค๋ณต๋๋ ๋ฌธ์์ด์ ๋ง๋๊ฒ ๋๋ฉด ๋๊ฐ์ ์ฐํ๋จ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋ ๊ฒ์ ์ ์ ์๋ค. ๋ํ, ์ค๊ฐ์ ์๋ก ๋ค๋ฅธ ๋ฌธ์์ด์ด ๋์ค์๋ง์ ์นผ๊ฐ์ด DP ํ
์ด๋ธ์ 0์ผ๋ก ๋ง๋ค์ด ์ฃผ๋ ๊ฒ์ด ํฌ์ธํธ์ด๋ค.
์ฌ๊ธฐ์ ์ฌ๊ณ ๋ฅผ ํ์ฅํด๋ณด์. 0์ผ๋ก ๋ง๋๋ ์ด์ ๋ ์ฐ์
๋๋ค๋ ์กฐ๊ฑด์ด ์๊ธฐ ๋๋ฌธ์ด๋ค. ๊ทธ๋ ๋ค๋ฉด ์ฐ์
๋๋ค๋ ์กฐ๊ฑด์ด ์์ ๋๋ ์ด๋ป๊ฒ ๋ ๊ฒ์ธ๊ฐ? ์ด ๊ฒฝ์ฐ ํ์ฌ๊น์ง์ ์ต๋ ๊ณตํต ๋ถ๋ถ ๊ธธ์ด๊ฐ ์ ์ง๊ฐ ๋์ด์ผ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ์ ์ง๋ x์ถ์ผ๋ก ํด์ผํ ์๋ ์๊ณ , y์ถ์ผ๋ก ํด์ผํ ์๋ ์๊ธฐ ๋๋ฌธ์ x, y์ถ์ ๋ํ max
๊ฐ์ ๊ตฌํด์ฃผ๋ฉด ๋๊ฒ ๋ค. ๊ทธ๋์ ์ DP
์์ด ์์ฃผ ์ฝ๊ฐ ๋ฐ๋๋ค. ์ด ๋ถ๋ถ๋ง ์์ ์ ํ๊ฒ ๋๋ฉด, ์ฝ๋๊ฐ Longest Common Subsequence๋ฅผ ๊ตฌํ๋ ์ฝ๋๋ก ๋ณํ๊ฒ ๋๋ค.
for(int a = 1; a <= lena; ++a) {for(int b = 1; b <= lenb; ++b) {if (A[a] == B[b]) DP[a][b] = DP[a-1][b-1] + 1;else DP[a][b] = max(DP[a-1][b], DP[a][b-1]);}}
์ ๋์ํ ๊น? ์ด ์๋ฌธ์ ํด์ํ๊ธฐ ์์์, ๋ก๋ ๊ฐ์ฅ ๊ธด LCS์ ๊ธธ์ด๋ง์ ์ ์ ์์ ๋ฟ์ธ๋ฐ, ๋ง์ฝ ์ด๋ฌํ LCS ์ค 1๊ฐ๋ฅผ ์ถ๋ ฅํ๋ผ๋ ๋ฌธ์ ๋ฅผ ๋ง๋๋ฉด ์ด๋ป๊ฒ ํ๊น? ์ ์ฝ๋๊ฐ ์ ๋์ํ๋์ง ์์๋ณด๊ธฐ ์ํด ์ ์ฒด์ ์ธ ๊ตฌ์กฐ ์ดํด์ ๋ฌธ์ ํด๊ฒฐ์ ์ํด ์๋์ ๊ฐ์ DP Table ๊ฒฐ๊ณผ๋ฅผ ์์๋ก ๋ณด์. ๊ฐ๋ก์ถ๊ณผ ์ธ๋ก์ถ์ ๊ฐ๊ฐ abc
์ axbycz
์ ๋ฌธ์์ด์ ํ ๋นํ๊ณ , ์ด๋ค์ LCS๋ ์์ ๋ฐ๋ก ์ ์ ์์ ๊ฒ์ด๋ค.
- | - | a | b | c |
---|---|---|---|---|
- | 0 | 0 | 0 | 0 |
a | 0 | 1 | 1 | 1 |
x | 0 | 1 | 1 | 1 |
b | 0 | 1 | 2 | 2 |
y | 0 | 1 | 2 | 2 |
c | 0 | 1 | 2 | 3 |
z | 0 | 1 | 2 | 3 |
LCS๋ฅผ ํ๋ ๊ตฌํ๊ธฐ ์ํด ์ฐ๋ฆฌ๊ฐ ์ฃผ๋ชฉํด์ผํ ๋ถ๋ถ์ ๋๊ฐ์
์ด๋ค. ์๋์ ๊ฐ์ ํ๋ก์ธ์ค๋ก ๋ฌธ์์ด์ ์ฐพ๋๋ค.
์ข์๋จ
๋ฐฉํฅ, ์ฆ ์ขํ์ ์๋ ์ซ์๊ฐ ์ขํ์ ์ซ์๋ณด๋ค ์์ ์๊ฐ ๋๋ค. ๊ทธ ์์น์์์ ๋ฌธ์์ด์ ๊ธฐ๋กํ๊ณ , ๋๊ฐ์ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ๋ค.LCS
๊ฐ ๋๋ค.2๋ฒ์ด ์กฐ๊ธ ์ดํด๊ฐ ์๋ ์ ์๋๋ฐ, ๋งจ ์ฒ์ ์ฝ๋๋ฅผ ๋ค์ ์ฌ๋ ค๋ณด๋ฉด, ๋ฌธ์์ด์ด ๊ฐ์ ๋ ๋ฐฉํฅ์ผ๋ก 1๋งํผ ๋ํ๋ฉด์ ์ ์งํ๋ค. ์ด๋ฅผ ์ญ์ผ๋ก ํ ๊ฒ์ด๋ผ๊ณ ๋ณด๋ฉด ๋๋ค.
๋ ๋ฌธ์์ด์ ๋ฐ์ ๊ฐ์ฅ ๊ธด LCS๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
char A[3010];char B[3010];char C[3010];int DP[3010][3010];void solve() {scanf("%s %s", &A[1], &B[1]);int lena = strlen(&A[1]);int lenb = strlen(&B[1]);for(int b = 1; b <= lenb; ++b) {for(int a = 1; a <= lena; ++a) {if (A[a] == B[b]) {DP[b][a] = DP[b - 1][a - 1] + 1;} else {DP[b][a] = max(DP[b - 1][a], DP[b][a - 1]);}}}// LCS ๊ธธ์ด = DP[lenb][lena]int ca = lena, cb = lenb;int cp = 0;while(DP[cb][ca] != 0) {if (DP[cb - 1][ca] == DP[cb][ca]) {--cb;} else if (DP[cb][ca - 1] == DP[cb][ca]) {--ca;} else if (DP[cb - 1][ca - 1] + 1 == DP[cb][ca]) {C[cp++] = B[cb];cb--; ca--;}}int clen = cp;for(int i = cp - 1; i >= 0; --i) { // ์ถ๋ ฅ์ ์ญ์์ผ๋กprintf("%c", C[i]);}printf("\n");}