글 읽기 - (C++) typedef 선언 방식의 차이

wlgur1023 2년 전 0

79번째 줄: cpx w = cpx( ( cos(2*PI/n), sin(2*PI/n) ) );

81번째 줄: cpx w( cos(2*PI/n), sin(2*PI/n) );

똑같은 선언이라 생각했는데 79번째 줄을 이용한 풀이는 오답을 내고, 81번째 줄을 이용한 풀이는 정답을 냅니다.

반면, w의 역수를 구하는 과정에서는

82번째 줄: cpx inv_w = cpx(1, 0)/w;

83번째 줄: cpx inv_w( cos(2*PI/n), -sin( 2*PI/n) );

이 둘 다 같은 답을 냅니다.

79, 81번째 줄의 선언 방식에 차이가 있다면 82, 83번째 줄의 선언 방식에도 차이가 있어야 할 것 같은데

왜 82, 83번째 줄은 차이가 없을까요?

또, 79, 81번째 줄은 왜 차이를 보이는 것일까요?

79, 81번째 줄에서 도대체 무슨 차이가 있는지 궁금합니다.

/*
* https://m.blog.naver.com/kks227/221633584963
*/

#include <iostream>
#include <vector>
#include <complex>
#include <math.h>
#include <algorithm>

using namespace std;
const double PI = acos(-1);
typedef complex <long double> cpx;

int size_N;
vector<cpx> X, Y;

void Input(){
    cin >> size_N;
    X.resize(size_N*2);
    Y.resize(size_N*2);

    for(int i = 0; i < size_N; ++i)
        cin >> X[i];

    for(int i = size_N-1; i >= 0; --i)
        cin >> Y[i];

    // X = [X0, X1, X2, X3, X0, X1, X2, X3]
    // Y = [Y3, Y2, Y1, Y0,  0,  0,  0,  0]
    copy(X.begin(), X.begin()+size_N, X.begin()+size_N);
}

// n-1차 다항식 f를 n개의 복소수로 DFT함. 이때 x = w
void FFT(vector<cpx> &f, cpx w){
    int n = f.size();
    if (n == 1) return; // base case

    // 다항식 분리
    vector <cpx> even(n/2), odd(n/2);
    for(int i = 0; i < n; ++i)
        (i%2 ? odd : even)[i/2] = f[i];

    // divide: 각각의 다항식을 재귀적으로 DFT함
    FFT(even, w*w);
    FFT(odd, w*w);

    // conquer: 재귀적으로 알아온 DFT 값들로 이번 함수의 결과를 계산
    cpx w_k(1, 0);
    for (int wk = 0; wk < n/2; ++wk){
        // f(x) = f_even(x^2) + x * f_odd(x^2)
        f[wk] = even[wk] + w_k*odd[wk];
        // f(-x) = f_even(x^2) - x * f_odd(x^2)
        f[wk + n/2] = even[wk] - w_k*odd[wk];
        // w_k = w^k. w_k = w_1^k for the first time
        w_k *= w;
    }
}

void invFFT(vector<cpx> &f, cpx inv_w){
    int n = f.size();
    FFT(f, inv_w);
    for(int i = 0; i < n; ++i){
        f[i] /= cpx(n, 0);
        // 원래 다항식의 계수가 전부 정수일 때만 사용
        f[i] = cpx( round(f[i].real()), round(f[i].imag()) );
    }
}

vector<cpx> convolution(vector<cpx> &X, vector<cpx> &Y){
    vector<cpx> Z;
    int n = 1;
    while(n <= X.size() || n <= Y.size()) n *= 2;
    n *= 2;
    X.resize(n);
    Y.resize(n);
    Z.resize(n);

    // cpx w = cpx( ( cos(2*PI/n), sin(2*PI/n) ) );
    // don't use this form...!
    cpx w(cos(2 * PI / n), sin(2 * PI / n));
    cpx inv_w = cpx(1, 0)/w;
    // cpx inv_w(cos(2 * PI / n), -sin(2 * PI / n));

    FFT(X, w);
    FFT(Y, w);

    for(int i = 0; i < n; ++i)
        Z[i] = X[i]*Y[i];
    
    invFFT(Z, inv_w);

    return Z;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    Input();
    // Print(X, Y);
    vector<cpx> Z = convolution(X, Y);
    
    long long MAX = 0;
    for(int i = size_N - 1; i < 2*size_N - 1; ++i)
        MAX = max(MAX, (long long)Z[i].real());

    cout << MAX;
    return 0;
}

bupjae 2년 전 1

79번째 줄은 괄호를 하나 더 쓰는 바람에 의미가 달라졌습니다.

이렇게 되면 , 는 parameter 구분자가 아니라 comma 연산자를 의미하며

첫 번째 식을 계산하고, 계산한 결과를 버리고, 두 번째 식을 계산하라는 의미가 됩니다.

// 잘못된 코드
cpx w = cpx( ( cos(2*PI/n), sin(2*PI/n) ) );
// cos(2*PI/n) 의 계산 결과는 버려지고, cpx w = cpx(sin(2*PI/n)); 만 남음
    
// 올바른 코드
cpx w = cpx(cos(2*PI/n), sin(2*PI/n));

wlgur1023 2년 전 0

정말 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(C++) typedef 선언 방식의 차이

wlgur1023 2년 전 0

bupjae 2년 전 1

wlgur1023 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말