BOJ 9251 LCS

태그

다이나믹 프로그래밍

문자열

URL

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

이번 문제는 LCS(Longest Common Subsequence)로 DP의 예제로 잘 알려진 문제입니다. https://www.acmicpc.net/problem/9251

문제 설명

•

두 문자열 S1S_1S1​, S2S_2S2​에 대해 LCS(가장 긴 공통부분 문자열)의 길이를 구하는 문제

예제 입력/출력

•

입력1

ACAYKP
CAPCAK
Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

N,M≤1,000N, M ≤ 1,000N,M≤1,000

◦

NNN: S1S_1S1​의 길이

◦

MMM: S2S_2S2​의 길이

문제 풀이

풀이1 브루트 포스 - O(2N⋅2M)O(2^N \cdot 2^M)O(2N⋅2M)

풀이2 그리디

풀이3 DP - O(N⋅M)O(N \cdot M)O(N⋅M)

풀이 코드

•

Bottom-Up 방식의 구현

s1 = input()
s2 = input()

N, M = len(s1), len(s2)
s1 = " " + s1
s2 = " " + s2

# 초기값 처리
dp = [[0] * (M + 1) for _ in range(N + 1)]

# DP Table 갱신
for n in range(1, N + 1):
    for m in range(1, M + 1): # dp[n][m]
        if s1[n] == s2[m]:
            dp[n][m] = dp[n - 1][m - 1] + 1
        else: 
            dp[n][m] = max(dp[n - 1][m], dp[n][m - 1])

print(dp[N][M])
Python
복사

Top-Down 방식의 구현 (시간 초과)

알아두면 좋은 내용들

DP 테이블을 잘 설계하는 방법