LCS - BOJ 9251번
안녕하세요! 꼬부기입니다. 이번 문제는 BOJ 9251번 - LCS 입니다. 1. 개요 LCS는 Longest Common Subsequence의 약자로, 해석하면 최장 공통 부분 문자열입니다. 연속적인 부분 문자열인 substring과는 달리 subsequence는 연속적이지 않은 부분 문자열입니다. 익숙한 숫자로 생각을 해보면 다음과 같은 집합이 있다고 가정하겠습니다. S = {4, 7, 3, 1, 2, 9, 5} 이때, substring은 {4, 7, 3, 1}, {3, 1, 2, 9} 또는 {7, 3, 1, 2, 9, 5}와 같이 연속적인 부분집합입니다. 반면에 subsequence는 {4, 1, 9}, {1, 5}와 같이 흔히 우리가 알고 있던 부분집합과 같은 개념이라고 접근하면 이해하기 편합니..
2018. 4. 4.