분류 전체보기 (49) 썸네일형 리스트형 [DP] LCS (Longest Common Subsequence) Substring vs Subsequence substring: 연속되고 진행 순서도 맞는 부분 문자열 subsequence: 연속적이지는 않지만 진행 순서는 맞는 부분 문자열 ex) Iamhungry substring: "mhun" subsequence: "mugy" LCS의 길이 구하기 예시로 설명하는게 편하기 때문에 예시를 하나 들어보겠다. 문자열 ACAYKP와 CAPCAK가 있다고 가정해보자. ACAYKP 를 기준 string으로, CAPCAK를 비교 String으로 두자. 그렇다면, 아래의 표와 같은 모양이 생성된다. 첫 번째로 할일은 문자열 맨 앞에 0을 추가해 첫번째 행과 열을 모두 0으로 만드는 것이다. 이유는 나중에 LCS를 찾을 때 0이 되면 반복문을 종료하기 위해서이다. 여기가 (0,.. 이전 1 ··· 4 5 6 7 다음