SJ_Koding

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Longest Common Subsequence, 최장 공통 부분 수열 문제는 두 수열이 주어지면, 공통되는 부분수열 중 최고길이를 가지는 수열을 찾는 문제이다. 해당 문제는 골드 V이지만, 한 번이라도 경험해보지 않으면 생각해내기 정말 어려운 문제인 것 같다. 최장 증가하는 부분수열을 구했던 문제와 동일한 난이도였지만, 어떻게 풀어내야할 지 감 조차도 안왔다. (내가 멍청한거 일수도..) 결국엔 이번 포스팅은 내가 ..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP를 입문하는 문제로 피보나치수열과 부분 수열을 구하는 문제가 대표적인 것 같다. 멘토링을 하면서 DP에 조금 더 관심이 생겼는데, 정말 어려운 개념이어서 이해하는데 시간이 걸렸다. 이해를 정립시키기 위해 해당 문제를 블로그에 다시 정리하겠다. 문제요약 문제는 간단하다. 수열이 주어지면 가장 긴 부분 수열을 찾는 문제. (수열 크기 최대 1000) ex1) [1, 100, 2, 300..