[백준/BOJ] 백준 코딩 알고리즘 9251번 LCS Python 다이나믹 프로그래밍

나의 풀이

이 문제는 DP 원리를 사용해서 크게 두 가지 방식으로 나눠 풀 수 있다

첫 번째는 2차원 배열을 사용하는 방식이고

두 번째는 누적합을 사용하는 방식이다

 

2차원 배열은 구현 및 이해 측면에서 좀더 간단하지만 시간 복잡도와 메모리 사용량이 좀 더 크고

누적합 방식은 시간 복잡도와 메모리 사용량을 크게 줄일 수 있지만, 이해 측면에서 살짝 복잡하다

 

첫 번째 : 2차원 배열 

2차원 배열을 사용하여 두 문자열의 중복 길이 여부를 저장한다

 

위 이미지 토대로 설명하자면, 알파 문자열과 베타 문자열을 비교한다

열을 따라 내려오면서 비교한다고 가정할 때,

 

알파 문자열의 문자와 베타 문자열의 문자가 동일하다면 -> 이전 문자열까지의 공통 길이 저장값에 1을 더하여 저장한다

구체적으로는 다음과 같다. dp[i][j] = dp[i-1][j-1]

 

알파 문자열의 문자와 베타 문자열의 문자가 동일하지 않다면 -> 이전 문자열까지의 비교 조합에 따라 최대값을 저장한다

구체적으로는 다음과 같다. dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

이를 코드로 구현하면 아래와 같다

import sys

def input():
  return sys.stdin.readline().rstrip()

A = input()
B = input()

dp = [[0 for j in range(len(B) + 1)] for i in range(len(A) + 1)]
for b in range(1, len(B) + 1):  # 열
  for a in range(1, len(A) + 1):  # 행
    if B[b - 1] == A[a - 1]:
      dp[a][b] = dp[a - 1][b - 1] + 1
    else:
      dp[a][b] = max(dp[a][b - 1], dp[a - 1][b])

print(dp[-1][-1])

 

두 번째 : 누적합

누적합에서는 2차원 배열이 아니라 1차원 배열을 쓴다

문자열 하나의 길이에 따라서 누적 공통 길이 값을 저장할 1차원 배열에 대해서

또 다른 문자열의 각 문자와 비교해가며 값을 업데이트한다

 

이 때, 각 문자를 비교하는 반복문마다 공통 길이 값을 비교하기 위한 cnt값을 계산하는데,

현재 비교하고 있는 곳의 누적 공통 길이의 값이 cnt 값보다 크다면, cnt 값을 업데이트 한다

만약 두 문자가 동일하다면 이전에 저장되어 있던 값에 1을 더한다

 

이를 코드로 구현하면 아래와 같다

# 누적합 방식
import sys

def input():
  return sys.stdin.readline().rstrip()

A = input()
B = input()
acc_sum = [0] * len(A)

for b in range(len(B)):
  cnt = 0
  for a in range(len(A)):
    if cnt < acc_sum[a]:
      cnt = acc_sum[a]
    elif A[a] == B[b]:
      acc_sum[a] = cnt + 1
      
print(max(acc_sum))

 

하지만 주의할 점이 있는데, 두 문자열이 같은지 먼저 비교한다면

같은 문자가 계속해서 반복될 때 cnt가 증가하지 않게 된다는 문제점이 있다

따라서 이에 유의하여 코드를 작성해야 한다.

 

이 과정을 AAAY / YAAA 테스트케이스로 비교해보면 아래와 같다

 

 

참고 페이지

https://myjamong.tistory.com/317

백준 9251 파이썬 - LCS - 동적 계획법