목록LCS (1)

Devlog_by_0giru

[boj] LCS2_9252

최장 공통 부분 수열이라고 부르는 알고리즘이다. 영어로 LCS(Longest Common Subsequence) 라고 하는데, 최장 공통 부분 문자열도 LCS라고 부르는 모양이다. 둘의 차이점은 공통 부분이 연속하느냐, 마느냐인 것 같다. 이 부분에 대해서는 나중에 후자인 LCS를 공부할 때 다시 수정할 계획이다. 백준 9252번을 풀기 위해 필요한 알고리즘인데, 아주 클래식한 알고리즘이기도 하니 필수적으로 알고 있어야 한다. https://www.acmicpc.net/problem/9252 LCS 알고리즘을 풀기 위해서는 검사할 두 문자열의 앞에 공백 문자열(혹은 더미 문자열)을 하나씩 붙여주어야 한다. 검사할 문자열이 ACAYKP, CAPCAK라고 하자. (백준 9252번의 테스트 케이스이다.) 위 ..
[PS] 2021. 3. 4. 22:12
이전 Prev 1 Next 다음