본문 바로가기

LCS

BOJ)9252 LCS 2 문제: icpc.me/9252 LCS를 구해주는 문제이다. 다이나믹 프로그래밍을 통하여 LCS를 구해준 뒤 백트래킹하여 해당 LCS를 출력해주면 된다. dp테이블의 정의는 dp[x][y]는 첫번째 문자열을 x까지 두번째 문자열을 y까지 봤을 때 LCS의 크기이다. 점화식은 (if a[x]!=b[y]) dp[x][y]=max(dp[x][y-1],dp[x-1][y]) else dp[x][y]=dp[x-1][y-1] 이 된다. 소스코드에서는 테이블의 정의를 반대로 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include usin.. 더보기
BOJ)13711 LCS4 문제: icpc.me/13711 LCS의 크기를 구하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 LCS를 구할 수 있다. 하지만 LCS4 문제는 N이 10만이기 때문에 다른 방법을 생각해보아야 한다. 단순히 N이 10만에서 최장 공통 부분 수열을 구하라고 한다면 무척 어려운 문제가 되겠지만 다행히 조건이 더 주어진다. 1~N까지 정수는 두 수열 A,B에서 전부 한번 씩 주어진다는 것이다. 우리는 수열 A에서 입력을 받은 후 입력 받은 수의 인덱스로 A[x]의 들어온 순서를 삽입하는 방식으로 A수열을 정의 해준 뒤 A[B[i]]의 LIS를 구함으로서 최장 공통 부분 수열의 길이를 구할 수 있다. 이때 N이 10만이기 때문에 N^2 DP로 LIS를 구하는 방법은 안되고 NlogN 이분 탐색의 방법으로.. 더보기