FFT 알고리즘

 
 

FFT(고속 푸리에 변환) 알고리즘 소개 및 구현

1. FFT(고속 푸리에 변환)란?

고속 푸리에 변환(Fast Fourier Transform, FFT)은 이산 푸리에 변환(DFT)을 빠르게 계산하는 알고리즘입니다. DFT는 시간 영역의 신호를 주파수 영역으로 변환하는 수학적 방법으로, 계산 복잡도가 O(N^2)이기에 큰 데이터셋에 대해 비효율적일 수 있습니다. FFT는 이러한 계산을 O(N log N)으로 줄여줍니다.

2. FFT 알고리즘의 기본 원리

FFT는 DFT를 계산할 때, 입력 신호를 재귀적으로 반으로 나누어 작은 부분들로 나누어 계산하는 방식입니다. 이러한 분할 정복 접근 방식은 중복 계산을 피할 수 있게 해주어 효율성을 극대화합니다.

3. FFT 알고리즘의 구현

이제 FFT 알고리즘의 파이썬 구현 코드를 살펴보겠습니다. 다음 코드는 기본적인 Cooley-Tukey FFT 알고리즘의 예제입니다

백준 1067 - 이동

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

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> cpx;
typedef vector<cpx> vec;
const double pi = acos(-1);

void FFT(vec &f, cpx w){
    int n = f.size();
    if(n == 1) return;

    vec even(n >> 1), odd(n >> 1);
    for(int i = 0; i < n; i++){     // 배열 분할
        if(i & 1) odd[i >> 1] = f[i];
        else even[i >> 1] = f[i];
    }

    FFT(even, w * w);
    FFT(odd, w * w);

    cpx wp(1, 0);
    for(int i = 0; i < (n / 2); i++){   // 배열 재조합
        f[i] = even[i] + wp * odd[i];
        f[i + (n / 2)] = even[i] - wp * odd[i];
        wp *= w;
    }
}

vec mul(vec a, vec b){
    int n = 1;
    while( n <= a.size() || n <= b.size() ) n <<= 1;    // 벡터 크기 조정
    n <<= 1;

    a.resize(n);    // 벡터 초기화
    b.resize(n);
    vec c(n);

    cpx w(cos(2*pi/n), sin(2*pi/n));
    FFT(a, w); FFT(b, w);

    for(int i = 0; i < n; i++) c[i] = a[i] * b[i];

    FFT(c, cpx(1, 0) / w);  // 역 FFT 변환 (주파수 -> 시간)

    for(int i = 0; i < n; i++){
        c[i] /= cpx(n, 0);  // 정규화
        c[i] = cpx(round(c[i].real()), round(c[i].imag())); // 반올림
    }
    return c;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N;
    cin >> N;

    vector<int> A(2*N), B(N);
    for(int i = 0; i < N; i++) cin >> A[i];     // 입력 받기
    for(int i = N-1; i >= 0; i--) cin >> B[i];
    for(int i = 0; i < N; i++) A[i + N] = A[i];

    vec a, b;
    for(auto i : A) a.push_back(cpx(i, 0)); // 벡터 복소수 변환
    for(auto i : B) b.push_back(cpx(i, 0));

    vec c = mul(a, b);  // 합성곱 계산

    long long int mx = 0;
    for(int i = 0; i< c.size(); i++)
        mx = max<long long int>(mx, round(c[i].real()));  // 최댓값 찾기

    cout << mx;
}

백준 15576 - 큰 수 곱셈 (2)

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

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> cpx;
typedef vector<cpx> vec;
const double pi = acos(-1);

string A, B;

void FFT(vec &f, cpx w, bool invert) {
    int n = f.size();
    if (n == 1) return;

    vec even(n >> 1), odd(n >> 1);
    for (int i = 0; i < n; i++) {
        if (i & 1) odd[i >> 1] = f[i];
        else even[i >> 1] = f[i];
    }

    FFT(even, w * w, invert);
    FFT(odd, w * w, invert);

    cpx wp(1, 0);
    for (int i = 0; i < (n / 2); i++) {
        cpx u = even[i], v = wp * odd[i];
        f[i] = u + v;
        f[i + (n / 2)] = u - v;
        if (invert) {
            f[i] /= 2;
            f[i + (n / 2)] /= 2;
        }
        wp *= w;
    }
}

vec mul(vec a, vec b) {
    int n = 1;
    while (n < max(a.size(), b.size())) n <<= 1;
    n <<= 1;

    a.resize(n);
    b.resize(n);
    vec c(n);
    cpx w(cos(2 * pi / n), sin(2 * pi / n));

    FFT(a, w, false);
    FFT(b, w, false);

    for (int i = 0; i < n; i++)
        a[i] *= b[i];

    FFT(a, cpx(1, 0) / w, true);

    for (int i = 0; i < n; i++)
        c[i] = cpx(round(a[i].real()), 0);

    return c;
}

string solve() {
    vec a, b;
    for (int i = A.size() - 1; i >= 0; i--)
        a.push_back(cpx(A[i] - '0', 0));
    for (int i = B.size() - 1; i >= 0; i--)
        b.push_back(cpx(B[i] - '0', 0));

    vec c = mul(a, b);
    vector<int> result(c.size());
    for (int i = 0; i < c.size(); i++)
        result[i] = int(c[i].real() + 0.5);

    for (int i = 0; i < result.size() - 1; i++) {
        result[i + 1] += result[i] / 10;
        result[i] %= 10;
    }

    string ans;
    bool chzero = true;
    for (int i = result.size() - 1; i >= 0; i--) {
        if (chzero && result[i] == 0) continue;
        chzero = false;
        ans += char(result[i] + '0');
    }
    return chzero ? "0" : ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> A >> B;
    cout << solve() << endl;
    return 0;
}

4. 코드 설명

위 두 가지 코드는 각각 이동 문제와 큰 수 곱셈 문제를 FFT 알고리즘을 사용하여 해결하는 예제입니다. 주요한 부분은 다음과 같습니다:

• 벡터를 분할하여 재귀적으로 FFT를 계산합니다.
• 주어진 문제에 맞춰 입력 데이터를 변환하고 FFT를 수행합니다.
• 결과 벡터를 처리하여 최종 값을 계산합니다.

5. 결론

FFT 알고리즘은 많은 분야에서 중요한 도구로 사용되며, 특히 신호 처리와 과학 계산에서 필수적입니다. 이를 통해 우리는 시간 영역의 신호를 주파수 영역으로 효율적으로 변환하여 다양한 분석 및 처리를 할 수 있습니다. 위의 구현 코드를 통해 FFT의 기본 개념을 이해하고 실제 적용해 보시기 바랍니다.