[문제]
7개의 음(pitch)으로만 구성된 악곡이 있다. 예를 들어 중세 그레고리안 성가는 7개의 음, 우리나라와 중국 일본의 민속 음악은 5개의 음으로 구성된 펜타토닉 음계를 사용한다. 음악에서 반복과 변형은 노래를 끌고 나가는 매우 중요한 동력 알고리즘이다. 반복이 너무 없으면 청중은 무료함, 지루함을 느끼지만, 또 너무 같은 상투적인 구조가 변화 없이 반복되면 긴장감이나 새로움이 떨어져 유치해지거나 쉽게 흥미를 잃게 된다. 이 문제에서 입력 음악은 7개의 소문자 {$c,d,e,f,g,a,b$}로 구성된 문자열로 표현된다. 이 문제에서 음의 지속을 나타내는 박자는 일단 무시하기로 한다.
어떤 구절이 반복된다는 것은 어떤 부분 문자열(substring)이 다른 위치에서 비슷한 모양으로 다시 나타난다는 것을 의미한다. 아래 예에서 붉은색으로 표시된 서로 다른 위치의 부분 문자열 (비록 길이는 다르지만) 2개를 alignment를 해보면 아래와 같이 된다. 이 문제에서 우리는 match, mismatch, gap의 점수(score)를 +5, -2, -3으로 계산한다. 단, 이 값은 문제마다 다르게 주어진다. mismatch와 gap의 penalty를 높이면 공백없는 짧은 구간이 더 선호된다. 만일 gap penalty를 극단적으로 올리면 완전히 동일한 substring만 선별될 수 있다.
afffbbgagccfeegeeeddeccggccaceefge
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| g | a | g | c | c | - | f | e | e | - | g | e | |
| g | - | g | c | c | a | c | e | e | f | g | e | |
| $s_i$ | +5 | -3 | +5 | +4 | +4 | -3 | -2 | +5 | +5 | -3 | +5 | +5 |
만일 우리가 반복된 두 구절을 붉은색으로 표시한 gagccfeege, ggccaceefge라고 한다면 이 둘의 alignment score는 5*8+3(-3)+(-2)=29가 된다. 만일 이 값이 가장 큰 값이라고 한다면 위에서 선택한 두 부분서열이 반복서열이라고 할 수 있다. 여러분은 이렇게 주어진 음악에서 이렇게 가장 높은 정렬값(alignment score)를 가지는 2 부분서열(substring), 즉 반복구간을 찾아야 한다. 즉 겹치지 않은 두 부분문자열의 정렬값이 가장 높은 부분은 가장 확실한 반복구간으로 본다. 이 문제에서 고래할 조건은 다음과 같다.
1) 두 부분서열(substring)은 겹칠 수 없다. 예를 들어 입력이 아래와 같을 경우 아래와 같이 겹치도록 선택된 bbbb...b 부분 문자열 substring은 선택될 수 없다.
gcdeffgebbbbbbbbbbbbbfaabcefgaadafegdfdgaaa
----------bbbbbbbbbbbb-----------------------
------------bbbbbbbbbbbb----------------------
2) 만일 같은 alignment score를 가지는 substring 쌍(pair), 즉 반복구절이 하나 이상 존재하면 substring의 시작 위치가 더 빠른 것을 선택해야 한다. 즉, 두 matched substring 중 먼저 나온 substring에서 사전식으로 가장 빠른 것을 선택한다. 그 이후에는 반복되며 나타나는 substring 중 가장 큰 alignment score를 가지면서 제일 먼저 나오는 것을 선택한다. 예를 들어 가장 높은 alignment score를 보여준 3쌍의 부분 문자열의 시작 위치가 각각 (345, 678), (123,789), (123,670)이라고 한다면 (123, 670)에서 시작하는 문자열을 찾아서 출력해야 한다.
[입출력]
입력 파일 music.inp의 첫 줄에는 match. mismatch, gap score 값을 나타내는 3개의 정수가 주어진다. match는 양수, mismatch와 gap은 항상 음수이며 그 절댓값은 10 이하이다. 그다음 줄에는 {$c,d,e,f,g,a,b$} 문자로 구성된 악보가 string $M$으로 들어온다. 단, $20 \leq |M| \leq 1000$ 이다. 출력으로는 가장 높은 alignment score를 보여주는 substring 2개와 그 alignment socre를 순서대로 제시해야 한다. (사전 순으로 빠른 string을 먼저 출력해야 한다). 즉, 먼저 나타난 substring을 첫 줄, 그다음 줄에 반복 aligned string을 제시하고 마지막에 alignment score를 정수로 출력한다.
[실전 예제]
| music.inp |
| 5 –2 –3 //match=+5, mismatch=-2, gap=-3 afffbbgagccfeegeeeddeccggccaceefge |
| music.out |
| gagccfeege ggccaceefge 29 |
[풀이] O($N^3$)
local alignment에 대한 강의를 수업시간에 했으므로 간단하게 설명만 하자면,
두 string의 substring들 중 alignment가 가장 높은 substring을 뽑아내는 알고리즘인데, dp로 구현된다.
dp table은 $dp[i][j] = max(0, dp[i - 1][j] + gap, dp[i][j - 1] + gap, dp[i - 1][j - 1] + (s_1[i] == s_2[j] ? match : mismatch)$이다.
문제는 두 string에 대해서 substring의 local alignment를 구하기 때문에 한 string에 대해서 구해버리면 중복되지 않는 substring을 filter하는게 상당히 까다롭다. 일반 local alignment에서 string을 추적해나가는 과정을 그대로 적용하면서 중복을 제거해줄 수 밖에 없는데, index가 겹치는 순간에 분기를 나누어 처리해줘야한다. 여기서 완전탐색을 해버리면 매우 오래걸리고, 다시 dp를 쓸 수 밖에 없는데, 여기서도 O($n^2$)이 걸리므로 결국 O($n^4$)이다.
그러므로 애초에 dp테이블을 채울 때 중복이 발생하지 않도록 채워주어야한다. 근데, 그런 방법은 존재하지 않는다.
따라서, 한 string을 0~i, i+1~n으로 나누어 dp table을 $n$번 만들어주는 방법 밖에 없다. 즉, O($n^3$)이다.
학교 커뮤니티에 O($n^2$)의 방법이 있다고 증명했다는 사람이 있었으나, 테스트케이스가 빈약해 통과된 것 뿐이고, 코드를 봐도 빈약한 테스트케이스를 회피하는 코드일 뿐이었다.
O($n^2$)으로 풀린다길래 3일 넘게 고민했는데, 아무리 생각해봐도 3d-segmentTree를 쓰는 O($n^2log^2{n}$)의 방법 밖에 생각이 나질 않아서 그냥 O($n^3$)으로 풀었다.
방학시즌이나 여유가 있을 때 3d-segmentTree도 배울 겸 다시 한 번 도전해봐야겠다.
