목록역추적 (1)

codinging

[알고리즘] LCS(Longest Common Subsequence) 최장 공통 부분 수열 과 역추적(Trace Back) 알아보기

LCS 알고리즘 두 수열 사이에 공통적으로 존재하는 가장 긴 부분 수열을 말한다. 예를 들면 ABCDEF 와 EBDEAF 의 가장 긴 부분수열은 BDEF 이다. 설명 문자열 X[i] = {x1, x2, x3 . . .xi} , Y[j] = {y1, y2, y3 . . .yj} 인 두 문자열이 있다, 그리고 이 두 문자열의 LCS의 길이를 구하는 함수를 LCS_LEN(X[i], Y[j]) 라고 하자 🐧첫번째 경우( i == 0 ) 만약 i == 0 이라면 문자열의 길이가 0이라는 뜻이니 LCS_LEN(X[i], Y[j]) == 0 이다. 🐧두번째 경우( xi == yj ) X[i] 문자열의 i번째 문자 xi 와 Y[i] 문자열의 j번째 문자 yj 가 같다( xi == yj ) 라면 다음과 같은 식이 성립한..
Algorithm 2023. 3. 31. 18:08
이전 Prev 1 Next 다음