목록FFT (1)
블로그 옮겼습니다
FFT(고속 푸리에 변환) 예제 - Hackerrank) Best spot
https://www.hackerrank.com/contests/w6/challenges/best-spot/problem 우선 FFT 코드는 명우님의 블로그의 코드를 참고했음을 알립니다. http://blog.myungwoo.kr/54 이 문제는 FFT를 모르면 절대 풀 수 없어 보이고, 안다면 단순한 구현문제로 전락해 버린다.우선 naive 하게 생각해 보았을 때 모든 위치에서 답을 계산해 보면 O((RC)^2) 의 시간이 걸린다.R, C가 최대 500 이기 때문에 시간안에 절대 돌 수 없다.FFT를 사용하면 O(RClgRC) 의 시간이 걸리게 되어 시간안에 돌게 된다. 우선 squared difference (x-y)^2 의 식을 풀어보면 x^2 - 2xy + y^2 이라는 것을 알 수가 있다.어차피..
Algorithm/Problem Solving
2017. 7. 28. 13:32