https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 행렬을 이용하여 기준이 되는 문자열과 다른 문자열을 한 글자씩 증가해가며 LCS를 구하는 문제였습니다. 행렬을 그린 후 하나씩 작성해 나가다 보면 규칙을 찾을 수 있습니다.
아래의 표에서 빨간색으로 칠한 3행 4열을 보시면 ACAYK에 CAPC의 LCS가 2라는 것을 알 수 있습니다.
이는 ACAYK CAPC 이기 때문입니다. 같은 원리로 5행4열을 보시면 ACAYK에 CAPCAK의 LCS가 4인 것을 알 수 있는데 이는 ACAYK CAPCAK이기 때문입니다.
다시 위의 표를 보시면 규칙을 찾을 수 있는데 바로 위의 행이 그대로 아래의 행으로 내려온 후 비교해나가다가 같은 글자를 만나면 좌측 + 1이 된다는 것입니다. 다른 글자의 경우 max(좌, 상)이 들어가는 것을 확인할 수 있습니다.
다른 글자의 경우 max(좌, 상)이 이해가 안 될 수 있어서 다른 예시를 첨부하면 다음과 같습니다.
2행4열을 보면 다음과 같이 P와 T가 다르기 때문에 max(1, 2)인 2가 들어간 것을 확인할 수 있습니다. 따라서 이를 코드로 옮기면 됩니다.
소스코드 - python
(코드 작성의 편의를 위해 행과 열을 하니씩 추가 하였습니다.)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
word1 = input()
word2 = input()
n = len(word1)
m = len(word2)
data = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
data[i][j] = data[i-1][j]
for j in range(1, m+1):
if word1[i-1] == word2[j-1]:
data[i][j] = data[i-1][j-1] + 1
else:
data[i][j] = max(data[i][j-1], data[i-1][j])
print(data[n][m])
|
cs |
소스코드 - c++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <bits/stdc++.h>
#define MAX 1001
using namespace std;
int main(void) {
char word1[MAX];
char word2[MAX];
scanf("%s", word1);
scanf("%s", word2);
int n = strlen(word1);
int m = strlen(word2);
int data[MAX][MAX] = {0};
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < m+1; j++) {
data[i][j] = data[i-1][j];
}
for (int j = 1; j < m+1; j++) {
if (word1[i-1] == word2[j-1])
data[i][j] = data[i-1][j-1] + 1;
else
data[i][j] = max(data[i][j-1], data[i-1][j]);
}
}
printf("%d\n", data[n][m]);
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2193번: 이친수(Python) (0) | 2022.01.31 |
|---|---|
| 백준 알고리즘 11057번: 오르막 수(Python) (0) | 2022.01.29 |
| 백준 알고리즘 1904번: 01타일(Python) (0) | 2022.01.28 |
| 백준 알고리즘 2156번: 포도주 시식(Python) (0) | 2022.01.25 |
| 백준 알고리즘 1912번: 연속합(Python) (0) | 2022.01.25 |