[PYTHON] 백준 9251 - LCS

성능 요약

메모리: 119708 KB, 시간: 144 ms

분류

다이나믹 프로그래밍, 문자열

문제 설명

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

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

---

아이디어, 문제풀이

• LCS는 정해져있는 알고리즘이 존재하고, dp를 활용해야만 문제를 통과할 수 있다.

---

TROUBLE SHOOTING

• 진짜… 이 문제부터 멘탈이 깨진것 같다. 그래프탐색을 위한 dp활용이나, dp특성을 활용한 기본문제들은 적어도 접근이 가능해 오래 고민하다보면 풀어낼 수 있었는데, 정말 잔인한 문제다. (중요한건 내가 앞으로 풀이할 dp문제 중에서 한문제를 제외하곤 전부다 점화식이 정해져있으며, 일반적으로 생각해 낼 수 없다…ㅋㅋ..)

  2차원 dp를 활용해서 문제를 풀어내는데, 뭐랄까… 여태껏 생각해온 방식대로라면 절대 문제를 풀어낼 수 없다. 완전 탐색으로도 풀이해 보려 했는데, 메모리 초과 에러가 뻔히 보여서 결국 다른 풀이들을 참고했다.

• 기본적인 이론은, 두번째 문자열을 한개씩 추가해가며, 첫번째 문자열에 일치하는게 있는지, 일치한다면 총 몇개가 일치하는지, 순서에따라 저장한다. 점화식을 직접 확인해보면 알 수있는데, “구지 순서에 따라” 라는 조건을 만족하기 위해 노력하지 않아도 된다. 애초에 순서대로 체크하며 개수를 늘려나가기 때문!

  여기까지 이해했다면… 이제 점화식을 보며 감탄하면 된다. 보자마자 “아~그러면 되는구나” 하고 생각하긴 했는데, 내가 이걸 제한 시간 안에 짤수 있나?… 생각해보면 역시 불가능한… 그런 문제다.

• 앞서 다른 문제에서 말했듯, dp는 범위 설정이 정말 중요하다. 이 문제는 위 배열, 아래배열의 개수가 같게 예제를 주었기에, 별 생각없이 코딩하다가 수많은 list index를 해결해야했다. 잘 확인하자..

    #세로 가로를 확실하게 체크하지 않으면 인덱스 에러 발생
    dp = [[0] * (b+1) for _ in range(a+1)]

---

코드

#https://www.acmicpc.net/problem/9251
#LCS
#9251

import sys
input = sys.stdin.readline

first_list = list(map(str, input().strip()))
second_list = list(map(str, input().strip()))

# print(first_list)
# print(second_list)

a = len(first_list)
b = len(second_list)

#first 를 second 로 확인
#세로 가로를 확실하게 체크하지 않으면 인덱스 에러 발생
dp = [[0] * (b+1) for _ in range(a+1)]

# print(dp)

def fun():
    for i in range(1, a+1):
        for j in range(1, b+1):

            # if first_list[i] == 0 or second_list[j] == 0:
            #     continue

            if first_list[i-1] == second_list[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1

            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp

result = fun()
# print(result)
answer = result[a][b]
print(answer)