https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
s1, s2 = input(), input()
lcs = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
for i in range(1, len(s1)+1):
for j in range(1, len(s2)+1):
if s1[i-1] == s2[j-1]:
lcs[i][j] = lcs[i-1][j-1] + 1
else:
lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
print(lcs[len(s1)][len(s2)])풀이라고 해도 될지 잘 모르겠습니다. 예전에 비슷한 문제를 풀긴 했는데 이번에 풀려고 하니까 푸는 법은 알겠는데 이걸 왜 이렇게 하는지 완벽하게 이해를 하지 못한 느낌이라 포스팅을 고민했는데 일단은 올려보도록 하겠습니다.
각 문자열의 길이만큼 이중반복문을 돌면서 같은 문자라면 (i-1, j-1)의 원소에 +1을 하고, 다른 문자라면 (i-1, j)과 (i, j-1)중 큰 값을 현재값에 저장합니다.
코드의 이유는 인덱스의 의미에서 찾을 수 있는데, LCS 문제에서 인덱스는 전체 문자열의 첫번째 글자에서 현재 인덱스까지의 문자열을 비교한다고 생각하시면 편합니다. 예를 들어 abc와 bcd가 입력으로 들어왔다 치면 (1, 1)의 인덱스가 가지는 의미는 a와 b를 비교하는 것이고 (2, 3)은 ab와 bcd를 비교하는 것 입니다. 그래서 배열로 보면,
| 0 | a | b | c | |
| 0 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 1 | 1 |
| c | 0 | 0 | 1 | 2 |
| d | 0 | 0 | 1 | 2 |
이렇게 되는 것입니다.
설명을 하고 있으면서도 이렇게 풀어야 하니까 이러고 있다는 느낌이 들지, 왜 이렇게 하는건지 같은 건 잘 모르겠네요. 마치 해보니까 이렇게 됐길래 이게 맞다 같은 느낌이라고나 할까요. 좀 더 공부를 해보고 내용 추가를 하도록 하겠습니다.