[BaekJoon] 15482 한글 LCS (Gold 5) - Python

문제

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, "최백준"과 "백준온라인"의 LCS는 "백준"이고, "스타트링크"와 "스트라토캐스터"의 LCS는 "스트"이다.

---

입출력 예시

 

입력: 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 최대 1000글자이고, 유니코드 U+AC00(가)부터 U+D7A3(힣)까지로만 이루어져 있으며, UTF-8로 인코딩 되어 있다.

출력: 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

입력예시1)

최백준
백준온라인

출력예시1)

2

 

입력예시2)

스타트링크
스트라토캐스터

출력예시2)

2

 

입력예시3)

선데이코딩
딩코이데선

출력예시3)

1

 

입력예시4)

가나다라가나다라
가다나가다라

출력예시4)

5

---

코드

 

LCS문제는 DP로 푼다

그 저어어어기 코드에 링크 적어놨는데, 들어가서 보면 진짜 정말 자세하게 설명되어 있다.

 

간단히 점화식부터 설명하자면,

if i == 0 or j == 0: LCS[i][j] = 0
elif string_a[i] == string_B[j]: LCS[i][j] = LCS[i - 1][j - 1] + 1
else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

이다.

 

맨 처음 라인은 마진, 즉 맨 앞의 쓸데없는 부분을 전부 0으로 설정한 것 이다

 

두 번재 라인은 두 문자가 같은 경우이다.

두 문자가 같은 경우, 해당 인덱스값을 대각선 앞의 인덱스 값에 +1을 한 값으로 저장한다.

 

세 번째 라인은 두 문자가 다른 경우이다.

두 문자가 다른 경우, 해당 인덱스 값의 수직으로 한 칸 앞, 즉 i - 1과 j - 1인덱스 중 더 큰 값으로 저장한다.

 

l_1 = list(input()) # 첫 번째 문자열 입력
l_2 = list(input()) # 두 번째 문자열 입력

l_1 = [None] + l_1 # 맨 앞에 더미데이터 추가
l_2 = [None] + l_2 # 맨 앞에 더미데이터 추가

LCS = [[0 for _ in range(len(l_2))] for _ in range(len(l_1))] # LCS를 나타낼 2차원 배열 생성

for i in range(len(l_1)):
    for j in range(len(l_2)):
        if i == 0 or j == 0: LCS[i][j] = 0
        elif l_1[i] == l_2[j]: LCS[i][j] = LCS[i - 1][j - 1] + 1
        else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

print(max(max(LCS))) # 최대값 출력

---

실행 화면

---

채점 결과