LCS(Longest Common Subsequence) 알고리즘 (F), 백준 18439 LCS6(C++)
이전 글
2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (E), 백준 18438 LCS5(C++)
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) 이전 글 2020/07/10 - [공부] - LCS..
rhtkdwls.tistory.com
에 이어서,
백준 18439 - "LCS 6"를 풀어봅시다.
https://www.acmicpc.net/problem/18439
18439번: LCS 6
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
이 문제는 루비 문제입니다. 말 다했죠? 9251 - "LCS" 문제에서 메모리와, 문자열의 길이가 달라졌습니다.
문자열의 길이는 최대 50000이고, 메모리는 8MB 가 주어졌습니다.
LCS 5 문제도 문자열 길이가 17000이었는데, 3배가 늘어났습니다. 다행히도 LCS 길이만 출력하면 됩니다.
이전 글의 LCS 5 문제를 다루면서, LCS 길이만을 원한다면 배열 2개만 가지고도 풀 수 있다는 것을 말했었습니다.
그렇게 된다면 문제의 8MB는 충분합니다.
하지만, 이제는 시간복잡도가 말썽입니다. O(N * M)이라면 50000 * 50000 = 2,500,000,000 으로, 1초의 시간제한 안에 풀 수가 없습니다.
50000개 짜리의 문자열을 가지고 어떻게 1초 안에 풀 수 있을까요?
(CPU한테 후딱 해달라고 말하면 됩니다. 그럼 후딱 해줌 ㄹㅇㅋㅋ)
먼저, http://users.monash.edu/~lloyd/tildeStrings/Alignment/86.IPL.html 을 보고 배웠음을 알립니다.
비트연산을 이용한 LCS 알고리즘
방법이 있습니다. 컴퓨터가 처리하는 word의 길이만큼 시간을 줄여주는 알고리즘이 있습니다.
32bit라면 O(n) / 32
64bit라면 O(n) / 64
만큼 줄여줍니다.(말이 그렇다는 것이지 실제로 그렇지는 않습니다.)
이를 설명하기 위해서는 LCS 테이블의 특징을 알아야 합니다.
이전 LCS에서 사용한 테이블을 또다시 재활용해보겠습니다.
| 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 |
각 행의 값들을 보면,
1행 : 0011111
2행 : 0111222
3행 : 0122233
4행 : 0122233
5행 : 0122234
6행 : 0123334
입니다. 무엇이 보이시나요? (보여요! 숫자가!)
1. 각 행의 값들은 인덱스가 커질수록 값이 커진다. 즉, 증가수열을 띈다
2. 마지막 열의 값이 n이라면, 해당 행에는 0부터 n까지의 모든 값들이 존재한다. 즉, 012235 와 같은 행은 존재하지 않는다.
엄밀한 증명은 아니지만 개략적으로 설명해보겠습니다.
1번을 설명하자면, A[i] != B[j] 인 경우는 애초에 max(DP[i - 1][j], DP[i][j - 1])을 계산하니, 값이 커지는 방향인 것은 어찌보면 당연합니다. A[i] = B[j] 인 경우는, DP[i - 1][j - 1]에 1을 더한 값이기에, 값이 커지는 방향인 것입니다.
2번을 설명하자면, 값이 A[i][j]에서 A[i][j + 1]으로 한번에 2만큼 커지려면 A[i - 1][j] 의 값은 A[i][j + 1]의 값과 같거나, 1이 작아야 합니다. 그렇게 되면 A[i][j]도 A[i][j + 1]의 값과 같거나 1이 작아야겠습니다.
그렇다면, 이제 모든 행을 다음과 같이 표현해봅시다.
증가 수열에서, 같은 값을 가지는 부분을 Segment라고 부르겠습니다.
Segment에서, 가장 첫번째 인덱스를 Head라고 부르겠습니다.
Segment에서, Head가 아닌 부분을 Tail이라고 부르겠습니다.
이제 위의 행을 가지고 다음의 행을 만들어 보겠습니다.
X 표시된 곳은 다음 i번째 행에서 A[i] = B[j] 인 인덱스를 표시한 것입니다.
만약, X표시가 Head 위에 있다면, 아무 일도 일어나지 않습니다. 즉, 값이 변하지 않습니다.
0의 Head 위에는 X표시가 생길 수 없고, 나머지 Head에서는 X표시가 없어도 값의 증가가 일어나기 때문입니다.
만약, X표시가 Tail 위에 있다면, 두 가지 경우로 나누어 볼 수 있습니다.
현재 Segment의 Tail 중, 가장 앞(인덱스 값이 가장 작은)에 위치한 Tail(다시 말해서, Leftmost Tail)인 경우, 값이 증가합니다! 실제로도 LCS 알고리즘에서 LCS 길이가 증가하는 부분은 이 부분들입니다.
현재 Segment의 Leftmost Tail 이 아닌 경우, 이미 Leftmost Tail에서 값이 증가했기 때문에, 아무 일도 일어나지 않습니다.
결론, A[i] = B[j] 인 인덱스에서, Leftmost Tail 만 유의해서 보면 된다!
이제, 위의 표를 다시 표현해봅시다.
| C | A | P | C | A | K | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| C | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| A | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| Y | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| K | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| P | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
이제, 각 Segment의 Head만 표시해줄 겁니다. 이렇게 표기해도 위 표가 가진 정보의 양은 같습니다.
결국, 각 행에서 1의 갯수가 현재 행의 LCS 길이를 나타냅니다.
그렇다면, 행(i) 가 주어졌을 때, 행(i + 1)은 어떻게 계산하면 되나요?
앞서 말했듯이, Leftmost Tail 만 유의해서 보면 됩니다!
우리가 할 일은, 각각의 Segment에서, Leftmost Tail 가 존재한다면, 현재 Head의 위치를 Leftmost Tail로 옮겨줄 겁니다.
자 이제, 우리는 위의 표를 "거꾸로" 봅니다. (레드.... 썬)
기존의 왼쪽에서 오른쪽으로 증가하는 수열을 반대로 적어 놓았습니다.
1행 : 1111100
2행 : 2221110
3행 : 3322210
4행 : 3322210
5행 : 4322210
6행 : 4333210
여기서,
각 Segment의 Head만 1로 표현해보면, 다음과 같습니다.
1행 : 00001 00
2행 : 001 001 0
3행 : 01 001 1 0
4행 : 01 001 1 0
5행 : 1 1 001 1 0
6행 : 1 001 1 1 0
그리고, 위에서 빨간색 X 표시한 위치들도 Bit형태로 표현해보면 다음과 같습니다.
1행(C) : 010000
2행(A) : 101000
3행(P) : 000001
4행(C) : 010000
5행(A) : 101000
6행(K) : 000010
이렇게 표현하는 것이 이해가 간다면 이제 본격적으로 시작해봅시다.
만약, i - 1번째 row의 bit가 (row_i-1라고 지칭하겠음)
1000000 1000 1 1 1 1 1
이고, i번째 row의 빨간색 X의 bit가(T라고 지칭하겠음)
0101100 0100 0 1 1 0 0
이라면, row_i 번째 bit는 어떻게 만들까요?
각 segment의 leftmost tail만을 유의해서 보면 된다고 위에서 말했죠? 따라서,
row_i : 0000100 0100 1 1 1 1 1 이 되고, 정리하면
row_i : 00001 0001 001 1 1 1 1 이 됩니다.
그렇다면, row_i를 어떻게 만들까요? 그것은 아래와 같이 구하면 됩니다.
X라는 새로운 BIT를
" X = row_i-1 | T "
라고 정의해보겠습니다. 그렇다면,
row_i = x & ((x - (row_i-1 << 1)) != x)
가 됩니다.
갑자기 급전개해서 죄송합니다. 다만, 이 방법은 설명하기가 까다로워서 독자분들이 손으로 각 연산을 해가면서 이해하셨으면 좋겠습니다.
이렇게, 우리는 row_i-1을 가지고 row_i를 얻어내는 방법을 알아냈습니다. T는 O(N) 만에 전처리를 통해 만들어놓으면 됩니다. 각 Alphabet마다 해당하는 T를 만들어 현재 row에 맞는 alphabet을 가지고 오면 되겠습니다.
++앞으로는, 제 소스코드를 올리지 않습니다. 백준의 복붙 문제가 있어서 그렇습니다. 양해바랍니다.
끝!!!)
출처 : (Bit-String LCS Algorithm) http://users.monash.edu/~lloyd/tildeStrings/Alignment/86.IPL.html
출처 : (Hunt-Szymanski LCS Algorithm) https://imada.sdu.dk/~rolf/Edu/DM823/E16/HuntSzymanski.pdf