📖Problem

9251번: LCS

🔍Intuition: LCS 개념

아래는 굉장히 잘 정리해주신 블로거분의 개념정리 게시글이다.

LCS에 대한 개념을 알아야 문제를 풀 수 있기 때문에 제한시간 1시간 내에 개념에 대한 이해를 먼저 하고 시작했다.

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

(표를 만들고 싶었지만 나도 시험기간인지라 이해만 하고 넘어감)

<aside> 🔍 문제 풀이에 필요한 내용 : Longest Common Subsequence 길이 구하기

</aside>

점화식

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

최장 공통 부분수열의 점화식을 코드로 작성해보았습니다. 위와 마찬가지로 LCS라는 2차원 배열에 매칭하고 마진값을 설정한 후 검사한다.

1. 문자열A, 문자열B의 한글자씩 비교한다.
2. 두 문자가 다르다면, 왼쪽 값이나 위쪽 값, 즉 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시한다.
3. 두 문자가 같다면 이전 값에 +1하기 위해 LCS[i - 1][j - 1] 값을 찾아 +1 한다.
4. 위 과정을 반복한다.

🔍Approach

🚩나의 제출 과정 코드 기록