[BOJ] 백준 9251 LCS / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

많이 알려진  Longest Common Sequence(LCS)  문제이다.

 

두 문자열이 입력으로 주어질 때, 이 두 문자열의 공통되는 부분 중 가장 긴 문자열의 길이를 출력하는 문제이다.

 

이 외국 유튜버의 풀이 를 참고하며 3가지 풀이로 접근해보았다.

 

 

1. 재귀 (Recursion)

2. 메모이제이션 (Memoization)

3. 동적 계획법 (Dynamic Programming)

 

 

 

 

💭 풀이 과정

 

 

 

1. 재귀 방식의 풀이

 

 

작성 언어: C++

 

#include <cstdio>	// c 표준 입출력
#include <algorithm>	// std::max

char str1[1001], str2[1001];

int LCS_recurs(int index1, int index2){
    if (str1[index1] == '\0' || str2[index2] == '\0') {
        return 0;
    }else if (str1[index1] == str2[index2]) {
        return 1 + LCS(index1 + 1, index2 + 1);
    }else {
    	return std::max(LCS(index1 + 1, index2), LCS(index1, index2 + 1));
	}
}

int main(){
    scanf(" %s %s", str1, str2); // 입출력버퍼에 '\n'을 남기지 않기 위해 %s 앞에 공백을 둠
    printf("%d\n", LCS_recurs(0, 0));
    return 0;
}

 

 

LCS_recurs 함수에서 보이는 것 처럼, 첫 비교의 시작은 두 문자열의 0번 인덱스이다.

 

만약 두 문자가 같다면, 리턴 값에 1을 더하고 두 문자열의 다음 인덱스를 비교한다.

 

두 문자가 다르다면, 한 문자열의 인덱스를 증가한 것과 다른 문자열의 인덱스를 증가한 것 중 리턴 값이 더 큰 것을 반환한다.

 

두 문자 중 하나라도 '\0' 이라면 (문자열의 끝) 0 을 리턴하게 된다.

 

 

그러나,  이 풀이는 지수의 시간이 걸리므로 문자열의 길이가 길어지면 기하 급수적인 시간이 걸리게 된다.

 

 

 

 

2. 메모이제이션

 

 

작성 언어: C++

 

#include <cstdio>	// c 표준 입출력
#include <algorithm>	// std::max

int memo[1001][1001] = {0, };
char str1[1001], str2[1001];

int LCS(int index1, int index2){
    if (memo[index1][index2] != 0) {
        return memo[index1][index2];
    }else {
        if (str1[index1] == '\0' || str2[index2] == '\0') {
            return 0;
        }else if (str1[index1] == str2[index2]) {
            return memo[index1][index2] = 1 + LCS(index1 + 1, index2 + 1);
        }else {
            return memo[index1][index2] = std::max(LCS(index1 + 1, index2), LCS(index1, index2 + 1));
        }
    }
}

int main(){
    scanf(" %s %s", str1, str2);	// 입출력버퍼에 '\n'을 남기지 않기 위해 %s 앞에 공백을 둠
    printf("%d\n", LCS(0, 0));
    return 0;
}

 

 

이미 수행한 연산은 memo 배열에 저장되어있어서 중복되는 연산이 호출되면 배열에 저장된 값을 리턴한다.

 

결국 이 방식은 memo 배열의 크기만큼 시간이 걸린다고 볼 수 있다. => O(M*N)

 

 

 

 

3. 동적 계획법

 

 

작성 언어: C++

 

#include <cstdio>	// c 표준 입출력
#include <algorithm>	// std::max

int dp[1001][1001] = {0, };
char str1[1001], str2[1001];

int LCS_dp(int row, int col){
    for (int i = 1; i <= row; ++i) {
        for (int j = 1; j <= col; ++j) {
            if (str1[i-1] != str2[j-1]) {
                dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
            }else {
                dp[i][j] = 1 + dp[i-1][j-1];
            }
        }
    }
    
    return dp[row][col];
}

int main(){
    int result;
    scanf(" %s %s", str1, str2);
    result = LCS_dp((int)strlen(str1), (int)strlen(str2));
    printf("%d\n", result);
    return 0;
}

 

 

입력데이터인 "ACAYKP" 와 "CAPCAK" 을 예로 풀어보면 다음과 같다.

 

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 

 

ACAYKP 의 'A' 와 CAPCAK 를 먼저 비교한다.

다른 문자라면 dp[i-1][j] 와 dp[i][j-1] 중 더 큰 값으로 채우고, 같은 문자라면 dp[i-1][j-1] 에 하나 더 증가한 값으로 채운다.

다음 ACAYKP 의 'C' 와 CAPCAK 를 비교하는 순서로 진행된다.

배열 가장 우측하단 항 값이 최대 공통 부분 수열의 길이가 된다.

 

또한 값을 추적하면 그 공통 수열이 "ACAK" 라는 것도 찾을 수 있다.

 

백준 채점 시스템에서 메모이제이션은 288ms, 동적 계획법은 4ms 이라는 실행시간이 나왔다.

 

 

 

 

🏆 배운 점

 

 

잘 알려진 LCS (Longest Common Sequence) 문제 풀이를 세 가지 풀이로 접근하면서

 

각 기법을 좀 더 잘 이해하게 되었고,

 

실행시간으로 수치화된 결과를 통해 비교하면서 효율성을 더 명확히 알 수 있어 유익한 풀이였다.