최장 공통 부분서열 > 문제은행

본문 바로가기


알고리즘 다이나믹1

1220 : 최장 공통 부분서열

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 922 회    시도횟수: 2227 회   



2개의 문자열이 입력 될 경우 두 문자열의 최장공통부분 서열의 길이를 출력하는 프로그램을 작성하라.


부분 서열이란, 원래 문자열에서 임의적으로 몇 개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열들을 말한다. 길이가 0인 문자열이나, 문자열 자기 자신도 부분 서열에 포함된다.


공통 부분 서열이란 문자열 집합 내에서 공통으로 존재하는 부분 서열을 뜻한다. 예를 들어, 다음과 같이 두개의 문자열이 주어진다고 하자.


abcdgh
aedfhr


위 두개의 수열의 최장공통부분서열은 adh 이고 길이는 3 이다.


입력은 두줄로 구성된다.
각 줄에는 최장공통부분서열의 길이를 구하고자 하는 문자열이 입력된다. 문자열의 길이가 1,000 개 이하인 문자열이 입력된다. 
문자열은 알파벳 소문자와 숫자로 구성되어 있으며, 그 외의 문자는 입력되지 않는다.


입력에 대한 최장공통부분서열의 길이를 출력한다.

[Copy]
a1b2c3d4e 
zz1yy2xx3ww4vv
[Copy]
4


[Copy]
abcdgh 
aedfhr
[Copy]
3


[Copy]
abcdefghijklmnopqrstuvwxyz 
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
[Copy]
26



출처 : uva



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.