[DP] 2. 백준 9251번

코딩테스트

코딩테스트 관련 알고리즘은 아래와 같다. 주로 이 아래의 알고리즘들 아래에서 문제가 출제된다 생각하고 확실하게 학습하고 지나가야 한다.

• DFS/BFS
• 이진 탐색
• DP (Dynamic Programming)
• 최단 경로: 다익스트라/플루이드 워셜
• 유니온 파인드/크루스칼/부분합/투 포인터

다이나믹 프로그래밍

다이나믹 프로그래밍은 규칙을 찾아내는 것에 집중해야 한다. 그러기 위해서는 특정 몇개의 입력값에 대한 출력값이 도출되는 과정들을 하나하나씩 적어보면서 규칙을 찾아낼 필요가 있다.

백준 9251번

문제 링크

LCS 참고: 최장공통문자열과 최장공통부분수열(문자열간 공백 존재 가능)

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

문자열의 길이가 1000이라 가정하고 모든 부분 문자열 조합을 만들어본다면, ${1000\choose 1} + {1000\choose 2} + {1000\choose 3} + .. {1000\choose 1000} = 2^{1000}$의 문자열 경우의 수가 나온다. 입력된 두 문자열로 만들 수 있는 부분 문자열의 조합을 모두 생각해낸 뒤, 겹치는 것 주 길이가 가장 긴 공통 부분 문자열을 뽑아내는 방법도 존재하겠지만, 상당히 비효율적으로 보인다. 우선 조합을 만들어내는 시간 복잡도 또한 굉장히 높을 것으로 예상된다. 그렇다면 어떻게 효율적으로 해결할 수 있을까?

이를 DP를 통해 해결해나갈 수 있다. 해당 파트는 설명이 길어 꼭 참고자료를 확인하길 바란다.

위의 정답 형태를 관찰하면 알겠지만, 마치 점화식의 꼴, 즉 이전의 정답값을 활용해 다음의 정답값을 도출해내는 것을 발견할 수 있다. 다만, 점화식을 세우기 위해서는 총 2가지 조건을 세워야 한다.

1) 초기값은 무엇인지 (= 탈출 조건은 무엇인지)
2) 점화식은 무엇인지

이때 초기값으로는 0을 입력한다. 즉, 이 문자열 이전으로 최장의 공통부분수열이 없었음을 의미한다.
이후의 점화식은 다음과 같다.

1. 문자열A, 문자열B의 한글자씩 비교해본다.
2. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시한다.
3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 한다.
4. 위 과정을 반복한다.

코드 풀이

항상 생각하자. 중요한 것은 문제를 어떻게 해결할 것인지에 대한 논리이고, 코드는 그저 이를 옮겨적는 언어일 뿐이다!

import sys

string_a = ' ' + sys.stdin.readline().rstrip()
string_b = ' ' + sys.stdin.readline().rstrip()
dp = [[0] * len(string_b) for _ in range(len(string_a))]

for i in range(1, len(string_a)):
    for j in range(1, len(string_b)):
        if string_a[i] == string_b[j]:
            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])