반응형 알고리즘 풀이/알고리즘 개념2 [알고리즘] 고속 푸리에 변환(FTT) 알고리즘 정리 (python) ※ 시작하기 전 내가 찾는 고속 푸리에 변환(FTT)은 알고리즘 문제 풀이를 해결하기 위한 FTT인데, 찾아보는 자료마다 이것 저것 푸리에 변환에 대한 공식이 적혀있고, Numpy를 이용해서 FTT 그래프를 그리고 해석하는 등 데이터 분석에 필요한 FTT 구현을 위주로 설명이 되어 있었다. 그런 FTT 그래프 구현 등은 다른 블로그 등에서 매우 잘 다룬 자료들이 많으므로 다루지 않을 거고, 내가 다룰 내용은 FTT 알고리즘을 구현하여 문제를 풀 수 있도록 (백준 등) 고속 푸리에 변환 (FTT)과 고속 푸리에 역변환 (IFTT)를 내용으로 작성함 (코드 첨부) 고속 푸리에 변환(FTT) 📌고속 푸리에 변환? 고속 푸리에 변환(FTT)란 이산 푸리에 변환(DFT)을 빠르게 진행하기 위해 만들어낸 알고리즘 .. 2023. 4. 30. [알고리즘] Manacher 알고리즘 정리 (python) Manacher 알고리즘 회문(Palidnrome)에 관한 문제를 빠르게 풀 수 있도록 만들어주는 알고리즘 문자열 S의 부분 문자열 중에서 팰린드롬인 것 중 가장 긴 것의 길이를 구하는 알고리즘을 해결하는 것에 최적화. 시간 복잡도 : O(n) 적용 방법 문자열 S에 대해 새로운 배열 A를 정의 배열 A의 i번째 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기 Banana를 예시로 들면, S[3]인 문자 a는 자신을 기준으로 an(a)na으로 최대 2의 반지름을 가지므로, A[3] = 2 위 방법으로 배열 A을 구성하면 [0, 0, 1, 2, 1, 0]의 값을 얻을 수 있음 문제점 어떤 위치(인덱스)를 중심으로 고려하기에 짝수가 아닌 홀수의 회문만 구할 수 있음 구한 결과가 회문의 한.. 2023. 4. 16. 이전 1 다음 반응형
