백준 문제풀이

백준 9251 LCS 문제풀이

LCS 설명 LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열을 뜻한다. LCS는 Dynamic Programming에서 흔히 나오는 문제 중 하나이다. DP 문제는 항상 최대, 최소, 가장 긴, 가장 짧은 값 등을 구하라는 문구가 많다. Subsequence란 무엇인가? Subsequence 를 우리가 흔히 쓰는 Substring과 비교하며 이해해보자. Substring은 Subsequence의 슈퍼셋이다. 즉, Substring인 문자열은 Subsequence이기도 하다. 단, Subsequence인 문자열은 Substring이 아닐 수도 있다. Substring: 반드시 연속되는 형태로 이루어진 부분 문자열이다. ex) abcdefg라는 문자열이 존재할 때, ..