백준 문제 주소 https://www.acmicpc.net/problem/9251
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
ACAYKP
CAPCAK
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
4
동적계획법 시리즈를 풀고있다보니 이제 문제를 풀 준비로 dp 배열을 만드는 것, 최솟값을 구한다면 min 함수를 사용하고 최댓값을 구한다면 max를 사용하는 것이 바로 생각이 난다.
이 문제도 바로 최대 길이를 찾아낼 수 없기 때문에, 아래부터 차근차근 더해가면서 계산을 해야할 것 같았다.
이 시리즈를 풀면서 많이 사용한 방법인데, 2차원 배열을 만들어서 그 전의 값과 비교한 다음 큰 것을 넣어주는 방법을 사용할 것이다.
이 문제를 풀 때, 주의할 점은 한 문자열에 같은 알파벳이 포함되어 있어도 중복으로 세지 않는 것이다. 따라서 평소 점화식과는 좀 다르게 나뉘게 된다.
첫 번째와 두 번째 문자열의 요소가 같을 때, 글자 추가 전 값에서 1을 더해준다.
dp[i][j] = dp[i-1][j-1] + 1
첫 번째와 두 번째 문자열의 요소가 같지 않을 때, 이전까지 비교한 값들 중에 최대 값을 넣는다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
n, m = input(), input()
h = len(n)
dp = [[0 for _ in range(h+1)] for _ in range(h+1)]
for i in range(1, h+1):
for j in range(1, h+1):
if n[i-1] == m[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])
백준에서 런타임에러(IndexError)가 발생했다. index-1을 사용하기 때문에 1부터 반복문을 돌렸는데 어디서 오류가 나는지 모르겠어서 이 문제로 고민을 길게 했다. 문제였던 부분은 입력이었는데, 예제 입력과 다르게 실제 입력들은 두 문자열의 길이가 다를 수 있었다. 문제에서 두 문자열의 길이가 같다는 부분이 없었는데 예제 입력만 보고 같다고 생각하고 코드를 짠 것이었다.
n, m = input(), input()
w, h = len(n), len(m)
dp = [[0 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1, h+1):
for j in range(1, w+1):
if m[i-1] == n[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])
w와 h, m과 n에 대하여 index를 잘 맞춰줘야지 IndexError가 발생하지 않았다.
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val n = br.readLine()
val m = br.readLine()
val dp = Array(m.length+1){ Array(n.length+1){0} }
for(i in 1..m.length) {
for (j in 1.. n.length) {
if (m[i-1] == n[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
println(dp[h][w])
}