백준 9252 : LCS

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

DP 문제이다.

진짜 모르겠어서, 낙담해버려 알고리즘을 4일 쉬게 만든 문제이다.

 

생각의 흐름

우선 완전 탐색으로 하면 얼마나 걸릴까 생각을 해보았다.

기본적으로 어떤 글자를 선택할 지를 결정하고, 비교하는 과정으로 진행한다고 가정했다.

이때 어떤 글자를 선택하는 경우의 수가 곧 최종 시간 복잡도라고 봐도 되겠다.

따라서

$2^{1000} \times 2^{1000} = 2^{1001}$

라는 어마어마한 수치가 나온다.

 

그래 우선 완전탐색은 안된다.

그리고 예시를 따라가다보면, 그리디처럼 맹목적인 하나의 규칙이 있어보이는 것도 아니다.

결국 완전탐색은 하면서도 효율적으로 해야하는 DP라는 감을 잡았다.

 

문제는 부분문제로 어떻게 쪼개야할 지 전혀 감이 오지 않았다는 것이다.

예제를 가지고, 글자를 하나씩 추가하면서 오랜 시간 따져보았지만, 이전에 대한 어떤 규칙이 존재하는 것인지 찾는데 실패했다.

 

진짜 1도 감이 안온다..

 

그러다가 결국 일단 이렇게 푸는 거라고 가정하고, 규칙을 추가하는 방향으로 접근하고자 했다.

결론부터 말하자면, 가정이 잘못되어서 결국 푸는데 실패했다.

 

나는 하나의 문자열에 대해서 다른 문자열 글자를 한 개씩 추가하면서, 이전 풀이들을 활용하는 방법을 가정했다.

쉽게 말하자면, dp 배열을 1차원으로 잡았다는 것이다.

하지만 결과적으로 이 방식은 모든 부분문제에 대한 답을 표현하기에는 부족했다.

 

다른 사람의 생각의 흐름 참고하기

헤매이다가 포기하고 하루 쉬고 헤매다가 포기하고 그러고 이틀 동안 쳐다보지도 않다가 용기내어 다시 헤매봤지만 실패했다.

그래서 그냥 답을 찾아봤다 ^^

 

이 과정에서 깨달은 핵심 사항은,

이전 풀이를 참조할 때, 꼭 선형적(1차원)으로 참조하지는 않는다는 것이다.

그리고, 2차원 형태를 분석하려면, 평면 또는 표의 형태를 이용하면 쉽게 그 규칙을 찾을 수 있다는 것이다.

 

결론적으로 내가 헤맸던 부분문제는,

현재 문제에서 가장 끝 글자를 1개 뺀 것이었다(어떤 문자열이든 상관 없음)

 

그래서 알아본 풀이는 다음과 같다.

1번 문자열과 2번 문자열의 LCS의 길이는,

1.

1번 문자열의 마지막 글자와 2번 문자열의 마지막 글자가 같으면,

1번 문자열의 맨 뒤에서 한 글자 뺀 1'번 문자열과

2번 문자열의 맨 뒤에서 한 글자 뺀 2'문자열의

LCS 길이 + 1이다.

2. 1번 문자열의 마지막 글자와 2번 문자열의 마지막 글자가 다르면,

1번 문자열에서 한글자 뺀 1'번 문자열과 2번 문자열 간의 LCS 값 L과

1번 문자열과 2번 문자열의 맨 뒤에서 한 글자 뺀 2'문자열 간의 LCS 값 L'

중 더 큰 값이다.

 

쉽게 코드로 표현하자면

if str1[i] == str2[j]:
	dp[i][j] = dp[i-1][j-1] + 1
else:
	dp[i][j] = max(dp[i-1][j], dp[i][j-1])

이다.

 

LCS 수열 구하기

LCS 수열의 길이는 위와 같이 구했지만, 이제는 LCS 수열 그 자체를 구해야 한다.

그리고 이것이 바로 LCS1 문제와의 차이점이다.

 

사실 이건 생각해내기 그렇게 어렵지 않았다.

일단 2차원 표를 그려놨으니 보기가 훨씬 편했다.

 

빨간색이 문자가 같은 경우이며, 화살표는 답을 표시한 것이고, 파란색이 탐색 경로이다.

 

언제나 값이 제일 큰, 가장 오른쪽 아래에서 시작해서, 

값이 1 증가되는, 그러니까 문자가 같아지는 경우를 어떠한 순서대로 탐색하면 된다.

 

그리고 그 순서는, 우리가 표를 채우던 규칙과 관련이 있다.

문자가 같으면, 대각선으로

문자가 다르면, 더 큰 쪽으로 이동하면 된다.

 

코드

구현의 편의성(표의 가장 왼쪽과 가장 위쪽 줄을 0으로 채우기)을 위해서, 문자열의 index를 1부터 시작하도록 했다. dp에서는 많이들 이렇게 하는 것으로 알고 있다.

str1 = " " + input()
str2 = " " + input()
dp = [[0] * len(str1) for i in range(len(str2))]

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

ans2 = ""
i, j = len(str2)-1, len(str1)-1
while i!=0 and j!=0:
    if str1[j] == str2[i]:
        ans2 = str1[j] + ans2
        i -= 1
        j -= 1
        continue
    if dp[i][j-1] >= dp[i-1][j]:
        j -= 1
    elif dp[i][j-1] < dp[i-1][j]:
        i -= 1

ans = dp[len(str2)-1][len(str1)-1]
print(ans)
if ans != 0:
    print(ans2)