[다이나믹 프로그래밍] ★★ 9251번 - LCS

[백준] 9251번 - LCS

(한줄평) 접근 방식은 맞았지만 점화식을 세우지 못해 어려웠던 문제.. 1차원 리스트로 접근하는 방식은 아예 생각하지도 못했고 이해하기도 어렵다.. 무조건 복습해야할듯하다

두 문자열의 LCS 길이를 구하는 문제다. 이 문제는 각 문자열의 길이를 하나씩 늘려가며 두 문자열의 LCS를 반복적으로 구하는 것이 핵심이다!! dp 테이블을 2차원 혹은 1차원 리스트로 풀이하는 방식 2가지가 있는데 1차원 리스트를 이용하여 구현항 방식이 조금 더 효율적인 방식이다.

 

<LCS(최장 공통 부분 수열) 문제>

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴것을 찾는 문제

(풀이1) 2차원 리스트 이용

풀이 시간: 50분 이내

1) 문제 해결 아이디어

dp 테이블을 2차원 리스트로 생성하여 푼 방식이다.

 

<경우의 수>

1. 두 문자열의 끝 문자가 같은 경우

두 문자열의 끝 문자가 같다면 두 문자열의 마지막 문자는 무조건 공통 부분 수열에 들어갈 수 있다.

그러므로 (같은 마지막 문자를 제외한 두 문자열의 LCS 길이 + 끝 문자 1개) 가 현재 두 문자열의  LCS 길이가 된다.

2. 두 문자열의 끝 문자가 다른 경우

두 문자열의 끝 문자가 다르면 첫번째 문자열의 끝 문자가 a, 두번째 문자열의 끝문자가 b라고 했을 때 공통 부분 수열에 a, b가 동시에 들어가수는 없다!!

여기서 2가지 경우의 수를 생각해 볼 수 있다.

2-1. 첫번째 문자열에서 끝문자 a를 제외한 문자열과 두번째 문자열의 최장 공통 부분 수열(LCS)

2-1. 첫번째 문자열과 두번째 문자열에서 끝문자 b를 제외한 문자열의 최장 공통 부분 수열(LCS)

그러므로 두 가지의 값 중 최댓값이 현재 두 문자열의 LCS 길이가 된다.

 

<점화식>

[참고] https://suri78.tistory.com/11

[백준알고리즘] 9251번: LCS -Python

 

2) 소스코드

a, b = input(), input()  # 알파벳 대문자로 구성된 수열 2개
lenA, lenB = len(a), len(b)
# 문자열 a의 i번째까지 문자열& 문자열 b의 j번째까지 문자열의 LCS 길이
d = [[0] * (lenB + 1) for _ in range(lenA + 1)]

for i in range(1, lenA + 1):
  for j in range(1, lenB +1):
    # 1. 두 문자열의 끝 문자가 같은 경우
    if a[i - 1] == b[j - 1]:
      d[i][j] = d[i - 1][j - 1] + 1
    # 2. 두 문자열의 끝 문자가 다른 경우
    else:
      d[i][j] = max(d[i - 1][j], d[i][j - 1])
print(d[lenA][lenB])  # 두 문자열의 LCS 길이

(풀이2) 1차원 리스트 이용

풀이 시간: 30분 이내

1) 문제 해결 아이디어

dp 테이블을 1차원 리스트로 생성하여 푼 방식이다.

사실 다른 사람의 풀이를 보긴 했지만 왜 정확히 이런 조건으로 검사를 하고 d[i]가 정확히 무엇을 뜻하는 건지도 잘 이해가 안간다ㅠㅠ

 

 

[참고] https://myjamong.tistory.com/317

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

 

2) 소스코드

# 2. dp 테이블 1차원 리스트
a, b = input(), input()  # 알파벳 대문자로 구성된 수열 2개
lenA, lenB = len(a), len(b)
# 문자열 a의 i번째까지 문자열& 문자열 b의 j번째까지 문자열의 LCS 길이
d = [0] * (lenB + 1)  # 문자열 b의 길이만큼 생성

# 문자열 a의 길이만큼 d 업뎃
for i in range(1, lenA + 1):
  cnt = 0  
  for j in range(1, lenB +1):
    # 누적 변수가 캐시값보다 작은 경우
    if cnt < d[j]:
      cnt = d[j]
    # 같은 글자인 경우
    elif a[i - 1] == b[j - 1]:
      d[j] = cnt + 1
  #print(d)
print(max(d))  # 두 문자열의 LCS 길이