LCS는 longest common subsequence의 약자입니다. 우리나라 말로는 최장 공통 부분 수열을 의미합니다.
이해하기 쉽도록 longest common substring 과 비교해보겠습니다.
substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다.
예를 들어 iamaboy에서 amab는 연속하는 부분 문자열이므로 substring이 되고 aaby는 순서는 일치하지만 연속적이지는 않는 subsqeunce가 됩니다.
LCS 개수 구하기 |
그렇다면 두 문자열에서의 LCS는 어떻게 구할까요?
예시를 들겠습니다. 두 문자열은 ACCGATCG와 GACAT 입니다.
우선 전체는 아래와 같은 구조입니다. ( 아래에 설명이 나옵니다. 우선은 이해하지 마시고 그렇구나 넘어가세요.)
문자열 ACCG와 G의 부분 수열은 G하나 입니다.
문자열 ACCGATCG와 G의 최대 부분 수열은 G하나 입니다.
문자열 ACCGATCG와 GA의 최대 부분 수열은 G,A 총 2개 입니다.
위와 같은 형태로 진행하다보면 아래와 같은 그림이 만들어 지는 것입니다.
점화식의 형태로 나타낸다면,
만약 두 알파벳이 같을때, dp[i][j] = dp[i -1][j - 1] +1
두 알파벳이 다를때는 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
LCS관련 문제 모음입니다.
다 풀어보세요!
백준 알고리즘
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
5502번: 팰린드롬
팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [백준] 2470-두 용액(C++) (0) | 2021.05.25 |
|---|