![[9251번] LCS](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fm7JZ1%2FbtqxGvucWR9%2FJm2xqE9OQzHQz3Y92WWKy1%2Fimg.png)
반응형
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
"LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제"입니다.
DP(Dynamic Programming)으로 풀 수 있는 유명한 문제 중 하나입니다.
사실 이 문제에 대한 알고리즘 설명을 드리고 싶지만 저보다 잘 설명하시고 자료도 많으신 블로거 분들이 많이 계셔서
그중 제가 참고했던 [블로그 하나]를 소개하겠습니다. ㅎㅎ
이 문제에서 얻어갈 것은 LCS 알고리즘에 대한 이해도 있지만, 역시 활용을 위한 근본적 원리 이해가 중요할 것으로 사료됩니다.
혹시 이해가 어려우시다면 이 문제는 보면서 이해를 하는 것도 좋다고 생각합니다.
DP문제의 아이디어 중 하나를 알아간다는 기분으로 말입니다.
반응형