15822번 - Ah-Choo! 서브태스크

모든 사람들은 각자 독특한 재채기 소리를 가지고 있다. 우렁찬 소리부터 귀여운 소리까지 다양한 형태뿐만 아니라 서로 다른 목소리까지 더해져 사람마다 고유한 소리를 가지게 된다.

대학원에서 데이터 사이언스를 공부하고 있는 동이는 재채기 소리를 사용한 사람 구분이 가능한지 궁금해졌다. 졸업이 얼마 남지 않은 동이는 학위 논문을 작성하기 위해 곧바로 실험을 시작하기로 했다.

평소 비슷한 재채기 소리를 내던 지애와 지수가 동이를 위해 실험에 참가해주기로 했다. 두 재채기 소리가 다른 사람의 소리인지 혹은 같은 사람의 소리인지 판단하기 위하여 두 소리의 유사도를 정의해야 한다. 두 소리의 유사도는 DTW(Dynamic Time Wraping) 기법을 사용하여 측정하려고 한다.

소리와 같은 파형 데이터는 시간을 x축으로 가지는 시계열(Time-series) 형태의 데이터로 표현된다. 하지만 같은 사람의 재채기 소리도 매 번 조금씩 다른 형태의 파형을 가질 수 있다. 아래의 예시를 보자.

그림 1. 시간을 기준으로 한 파형의 비교(좌) / DTW를 적용한 파형의 비교(우) 방식 예시 

그림 1의 (a)와 같이 단순히 두 파형을 각 단위 시간 기준으로 비교한다면, 비슷한 파형임에도 불구하고 실제로 유사도가 낮게 계산될 수 있다. 이에 반해 DTW 방식은 (b)와 같이 두 파형의 각 시점이 최대한 유사한 지점들을 대응시킨 후에 유사도를 계산하는 방식을 의미한다. 결과적으로 재채기 속도나 녹음 시점으로 인해 발생하는 오차를 최소화 할 수 있다.

두 소리 X, Y의 각 시점의 파형의 높이를 X(i), Y(j)라고 하자. 이때, 파형 X의 시점 i와 파형 Y의 시험 j에서의 두 파형의 오차는 {X(i)-Y(j)}²와 같이 정의한다. 두 파형의 각 시점은 하나 이상의 상대편 파형의 시점에 대응되어야 하며, 각 대응된 시점간의 오차의 총 합이 두 소리의 거리가 된다. 결과적으로 DTW 기법을 적용해 얻을 수 있는 두 소리의 최소 거리의 역수가 두 소리의 유사도가 된다.

그림 2. 두 소리의 거리가 최소가 되도록 각 시점을 대응시킨 예시

결과적으로 유사도를 계산하기 위하여 두 파형에 대해서 대응되는 시점을 정해야 한다. 각 소리 파형의 각 시점은 하나 이상의 대응되는 시점을 가져야 한다. 단, 두 시점의 대응이 다른 두 시점의 대응과 교차되어서는 안 된다. 예를 들어서 X 파형의 7초 시점과 Y 파형의 6초를 대응했을 때 이후에 X파형의 8초 시점과 Y파형의 5초 시점을 대응시키면 두 대응 관계간의 교차가 발생하므로 올바른 대응이 아니다.

그림 3. 예시 파형의 각 시점을 대응시키는 방법. 

위의 그림처럼 두 개의 파형을 표현하는 수열 X:[10, 20, 45, 20, 14, 15]와 Y:[10, 25, 50, 50, 30, 15]을 예로 들어보자. (a)와 같이 단순히 같은 시점으로 대응시키는 경우 두 소리의 거리가 0+25+25+900+256+0=1206이 되지만, (b)와 같이 대응시키면 0+25+25+25+100+1+0=176이 된다. (c)와 같이 시점의 대응 관계 사이에 교차가 발생하는 경우는 고려하지 않는다.

지애와 지수가 녹음한 재채기 소리들 중 임의의 두 소리 정보가 시간에 대한 수열로서 주어질 때, DTW 기법으로 계산할 수 있는 두 소리 사이의 최소 거리를 계산하는 프로그램을 작성해주자.

입력의 첫 줄에는 파형의 길이를 나타내는 자연수 N이 주어진다. 두 번째 줄에는 첫 파형 X의 시간 별 높이를 나타내는 N개의 정수가 공백으로 구분되어 시간순으로 주어진다. 세 번째 줄에는 두 번째 파형 Y의 시간 별 높이가 같은 형식으로 주어진다.

모든 파형의 높이는 0이상 1,000이하의 정수다.

두 파형의 최소 거리를 정수로 출력한다.

• 1 ≤ N ≤ 10

• 1 ≤ N ≤ 2,000