https://www.acmicpc.net/problem/9251처음 문제를 봤을때, 접근법이 선뜻 떠오르지 않았던 문제이다.dp 알고리즘의 대표격인 문제라 정리해둔다. LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제부분 수열이란?원래 수열에서 몇 개를 골라 순서는 유지한 채 만든 수열이다.- 순서는 유지해야 한다.- 중간 원소는 건너뛰어도 된다. 예를 들어 원래 수열이 [2, 3, 5, 6, 9] 라면, 부분 수열은- [2, 3, 5, 6]- [2, 5, 6]- [3, 9]... 등이 있다.이런식으로 원래 순서만 안 바꾸면 된다. 왜 DP 알고리즘 대표 문제일까?DP의 핵심 사고 방식은 다음과 같다.1. 큰 문제를 작은 문제로 나누고,2. 그 작은 문제의 답을 재사..