백준(G5) 9251번: LCS(파이썬,Python3)

나는 이 문제를 DP 알고리즘 중 Tabulation(상향식)을 이용해서 풀었다.

DP에 대해 간단히 설명을 하자면 Tablulation(상향식)과 Memoization(하향식)이 있다.

 

Tabulation은 우리가 흔히 아는 DP 알고리즘이다.

중복된 값은 계산하지 않으며 이전에 계산한 값을 바탕으로 새로운 값을 계산한다.

피보나치수열을 예시로 들 수 있다.

f[i] = f [i-1] + f [i-2]에서 볼 수 있듯이 이전에 계산한 값을 바탕으로 새로운 값을 계산하는 방법이다.

 

Memoization은 결과값에 접근하려는 시도를 하고, 해당 값에 가까운 값을 DP에서 찾아나가며 탑 다운의 형태로 중복된 값을 사용하거나 메모하는 형태를 띤다. 

 

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

9251번: LCS

문자열이 두개 주어지고 문자열의 최장 부분수열을 구하는 문제다.

이 문제를 보자마자 다들 이론은 쉽게 생각할 것이라고 생각한다.

이중 반복문을 사용한 다음 문자 하나와 문자열 전체를 비교하는 방식으로 문제를 풀면 된다.

그런데 DP를 접목해서 풀어야 한다.

 

코드와 함께 설명하겠다.

 

list1,list2 = input().strip(),input().strip()
 
len_list1, len_list2 = len(list1),len(list2)
table = [[0] * (len_list2 + 1) for _ in range(len_list1 + 1)]   

문자열 두개를 입력받은 뒤, 변수 두 개에 문자열의 길이를 각각 넣는다.

이후 반복문을 이용해 2차원 배열을 만든다. 이때 X축과 Y축을 매우 주의해야 한다..(이것 때문에 3번 틀렸다)

 

 

for i in range(1,len_list1 + 1):
    for e in range(1,len_list2 + 1):
        if list1[i-1] == list2[e-1]:
            table[i][e] = table[i-1][e-1] + 1
        else:
            table[i][e] = max(table[i][e-1], table[i-1][e])

첫 번째 문자열의 문자와 두 번째 문자열의 문자들을 비교하는 방식으로 이중 반복문을 만들었다.

이때 이전 문자를 비교해 같으면 현재 문자 값에 1을 더하고 다르면 더 큰 값을 찾는 방식으로 풀었기 때문에 for 반복문의 범위를 1부터 문자열의 길이 + 1 한 값으로 풀어야한다. 

이전 문자가 같으면 더 큰 값을 찾을 필요 없이 전 값에 1을 더하면 되고 이전 문자가 다르면 x축에서 1을 뺀 값과 y축에서 1을 뺀 값을 비교해 더 큰값을 현재값으로 설정한다.

 

정답코드:

 

import sys
input = sys.stdin.readline
 
list1,list2 = input().strip(),input().strip()
 
len_list1, len_list2 = len(list1),len(list2)
table = [[0] * (len_list2 + 1) for _ in range(len_list1 + 1)]   
for i in range(1,len_list1 + 1):
    for e in range(1,len_list2 + 1):
        if list1[i-1] == list2[e-1]:
            table[i][e] = table[i-1][e-1] + 1
        else:
            table[i][e] = max(table[i][e-1], table[i-1][e])
print(table[-1][-1])