백준 LCS 파이썬

문제링크

처음으로 맞이해본 LCS문제 어떻게 접근해야할지 감도 잘 잡히지않았다 그래서 답을보고 공부하였다

블로그출처

답을봤는데도 개념을 이해하는데 시간이 조금 걸렸다

알파벳으로 이루어진 X와 Y라는 수열이 있다고 하자 두 수열의 공통 부분 수열의 길이는 N이다

 

여기서 두수에 같은 알파벳이 입력으로 들어온다면 어떨까

X+A와 Y+A의 공통 부분 수열의 길이는 N+1이다

 

그렇다면 두수에 다른 알파벳이 입력으로 들어온다면?

아까와 똑같이 알파벳으로 이루어진 X와 Y라는 수열이 있고 두 수열의 공통 부분 수열의 길이는 N이다

두 수열에 각각 다른 알파벳이 들어온다 A와 B

X+A와 Y+B간의 공통 부분 수열을 구하는데에있어 끝자리가 다르다는것은

공통 부분 수열의 구성요소로써 A만 사용하거나 B만 사용하거나 혹은 둘다 사용하지않는다는 뜻과 같다

절대 A와 B를 함께 사용할수는 없다

 

따라서 X+A 와 Y+B의 공통 부분 수열의 길이는

X+A와 Y의 공통 부분 수열의 길이와 

X와 Y+B의 공통 부분 수열의 길이중 더 큰것을 취한다

 

문제에서 예제로 주어진 

ACAYKP

CAPCAK

의 공통 부분 수열의 길이를 위의 과정을 토대로 구해보겠습니다

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

0을 넣는 이유는 모든 경우가 저 식의 알고리즘대로 채워지게 하기 위해서이다

답은 4이다

 

원리를 알았으니 이제 구현해보도록하자

 

---

첫번째 제출

s1='0'+input()
s2='0'+input()
# 2차원 배열 만들기
dp=[[0 for i in range(len(s1))] for j in range(len(s1))]

for i in range(1,len(s1)):
    for j in range(1, len(s2)):
        if s1[i] == s2[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j], dp[i][j-1])

print(dp[len(s1)-1][len(s2)-1])

인덱스 에러가 떳다

 

인덱스 에러의 원인은 dp2차원 배열을 생성할때

j가 행

i가 열을

생성하도록 만들었는데 

실제로 인덱싱 할때는 반대로 했기때문에 에러가 생겼다

 

---

수정후 제출

s1='0'+input()
s2='0'+input()
# 2차원 배열 만들기
dp=[[0 for i in range(len(s1))] for j in range(len(s2))]
dp
for i in range(1,len(s1)):
    for j in range(1, len(s2)):
        if s1[i] == s2[j]:
            dp[j][i]=dp[j-1][i-1]+1
        else:
            dp[j][i]=max(dp[j-1][i], dp[j][i-1])

print(dp[len(s2)-1][len(s1)-1])

정답