[백준] 9251 - LCS

문제

9251번: LCS

해결 과정

따로 네이밍이 있는 만큼 유명한 알고리즘 문제인 듯 하다.

결론적으로 혼자 힘으로 풀 수 없었다. 알파벳 별로 배열을 만들어서 푸려고도 해보고 한 글자씩 대조해 보며 일치하면 두 인덱스 모두 1씩 증가시킨 후 탐색하려고도 해봤지만 이는 이미 탐색한 부분을 중복 탐색해 결과를 바꾸는 등 다른 오류를 야기해냈다.

[ LCS 알고리즘 ]

구현은 위의 블로그를 참조해서 해냈다.

결과

#include <stdio.h>
#include <algorithm>

inline bool isEnd(char c) {return c == '\0' || c == '\n';}
inline int max(int a, int b) {return a > b ? a : b;}

int main() {
    
    char s1[1001];
    char s2[1001];
    int r[1002][1002];
    int i, j = 0;
    
    scanf("%s", s1);
    scanf("%s", s2);
    
    std::fill(r[0], r[0] + 1002, 0);
    
    for(i = 0; !isEnd(s1[i]); i ++) {
        
        r[i+1][0] = 0;
        
        for(j = 0; !isEnd(s2[j]); j ++)
            r[i+1][j+1] = s1[i] == s2[j] ? r[i][j] + 1 : max(r[i][j+1], r[i+1][j]);
        
    }
    
    printf("%d\n", r[i][j]);
    
}

 

메모리...

회고

위의 방법은 len(s1) * len(s2)만큼의 메모리를 차지하기 때문에 공간적인 측면에서 썩 효율적이지는 않아 보인다. 다른 사람의 코드에 이에 관한 해결법이 있었다.

#include<stdio.h>
#include<string.h>
#define max(x,y) ( (x)>(y)?(x):(y) )
int main(void)
{
	char s[2][4001];
	short dp[2][4001] = {{0,},},i,j,len[2];
	for(i=0;i<2;++i)
	{
		scanf("%s",s[i]);
		len[i] = strlen(s[i]);
	}
	for(i=1;i<=len[0];++i)
		for(j=1;j<=len[1];++j)
			dp[i%2][j] = s[0][i-1]==s[1][j-1] ? (dp[1-i%2][j-1]+1) : max(dp[1-i%2][j],dp[i%2][j-1]);
	printf("%d",dp[len[0]%2][len[1]]);
	return 0;
}

메모리와 실행 시간 둘 다 잡은 모습이다.

 

사실 방법은 생각보다 간단했다. 위의 링크의 방법을 이용할 때 우리가 계산하는 데에 필요한 배열은 바로 윗 배열이다. 즉, 모든 배열을 메모이제이션(memoization, 동적 계획법의 핵심으로 필요한 변수만을 메모하는 행위)할 필요가 없고 바로 위 배열과 현재 배열만 메모하면 된다.

이번 보완점은 동적 계획법과 직접 맞닿아 있기 때문에 꽤 도움이 되었다.