LCS(Longest Common Subsequence) 알고리즘 (E), 백준 18438 LCS5(C++)

이전글

 

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (D), 백준 13711 LCS4(JAVA)

LCS(Longest Common Subsequence) 알고리즘 (D), 백준 13711 LCS4(JAVA)

에 이어서, 백준 18438 - "LCS 5" 문제를 풀어보겠습니다.

 

여태까지는 JAVA를 이용해 문제를 풀었지만 이번 "LCS - (E)"부터 C++을 이용해 풀겠습니다.

LCS - (E) 부터는 문제의 "시간 제한" 과 "메모리 제한"이 굉장히 타이트하기 때문에 C를 이용하지 않으면 안될 것 같습니다(순전히 제 생각 ㅎㅎ)

 

 

 

https://www.acmicpc.net/problem/18438

18438번: LCS 5

백준 18438 - "LCS 5"

 

문제만 본다면 "백준 9252 - LCS 2" 문제와 똑같습니다. 다만, 메모리 제한이 256MB에서 4MB로 줄었습니다. 줄어도 너무 많이 줄었죠?

 

이 LCS 문제가 이렇게 메모리를 조금만 사용해도 풀 수가 있는 문제가 맞나요? 네 맞습니다.

왜냐? 위에 보시면 이미 37명이 풀었다고 쓰여있죠? 그럼 풀 수 있는거임 ㅇㅇ 암튼 내 말이 맞음

(사실 저도 풀었습니다 ㅎㅎ)

 

 

 

LCS 알고리즘의 공간복잡도

 

여태까지 쓴 글을 본다면, LCS 알고리즘은 시간복잡도 O(N * M), 공간복잡도 O(N * M)을 필요로 한다고 말했습니다.

그런데, 문제의 "최대 7000글자"를 보면 7000 * 7000 = 49,000,000 = 49M 으로, int가 4바이트를 사용한다고 치면 200MB정도를 필요로 합니다.

 

여기서 4MB라면 결국 O(N)의 공간복잡도로 풀라는 말입니다.

 

한번 풀어봅시다.

 

 

 

 

배열 2개만 가지고 LCS의 길이를 알 수 있을까?

 

사실, LCS를 출력하는 것이 아니라면, LCS의 길이는 배열을 2개만 가지고도 풀 수 있습니다.

 

0번째 행만 가지고, 1번째 행을 계산할 수 있고,

1번째 행만 가지고도, 2번째 행을 계산할 수 있고,

....

5번째 행만 가지고도, 6번째 행을 계산할 수 있습니다.

 

결국, 배열 2개를 번갈아가면서 사용한다면 LCS의 길이는 공간복잡도 O(N) 으로 풀 수 있습니다.

 

 

 

 

 

그렇다면, 3번째 행에서 어느 값이 최종적으로 쓰였는지는 알 수 있을까?

 

백준 LCS2 때 사용한 테이블을 재활용해봅시다.

 

3번째 행의 각각을 서로 다른 색깔로 칠해본다면, 3행에서는 보라색, 즉 3행 5열이 사용되었다는 것을 알 수 있습니다.

2개의 배열만을 사용해야되는 상황에서, 이렇게 특정 열의 어느 값이 사용되는지를 지속적으로 기록하려면 메모리가 얼마나 필요할까요?

2개의 배열을 계속해서 갱신하는 과정에서 색깔을 지속적으로 저장해놓아야 하므로, 색깔을 저장하는 2개의 배열이 추가적으로 필요합니다. (총 4개)

	(0)	C(1)	A(2)	P(3)	C(4)	A(5)	K(6)
(0)	0	0(left)	0(left)	0(left)	0(left)	0(left)	0(left)
A(1)	0(up)	0(up)	1(wow!)	1(left)	1(left)	1(wow!)	1(left)
C(2)	0(up)	1(wow!)	1(up)	1(up)	2(wow!)	2(left)	2(left)
A(3)	0(up)	1(up)	2(wow!)	2(left)	2(up)	3(wow!)	3(left)
Y(4)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	3(left)
K(5)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	4(wow!)
P(6)	0(up)	1(up)	2(up)	3(wow!)	3(left)	3(left)	4(up)

(이 문제에서는, 이처럼 2차원 배열을 사용할 수 없습니다. 다만, 이해를 돕기 위해 사용했습니다.)

 

이렇게 3행에서 어떤 원소가 사용되었는지를 알면 무엇에 도움이 될까요? 나머지 행에서 어떤 원소가 출력되어야하는지를 모르는데 말이죠.

그렇다면, LCS 문제를 다시 풀면 됩니다(???). 3행 5열이 선택되었다는 것은 알기 때문에,

 

- 0행 0열부터 3행 5열까지의 부분 문제를 다시 처음부터 풀고,

- 3행 5열부터 6행 6열까지의 부분 문제를 다시 처음부터 풀면 되겠습니다.

 

	(0)	C(1)	A(2)	P(3)	C(4)	A(5)
(0)	0	0(left)	0(left)	0(left)	0(left)	0(left)
A(1)	0(up)	0(up)	1(wow!)	1(left)	1(left)	1(wow!)
C(2)	0(up)	1(wow!)	1(up)	1(up)	2(wow!)	2(left)
A(3)	0(up)	1(up)	2(wow!)	2(left)	2(up)	3(wow!)

 

	A(5)	K(6)
A(3)	3(wow!)	3(left)
Y(4)	3(up)	3(left)
K(5)	3(up)	4(wow!)
P(6)	3(left)	4(up)

요렇게 말이죠.

 

(나) : 다 구했습니다....

(???) : 다시 해!

(나) : ...ㅠㅠ

 

이런 방법을 쓴다면 우리가 사용하는 배열은 항상 4개(LCS 크기 2개, N번째 행의 색깔 2개)만 사용합니다.

이 배열의 크기도 처음에만 |M| 만큼이고 배열의 크기는 지수적으로 작아지게 됩니다.

결국 공간복잡도 O(N) 만에 풀 수 있게 됐지만, 시간 복잡도는?

 

시간 복잡도도 O(N * M)으로 동일합니다.

만약 길이가 N과 M인 두 문자열의 LCS를 구한다 칩시다. 처음 계산에 시간 O(N * M) 이 들겠죠. 다음에 풀어야 할 부분 문제는 각각의 크기가 어떻게 될까요?

여기서, 우리가 위에서 3행의 색깔을 구한 이유가 있습니다. 행을 반으로 자른다면, 다음에 풀어야 할 부분문제는 각각의 크기가 N / 2, M / 2 인 두 문제가 되기 때문입니다. O(N * M / 2)

그렇다면 시간 복잡도는 O(N * M + N * M / 2 + N * M / 4 + N * M / 8 + ....) = O(N * M * 2) 가 됩니다.

이론적으로 시간이 두배가 걸린다는 소리입니다. 즉, 7000 * 7000 * 2 = 98,000,000 입니다. (아슬아슬하죠?)

 

코드를 보겠습니다.

#Colored by Color Scripter

 

구현이 생각보다 복잡했습니다. 위의 코드를 읽어보시면 좋습니다.

 

solve() 함수를 보시면 count, top, top_mid 라는 변수가 있습니다.

count는 우리가 아는 그 "LCS의 크기"를 말하는 것이고,

top과 top_mid 는 뭘까요?

사실 위의 그림은 정확히는 맞지 않습니다. 제대로 그림을 그리면 다음과 같습니다.

	(0)	C(1)	A(2)	P(3)	C(4)	A(5)	K(6)
(0)	0	0(left)	0(left)	0(left)	0(left)	0(left)	0(left)
A(1)	0(up)	0(up)	1(wow!)	1(left)	1(left)	1(wow!)	1(left)
C(2)	0(up)	1(wow!)	1(up)	1(up)	2(wow!)	2(left)	2(left)
A(3)	0(up)	1(up)	2(wow!)	2(left)	2(up)	3(wow!)	3(left)
Y(4)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	3(left)
K(5)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	4(wow!)
P(6)	0(up)	1(up)	2(up)	3(wow!)	3(left)	3(left)	4(up)

차이가 보이시나요? (초록색이랑 회색이 없습니다)

중간 행에서, left의 경우 자기만의 색을 갖지 않고 왼쪽 색깔을 따라갑니다.

top은 각 행마다 이를 계산하는 것입니다.

그렇게 현재 계산하는 행이 중간 행이 되었을 때만, top_mid는 현재 top의 값들을 저장합니다.

그렇다면 top은 뭘까요? (이유 : 사실은 마지막 행 계산하기 귀찮아서)

 

이를 설명하려면 아래의 그림이 필요합니다.

 

	K(6)
K(5)	4(wow!)
P(6)	4(up)

우리는 5행 6열이 선택될 것이라는 것을 압니다. 5행 6열이 선택되고 나면, 5행 6열 부터 6행 6열까지의 부분문제를 풀어야 되겠죠. 

이 문제의 중간행은 몇번째 행이죠? 5번째 행입니다. 즉, 시작행과 중간행이 같습니다.

이렇게 되면 루프가 무한이 돌아가게 됩니다. 6번째 행에서 무엇이 선택되는지 알지 못하고요.

 

그러면, 행 차이가 2이하이면 건너뛰면 될 거 아니냐? 맞습니다. 사실 0행 0열과 6행 6열이 아니라면 모든 부분문제의 시작과 끝은 이미 정답이 나왔습니다.

제가 top을 사용한 이유가 이겁니다. 마지막 행을 계산하기 귀찮아서.... (죄송합니다)

 

추가 설명을 드리자면, 행 차이가 2이하일 때 건너뛰는 방향으로 코딩을 하게 된다면 문제는 0행 0열과 6행 6열에서 생깁니다. 그런데...

0행에서 무엇이 선택되는 것은 관심이 없습니다. 왜냐? 0행에서는 뽑히지 않습니다!

결국, 6행을 계산하는 것이 문제입니다. 여기서 5행에서 선택되는 원소의 위치(DP[5][j]) 만 계산하고, 6행은 해당 원소의 뒤부터 살피면서(DP[6][j + 1] ~ DP[6][6]) 문자가 같을 때 이 문자만 출력하면 되지만 저는 그냥 top이라는 것을 하나 만들었습니다. (메모리가 남기 때문에, 이렇게 사용해도 되었습니다.)

 

 

끝)

 

 

제가 다시 봐도 설명이 어렵게 되어있네요.... 사실 이 문제는 백준 편집거리(Hard) 문제를 토대로 만든 것입니다.

시간이 된다면 편집거리(Edit Distance) 문제도 보시면 좋을 것 같습니다.

https://www.acmicpc.net/problem/17161

17161번: 편집 거리 (Hard)

편집거리(7620) -> 편집거리(Hard)(17161) -> LCS 5(18438) 순서대로 보셔도 좋습니다.

 

 

다음글

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (F), 백준 18439 LCS6(C++)

LCS(Longest Common Subsequence) 알고리즘 (F), 백준 18439 LCS6(C++)