백준 #1067 이동(FFT)

이번 문제는 Platinum II 난이도 문제입니다.

 

이 문제를 풀기 위해서는 길쌈 코드(Convolution Code)에 대한 이해가 필요합니다.  길쌈 코드는 크게 순환하지 않는 코드와 순환하는 코드가 있습니다.  이 문제에서는 순환하는 코드와 관련된 문제입니다.  길쌈 코드는 통신에서 많이 사용되기는 하지만, 보통 시스템을 이해하는데 있어서 중요한 개념 중 하나입니다.

 

N개의 수를 가지고 있는 두개의 수열 X, Y가 있습니다.  이 수열을 순환하는 길쌈 코드로 만들 때, 가장 큰 값을 찾아야 합니다.

 

길쌈 코드라는 것은 무엇인가를 알아야 합니다.  두개의 수열 { 1, 3, 2, 4 } 와 { 1, 2, 3, 4 } 가 있다고 해보죠.  이 두 수열을 길쌈 코드로 작성하면 다음과 같이 됩니다.

 

Acyclic Convolution Code

 

두개의 수열을 순환하지 않는 길쌈 코드로 작성하면 위의 그림과 같이 됩니다.  첫번째 수열을 고정시켜놓고, 두번째 수열을 역순으로 하나씩 맞추어 갑니다.  위와 같이 첫번째 자리끼리 곱해서 1을 얻고, 그 다음은 첫번째 자리와 두번째 수열의 두번째 자리와 곱하고, 두번째 자리와 두번째 수열의 첫번째 자리와 곱한 것을 합해서 5를 얻습니다.  사실 길쌈 코드는 우리가 곱셈을 하는 것과 크게 다르지 않습니다.  4231 곱하기 4321을 하는 과정과 같습니다.  1의 자리는 1x1 이 되어서 1이 되고, 10의 자리는 1x2+3x1 = 5 를 얻습니다.  그래서 결론적으로 위의 계산을 하면 21000 + 1100 + 50 + 1 형태로 아래에 있는 4자리 숫자를 맞출 수 있습니다.  길쌈 코드는 길이 4짜리 두개의 수열을 계산하면 총 7개의 숫자가 나옵니다.  이 숫자는 방금 이야기한 것처럭 두 숫자를 곱하는 것과 동일한 결과를 내게 됩니다.

 

이 문제를 풀기 위해서 우리는 고속 푸리에 변환(Fast Fourier Transform)을 이용하새 풀게 됩니다.  수열의 숫자가 꽤 크고, 수열의 숫자가 많다면, 반올림 에러가 발생해서 정확한 값을 낼 수 없지만, 본 문제처럼 100이하의 숫자에 6만개정도의 데이터라면, 정밀도가 아슬아슬하게 감당이 될거라 봅니다.  더블형을 쓰니까, 대략 몇백억단위 이상까지는 정밀도가 보장될테니까요.  최대 숫자는 6백만에 곱하기가 들어가니까, 36조정도가 나옵니다.  이정도면, 특이 데이터에서는 반올림 에러가 나올 가능성도 있어보입니다만.

 

고속 푸리에 변환을 사용하면, FFT 연산과 iFFT 연산시에 \(O(N \log N)\)이니까, FFT 연산과 순환연산을 위해서 데이터 갯수를 2배 이상 높이더라도, 기본적인 컨볼루션 연산을 하는 \(O(N^2)\) 보다 성능이 좋게 나옵니다.  안 그러면 데이터 갯수 6만개이므로 시간초과가 발생합니다.

 

FFT로 순환하는 길쌈 코드를 만드는 방법은 다음과 같이 하면 됩니다.

 

\[ X(z) = FFT(x(k)), Y(z) = FFT(y(k)) \]

\[ Z(z) = X(z) \cdot Y(z) \]

\[ z(k) = iFFT(Z(z)) \]

 

제 소스의 경우에는 채점 결과가 52ms 나왔습니다.  그런데 16ms 나온 분들도 계시네요.  FFT 알고리즘 개선이 필요한 것인지.  일단 FFT 소스는 다른 곳에서 가져온 것을 사용했습니다.  그 외에는 위의 공식에서 크게 벗어나는 것은 없습니다.

 

제가 사용한 FFT 소스를 첨부합니다.  사실 FFT 소스가 가장 중요하고, 그 외에는 간단한 구현입니다.

//----------------------------------------------------------
//  baekjoon #1067 - Moving
//    - by Aubrey Choi
//    - created at 2020-02-13
//----------------------------------------------------------
#include <stdio.h>
#include <complex>
#define  MAX  (1<<17)

std::complex<double> ca[MAX], cb[MAX];
void fft(std::complex<double> a[], int n, bool inv)
{
  int i, j, k, bit;
  for(i=1,j=0;i<n;i++) 
  {
    for(bit=n>>1;!((j^=bit)&bit);bit>>=1);
    if(i<j) swap(a[i], a[j]);
  }
  for(i=1;i<n;i<<=1) 
  {
    double x = (inv ? 1 : -1) * M_PI / i;
    std::complex<double> w={cos(x),sin(x)}, th, tmp;
    for(j=0;j<n;j+=i<<1) for(k=0,th=1;k<i;k++)
    {
      tmp = a[i+j+k]*th;
      a[i+j+k] = a[j+k]-tmp;
      a[j+k] += tmp;
      th *= w;
    }
  }
  if(inv) for(i=0;i<n;i++) a[i]/=n;
}