링크
https://www.acmicpc.net/problem/9251
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
예제 입력 1
ACAYKP
CAPCAK예제 출력 1
4
아이디어 스케치
- 이 문제는 동적계획법 알고리즘을 이용하는 대표적인 문제 중 하나인 LCS 문제이다.
- 주어진 두 문자열의 길이는 항상 서로 같지 않기 때문에 각 문자열의 맨 뒤부터 비교를 하면 앞에서부터 비교하는 것보다 수월하다.
- 동적계획법 알고리즘을 이용해야 시간초과가 발생하지 않기 때문에 dp 테이블을 만든 후 각 경우의 결과 값을 저장(기억)하며 문제를 풀어나가면 된다.
코드 분할 설명
char a[1000]; // 첫번째 문자열을 저장하는 배열
char b[1000]; // 두번째 문자열을 저장하는 배열
int n, k;
scanf("%s", &a);
scanf("%s", &b);
n = strlen(a); // 첫번째 문자열의 길이
k = strlen(b); // 두번째 문자열의 길이
// 2차원 배열 동적할당
dp = (int**)calloc(n+1, sizeof(int*));
for (int i = 0; i < n+1; i++)
dp[i] = (int*)calloc(k+1, sizeof(int));- 주어지는 두 문자열의 최대 길이는 1000이므로 문자열을 저장할 배열의 크기를 각 1000으로 설정한다.
- 각 문자열을 입력 받은 후 n과 k에 각각의 문자열의 길이를 저장한다.
- 동적계획법에 쓰일 dp테이블을 n+1 x k+1 크기로 동적할당한다.
void LCS(char a[], char b[], int n, int k)
{
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < k + 1; j++) {
if (i == 0 || j == 0) // a와 b문자열 중 하나의 길이라도 0이면
dp[i][j] = 0;
else if (a[i - 1] == b[j - 1]) // 현재 비교한 문자가 같은 경우
dp[i][j] = dp[i - 1][j - 1]+1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // a문자열의 포인터를 1 감소시킨 경우와 b문자열의 포인터를 1 감소시킨 경우 중 일치하는 문자열의 개수가 더 값을 저장
}
}
}- 이 문제의 핵심 알고리즘이다.
- 이중 for문을 이용하여 dp테이블을 채워나가는 코드이다.
- i와 j는 각각 첫 번째 문자열과 두 번째 문자열에서 현재 선택한 문자의 인덱스를 뜻한다.
- i 또는 j가 0인 경우는 두 개의 문자열 중 하나의 길이가 0인 경우로 문자열을 서로 비교할 수 없는 경우이기 때문에 0을 저장한다.
- a[i-1] == b[j-1]인 경우는 현재 비교한 문자가 같은 경우로 현재까지 구한 LCS길이에 +1을 한 후 저장한다.
- 마지막 경우는 첫 번째 문자열의 포인터를 1 감소시킨 경우와 두 번째 문자열의 포인터를 1 감소시킨 경우 중 LCS의 길이가 더 큰 값을 저장한다.
전체코드
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a,b) a > b ? a : b
int** dp; // 동적계획법에 사용할 dp 테이블
void LCS(char a[], char b[], int n, int k)
{
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < k + 1; j++) {
if (i == 0 || j == 0) // a와 b문자열 중 하나의 길이라도 0이면
dp[i][j] = 0;
else if (a[i - 1] == b[j - 1]) // 현재 비교한 문자가 같은 경우
dp[i][j] = dp[i - 1][j - 1]+1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // a문자열의 포인터를 1 감소시킨 경우와 b문자열의 포인터를 1 감소시킨 경우 중 일치하는 문자열의 개수가 더 값을 저장
}
}
}
int main()
{
char a[1000]; // 첫번째 문자열을 저장하는 배열
char b[1000]; // 두번째 문자열을 저장하는 배열
int n, k;
int cnt = 0;
scanf("%s", &a);
scanf("%s", &b);
n = strlen(a); // 첫번째 문자열의 길이
k = strlen(b); // 두번째 문자열의 길이
// 2차원 배열 동적할당
dp = (int**)calloc(n+1, sizeof(int*));
for (int i = 0; i < n+1; i++)
dp[i] = (int*)calloc(k+1, sizeof(int));
LCS(a, b, n, k); // LCS 함수 실행
printf("%d", dp[n][k]); // 결과 출력
// 메모리 할당 해제
for (int i = 0; i < n; i++)
free(dp[i]);
free(dp);
return 0;
}제출 결과
IT Velog