[백준] 9251번 : LCS - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

9251번: LCS

 

1. 문제 설명

2. 풀이과정

해당 문제는 두 문자열의 부분 수열 중 가장 긴 부분 수열의 길이를 구하는 문제이다.

각 문자열을 2차원 리스트로 고려하여 해당 문자열까지 가장 긴 부분 수열의 길이를 저장해 나간다.

2차원 리스트는 각 문자열의 길이보다 1씩 크게 만들어 제일 앞에는 문자열을 빼는 경우를 생각한다.

초기 2차원 리스트는 위 배열처럼 나타낼 수 있다.

[1][1] 위치에서부터 시작하여 마지막 칸까지 가장 긴 부분 수열의 길이를 저장하는데, 이때  만약 각 현재 위치에서 이전 문자열들이 서로 동일하다면 현재 위치에서의 가장 긴 부분 수열의 길이는 이전 문자열들의 가장 긴 부분 수열의 길이에 1을 더한 값이다.

반면에 현재 위치에서 이전 문자열들이 서로 동일하지 않다면 현재 위치에서의 가장 긴 부분 수열의 길이는 각 이전 문자열까지 가장 긴 부분 수열의 길이 중 최댓값이다.

하여 위의 과정대로 2차원 배열을 채워보면 최종적으로 위 그림과 같이 채워지는 것을 확인할 수 있다.

마지막 문자열까지 확인했을 때 두 문자열의 가장 긴 부분 수열의 길이는 마지막 칸의 값이 된다. [-1][-1] 위치

해당 풀이 방법은 전형적인 DP 알고리즘의 top-down 방식이다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 첫 번째 문자열을 입력받아 각 문자를 리스트로 저장한다. st1 = list(sys.stdin.readline().rstrip())
3. 두 번째 문자열을 입력받아 각 문자를 리스트로 저장한다. st2 = list(sys.stdin.readline().rstrip())
4. 긴 부분 수열의 길이를 저장할 2차원 리스트를 생성하고 초기화한다. 여기서 각 문자열의 길이보다 1칸씩 더 크게 만들어 줘야 한다. dp = list(list(0 for _ in range(len(st2) + 1)) for _ in range(len(st1) + 1))
5. 행의 위치를 1번 행부터 마지막 행까지 for i in range(1, len(dp))
6. 열의 위치도 1번 열부터 해당 행의 마지막 열까지 지정하며 for j in range(1, len(dp[i]))
7. 만약 해당 위치에서 각 이전 문자열들이 서로 동일하다면 if (st1[i - 1] == st2[j - 1])
8. 해당 위치에서 가장 긴 부분 수열의 길이는 이전 문자열들 위치에서 가장 긴 부분 수열의 길이에 1을 더한 값이다. dp[i][j] = dp[i - 1][j - 1] + 1
9. 반면에 해당 위치에서 각 이전 문자열들이 서로 다르다면 else
10. 해당 위치에서 가장 긴 부분 수열의 길이는 각 이전 문자열들의 위치에서 가장 긴 부분 수열의 길이 중 최댓값이다. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
11. 2차원 배열을 모두 채운 뒤, 각 문자열의 마지막 문자까지 가장 긴 부분 수열의 길이를 출력한다. print(dp[-1][-1])

반응형

3. 소스코드

import sys

st1 = list(sys.stdin.readline().rstrip())
st2 = list(sys.stdin.readline().rstrip())

dp = list(list(0 for _ in range(len(st2) + 1)) for _ in range(len(st1) + 1))

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

print(dp[-1][-1])