(백준 알고리즘 문제풀이) 9251번 LCS(최장 공통 부분 수열)

문제

문제 링크

 

문제 접근

• LCS: 최장 공통 부분 수열
  ex)ACAYKP, CAPCAK -> ACAK
  output: LCS의 길이
• 예제로 문제를 접근해 보았다.
• x, y 축의 첫 항의 값은 모두 0으로 고정이다. (margin을 주기 위함)
• x, y 축에 cross하여 같은 것이 있으면 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값에 + 1해주는 식의 알고리즘이다.
• 그렇지 않으면, 바로 위의 표 or 바로 왼쪽표 or 바로 왼쪽 위 대각선 표의 값 중 높은 값을 입력하면 된다.
• 잘 이해가 되지 않으니 그림으로 설명하겠다.
• 그림1

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1
A	0	1
Y	0	1
K	0	1
P	0	1

• 그림2

	0	C	A	P	C	A	K
0	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
Y	0	1	2
K	0	1	2
P	0	1	2

• 그림3

	0	C	A	P	C	A	K
0	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
K	0	1	2	2
P	0	1	2	3

• 그림4

	0	C	A	P	C	A	K
0	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	3	3	4
P	0	1	2	3	3	3	4

코드

import sys

str1 = "0" + sys.stdin.readline().strip()
str2 = "0" + sys.stdin.readline().strip()

LCS = list([0] * len(str2) for _ in range(len(str1)))
for i in range(len(str1)):
    for j in range(len(str2)):
        if i == 0 or j == 0:
            LCS[i][j] = 0
        elif str1[i] == str2[j]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])


# for i in LCS:
#     print(i)

print(LCS[len(str1)-1][len(str2)-1])

 

느낀점

 

LCS라는 단어를 처음 들어봤을 때는 익숙하지 않아서 많이 서칭을 한 것 같다. 그리고 문제를 풀면서 이렇게나 많은 고민을 한적도 몇 없었다. 하지만 더욱 복잡한 알고리즘을 공부하기 전에 기본으로 열심히 공부해야하는 디딤돌으로 생각하고 더욱 열심히해야겠다.