개발자꿀꿀이

문제 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라. 풀이 LCS 의 개념을 미리 앞에서 풀어 봤기 때문에 문제를 이해하는데는 어렵지 않았다. conpulake.tistory.com/55 백준 9252 (LCS 2) 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. ..

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 풀이 이문제를 분류를 두는것이 어려웠다. 동적 계획법(Danamic Programming)을 기반을 한 String 문제이기 때문이다. 하지만 중요한건 문자열 이므로 문자열 카테고리에 넣는다. LCS는 두가지가있다. Longest Common Substring (공통 부분 문자열) Longest Common Subsequence (공통 부분 수열) ACAYKP CAPCAK 이 두개의 문자열에서 Substring -> CA Subsequence -> ACAK 이..