백준 9251 LCS 골드5(DP)

문제 설명

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

- ex) ACAYKP와 CAPCAK의 LCS는 ACAK

입력값

1. 문자열1

2. 문자열2

- 알파벳 대문자로만 이루어져 있으며 최대 1000글자

 

- 예제

ACAYKP
CAPCAK

출력값

- 두 문자열의 LCS 길이

 

- 예제 답 : 4

 

 

 

문제 풀이

첫번째 시도

같은 패턴의 길이 중 가장 긴 길이를 출력하라는 줄 알고 잘못 풀었다..!

# 단순히 패턴이 겹치는 것 중 긴 패턴을 찾으라는 줄 알고 잘못 품..!

text = input()
pattern = input()

# 최장 길이 count
max_cnt = 0
cnt = 0

N = len(text)
M = len(pattern)

if N > M :
    for i in range(N-M+1) :
        for j in range(M) :
            if text[i] == pattern[j] :
                cnt += 1
            else :
                if max_cnt < cnt :
                    max_cnt = cnt

else :
    for i in range(M-N+1) :
        for j in range(N) :
            if text[i] == pattern[j] :
                cnt += 1
            else :
                if max_cnt < cnt :
                    max_cnt = cnt

print(max_cnt)

 

 

 

 

두번째 시도

-예제는 맞지만 반례를 발견함

ABCDEFG

AKCRELG

- 한 글자씩 서로 비교해야하는데 지나간 글자는 비교하지 않아서 발생하는 문제

text = input()
sentence = input()

N = len(text)
M = len(sentence)


# 최장 길이 count
max_cnt = 0
cnt = 0

i = j = 0


while i < N and j < M :
    if text[i] == sentence[j] :
        if i == N-1 :
            cnt += 1
            break
        else :
            cnt, i, j = cnt +1, i+1, j+1
    else :
        if i == N-1 :
            j += 1
        else :
            i += 1

if max_cnt < cnt :
    max_cnt = cnt

# 값 초기화
i = j = cnt = 0

while i < N and j < M :
    if text[i] == sentence[j] :
        if j == M-1 :       # 패턴의 맨 끝 단어까지 같은 단어가 나오면 중단
            cnt += 1
            break
        else :
            cnt, i, j = cnt +1, i+1, j+1
    else :
        if j == M-1 :
            i += 1
        else :
            j += 1

if max_cnt < cnt :
    max_cnt = cnt

print(max_cnt)

 

 

세번째 시도 : 성공

# 118572KB, 124ms

text = input()
sentence = input()

N = len(text)
M = len(sentence)

dp = [[0]*(M+1) for _ in range(N+1)]

for i in range(1, N+1) :
    for j in range(1, M+1) :
        if text[i-1] == sentence[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[N][M])

 

- 2차원 배열의 dp 테이블 생성

- 하나씩 문자를 비교하며 최장 공통 부분 수열을 dp 테이블에 저장

- 문자가 같으면 이전 글자 비교한 값 + 1

- 문자가 다르면 현재 글자와 이전 글자, 이전 글자와 현재 글자 비교한 값 중 큰 값

 

 

 

 

 

네번째 시도 : 성공

- 다른 사람 코드를 보니 나보다 빠르고 메모리도 효율적인 것을 발견!

- 차이점을 살펴보니 DP 테이블을 1차원으로 만들어서 사용하고 있었다

 

# 1차원 배열로 풀기
# 110728KB, 104ms

s1 = input()
s2 = input()

n = len(s1)
m = len(s2)

dp = [0]*m

for i in range(n) :
    temp = 0
    for j in range(m) :
        if temp < dp[j] :
            temp = dp[j]        # 지금까지의 최대값 저장
        elif s1[i] == s2[j] :   # dp[j]의 값이 더 크다면 이미 계산된 글자이므로 elif(다시 계산할 필요 없음)
            dp[j] = temp + 1    

print(max(dp))

 

 

포인트1

- temp에 현재 열(j)까지의 최댓값을 저장

- temp는 LCS 값을 계산할 때 활용된다

 

 

포인트2

- elif 의 사용

- temp보다 dp[j]의 값이 더 크다면 이미 지나온 값이므로 계산할 필요가 없음!

- ex) ABCDEF, ASCREK 의 경우 첫 문자열의 C를 기준으로 ASCREK를 검사할 때, 앞의 A,S 값은 계산할 필요 없음(A를 볼 때 temp의 값이 1이 되어 `temp < dp[j]` 조건이 참이 되므로  불필요한 계산을 피하게 해줌)