문제 설명문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.https://www.acmicpc.net/problem/1958 제한 사항 풀이문제를 요약하면, 3개의 문자열의 lcs를 구하는 것이다. 해당 문제는 2개의 문자열의 lcs를 구하는 것을 확장시키는 문제이다.그럼 2개의 문자열의 lcs를 구하는 방법을 알아보자.2개의 문자열의 lcs를 구하는 방법은 두 문자열의 요소를 하나..
문제 설명LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 제한 사항 풀이문제를 요약하면 LCS를 구하는 것이다.LCS는 최장 공통 부분 수열을 의미한다. 최장 공통 부분 수열은 두 개의 문자열 혹은 배열에서 가장 긴 공통된 부분을 의미한다.예를 들어 보자.ACAYKP, CAPCAK 두 개의 문자열의 LCS는 ACAK이다. 그렇다면, 이를 어떻게 구해내는지 알아보자.LCS는 DP를 이용하여 간단하게 구해낼 수 있다.이차원 배열을 통해 메모이제이션을 한다.두 문자열의 각 위치를 비교하며 같을 때와 다..
두 수열이 주어졌을 때, 가장 긴 공통 수열을 찾아내는 문제이다. 앞서 풀었던 가장 긴 증가하는 부분 수열과 비슷하다고 생각할 수 있지만 조금 다른 문제이다. for문을 여러 번 돌려 메모제이션을 이용하여 문제를 풀려했었다. 하지만, 문자열을 계속해서 반복하고 어디까지 일치하는지를 기록해야 하고, 건너뛰는 요소가 있을 수 있기 때문에 쉽지 않았다. 해답은 2차원 배열을 이용한 메모제이션이였다. 입력받은 두 문자열 길이보다 1씩 큰 2차원 배열을 생성한 뒤, 0번째 column과 0번째 row을 0으로 초기화 한 뒤, 문제를 풀어나가면 된다. 0으로 채우는 이유는 기저 조건을 설정하는 것이다. 2중 for문을 이용하여 row와 column의 각 요소들을 비교하며 진행한다. 그러다 일치하는 요소가 발견되면,..
