백준 GOLD 5 [9251번] LCS {언어 : Python} [다시 풀어 보기]

문제 링크

https://www.acmicpc.net/problem/9251

정답 코드 1

a = input()
b = input()
lenA = len(a)
lenB = len(b)
dp = [[0] * (lenA+1) for _ in range(lenB+1)]
maxLength = 0
for i in range(lenB):
    alphaB = b[i]
    for j in range(lenA):
        alphaA = a[j]
        if alphaA == alphaB:
            dp[i][j] += dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        maxLength = max(maxLength, dp[i][j])
print(maxLength)

정답 코드 2

a = input()
b = input()
lenA = len(a)
lenB = len(b)
prevDp = [0] * (lenB+1)
for i in range(1, lenA+1):
    nextDp = [0] * (lenB+1)
    alphaA = a[i-1]
    for j in range(1, lenB+1):
        alphaB = b[j-1]
        if alphaA == alphaB:
            nextDp[j-1] = prevDp[j-2] + 1
        else:
            nextDp[j-1] = max(prevDp[j-1], nextDp[j-2])
    prevDp = nextDp
print(max(prevDp))

풀이 방법

1. lcs라고 최장 공통 부분수열(Longest Common Subsequence) 또는, 최장 공통 문자열(Longest Common Substring)을 사용했다.
2. dp[i][j]에 값을 더해가면서 가장 긴 부분의 길이를 찾는다.
   • 역추적하면 가장 긴 수열도 출력할 수 있다.
3. 알파벳이 같을 경우 대각선의 dp[i-1][j-1]에 1을 더해준다.
4. 다를 경우 상, 좌에 있는 dp[i-1][j]와 dp[i][j-1] 중 큰 값을 넣는다.
5. dp에 가장 큰 값이 공통되는 가장 긴 길이이다.

느낀점

• 전에 비슷한 문제를 풀어봤다.
• 하지만 한 번밖에 안 풀어봐서 그런지 기억이 잘 나지 않았다.

https://sound-programming.tistory.com/352

Softeer [Level 3] 효도 여행 {언어 : JavaScript} [시간초과 해결]

• 결국 다시 푸는 방법을 찾았고 이 분이 쓴 내용이 제일 이해가 잘 되었다.

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

• 1번 풀이는 2차원 배열로 풀어봤고
• 2번 풀이는 1차원 배열로 풀어봤다.

• 2번 풀이가 메모리도 작고 시간복잡도도 낮아서 더 효율적인 것을 알 수 있다.