[다이나믹 프로그래밍] ▲ 9252번 - LCS 2

[백준] 9252번 - LCS 2

(한줄평) 이전에 풀었던 LCS를 잘 이해하고 있다면 쉽게 풀 수 있었던 문제! 메모리, 시간 복잡도를 개선할 수 있는 방향으로 코드를 짜기 위해 고민해야하므로 나중에 한 번 쯤 다시 풀어보는 것이 좋을 것 같다

유사 문제: 9251

https://hseungyeon.tistory.com/311

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

이 문제는 LCS 길이와 LCS를 구하는 문제로 DP테이블에 LCS를 바로 기록하는 방식과 LCS길이를 기록하고 모두 기록한 후 그 값을 토대로 LCS를 구하는 방식 2가지 풀이법이 있다. 메모리, 시간 복잡도 측면에서 2번 풀이가 훨씬 효율이 뛰어나므로 2번 풀이로 풀 것을 추천한다!

(풀이1) DP테이블에 LCS를 기록

풀이 시간: 10분 이내

1) 문제 해결 아이디어

여기서는 dp 테이블에 LCS 길이가 아닌 문자열 a의 i번째까지와 문자열 b의 j번째까지의 LCS를 기록했다. 아래와 같이 이 방식은 문자열의 길이가 길다면 메모리, 시간 복잡도 측면에서 효율이 크게 떨어진다. 

<동작 과정>

1. dp테이블에 LCS를 기록

2. LCS 길이 출력

3. LCS가 빈 문자열이 아니면 LCS 출력

 

2) 소스코드

# 1. dp 테이블에 lcs 기록
a, b = input(), input()  # 알파벳 대문자로 구성된 수열 2개
lenA, lenB = len(a), len(b)
# 문자열 a의 i번째까지 문자열& 문자열 b의 j번째까지 문자열의 LCS 길이
d = [[""] * (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] + a[i - 1]
    # 2. 다른 문자면 같은 값인 곳으로 이동
    else:
      if len(d[i - 1][j]) == len(d[i][j - 1]):
        d[i][j] = d[i - 1][j]
      else:
        d[i][j] = d[i][j - 1]
if d[lenA][lenB] == "":
  print(0)
else:
  print(len(d[lenA][lenB]))
  print(d[lenA][lenB])

(풀이2) DP테이블에 LCS 길이를 기록, LCS 길이 기록을 토대로 LCS 구함(추천)

풀이 시간: 30분 이내

1) 문제 해결 아이디어

여기서는 문자열 a의 i번째까지와 문자열 b의 j번째까지의 LCS의 길이를 기록했다. 다만 dp테이블을 가지고 어떻게 LCS를 구할 수 있을지 고민해봐야 했다. 아래와 같이 LCS 길이만 기록하면 되기 때문에 위 풀이보다 메모리, 시간 측면에서 효율이 크게 증가했다.

<동작 과정>

1. dp테이블에 LCS의 길이를 기록

2. LCS 길이 출력

3. LCS 구하기

4. LCS가 빈 문자열이 아니면 LCS 출력

 

<LCS 구하는 방법>

1. 두 문자열의 LCS 길이 값을 얻은 곳에서 출발

2. 현재 기록하고 있는 LCS(cnt)가 lcs 길이(d[i][j])와 같다면 탈출

3. 같은 문자를 찾을 때마다 LCS에 추가하는 것을 반복

3-1. 두 문자가 같다면 문자를 앞에 추가하고 왼쪽 위 대각선으로 이동

3-2. 위쪽값과 현재값이 같다면 위쪽으로 이동

3-3. 왼쪽값과 현재값이 같다면 왼쪽으로 이동

 

2) 소스코드

# 2. dp테이블에 LCS길이 기록
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 길이 
      
# 두 문자열의 lcs 구하기
i, j = lenA, lenB
lcs = ""  # 두 문자열의 LCS
cnt = 0
while True:
  # 종료 조건
  if cnt == d[lenA][lenB]:
    break
  # 1. 두 문자가 같다면
  if a[i - 1] == b[j - 1]:
    lcs = a[i - 1] + lcs  # 문자를 앞에 추가  
    cnt += 1
    # 왼쪽 위 대각선으로 탐색할 인덱스 변경
    i -= 1
    j -= 1
  # 2. 두 문자가 다르다면
  else:
    # 자신과 같은 값인 곳으로 탐색할 인덱스 변경
    if d[i][j] == d[i - 1][j]:
      i -= 1  # 위쪽
    elif d[i][j] == d[i][j - 1]:
      j -= 1  # 왼쪽
if lcs != "":
  print(lcs)