https://speakerdeck.com/wookayin/fast-fourier-transform-algorithmhttp://cubelover.tistory.com/12 내가 개념을 설명하기에는 위의 링크로도 충분한 것 같아서 따로 설명을 하지는 않겠다. 특히 맨 처음 인용한 ppt 슬라이드가 엄청나게 이해하기가 쉬우니 보면서 따라가는 것이 좋을 것이다. 다만 생각의 흐름 정도를 정리하자면 * 다항식을 표현하는 데 있어서는 sigma(ai * x^i) 형태의 coefficient representation과, {(x1, f(x1)), (x2, f(x2)), .. (xn, f(xn))} 형태의 point-value representation이 있다. lagrange interpolation theore..
https://www.acmicpc.net/problem/3419격자 그래프가 주어질 때, 갔던 정점을 다시 들리지 않는 조건으로 First와 Second가 번갈아 움직인다. 움직일 수 없는 사람이 질 때, 각각의 정점을 시작점으로 했을 때, 각각의 정점에서 누가 이기는지를 출력하면 된다.격자 그래프는 이분 그래프다. 정점을 두 집합으로 쪼개서, 현재 정점이 속한 집합을 A, 반대 집합을 B라고 하자. 이 문제의 답은 이분 그래프의 최대 매칭과 관련이 있다.설명을 돕기 위해, 먼저 매칭 크기 == |A| 인 경우를 생각해 보자. 이 때는 First가 A에서 매칭된 B의 정점으로만 움직여주면, 항상 이길 수 있다. B가 어떻게 움직이든간에, A 집합에 있는 정점으로 다시 가게 될 것이고, 그 정점은 매칭에..
- Total
- Today
- Yesterday