두찡의 일상

알고리즘을 풀다보면 fft 로 풀리는 문제가 참 많다.왜 이런 변환을 사용하게 됐는지, 어떤 문제에서 사용하면 되는지 알아보기위해 영상을 보면서 정리를 해보자 FFT 란 뭘까?https://www.youtube.com/watch?v=eKSmEPAEr2U 푸리에 변환이란 어떤 신호를 주파수 종류별로 분해하는 방법.기존 신호에, 사인파, 코사인파를 곱한 면적을 더하는 방식으로 해당 주파수가 얼마나 연관이 있는지 알아낸다. 신호가 여러 주파수의 합으로 구성된 경우, 어떤 주파수가 존재하고 어느 비율로 존재하는지 알수 있게됨.사인파와 코사인파의 진폭을 계산할때 오일러 공식을 사용하여, 하나의 지수항으로 계산이 가능실수부는 코사인파의 진폭, 허수부는 사인파의 진폭 그러나 실제로 얻는 신호는, 무한한 연속파가 아니..

아래 블로그를 보고 이해한 내용을 정리합니다. blog.naver.com/kks227/221028710658 접미사 배열(Suffix Array) (수정: 2018-03-03) 시험기간 버프를 맞아서 돌아왔습니다.영영 포스팅할 수 없을 줄 알았던 SA도, 시험기간 앞에선 무력화되... blog.naver.com // [출처] 접미사 배열(Suffix Array) (수정: 2018-03-03)|작성자 라이 #include #include #include using namespace std; const int MAX = 1

기본 풀이가 deque 인 것 같은데 priority queue 두개로 푼게 기-묘 해서 올려봅니다 1. i 로 순회를 한다고 할 때 0 N >> L; priority_queue pq; priority_queue reserved; for ( int i = 0; i > arr[i]; pq.push( -arr[i] ); if ( pq.size() > L ) { reserved.push( -arr[i - L] ); } while ( !reserved.empty() ) { if ( pq.top() == reserved.top() ) { pq.pop(); reserved.pop(); } else { break; } } cout

백준 문제를 go 언어로 풀었는데, 시간초과가 나서 찾아봤다 // 기존코드 for r := 1; r

백준 문제를 풀면서 알게된 Trie 자료구조에 대한 정리 많은 문자열중에서 같은 문자열을 찾을 때 최대길이가 m이라면 n번 시행할때 O(mn)으로 찾을 수 있고, 트라이를 만들 때도 O(mn)으로 만들 수 있게 한다. #include #include #include #include using namespace std; struct Trie { char c; bool end; Trie* next[10]; Trie() { end = false; memset(next, 0, sizeof(next)); } ~Trie() { for (int i = 0; i < 10; i++) { if (next[i]) delete next[i]; } } void insert(string s) { if (s.size() == 0)..

외판원 길찾기 문제에서 비트마스크 개념이 나오는데 그 개념을 몰라서 차라리 비트마스크를 공부해보자 싶었다. 왜 길을 찾는데 비트마스크란 개념을 쓰냐면, 어떤 곳에 방문했는지 탐색할때마다 배열을 만드는건 비효율적이니까 int값만 넘기는데 자릿수마다 어떤 마을에 방문했는지 쓸 수 있는것 이다. (1번째 bit가 1이라면 1번 마을을 방문) 대신 넘기는 자료형의 자릿수보다 크게는 안된다. (32bit int 에서는 32까지 표현 가능) - n번째 비트를 1로 만들기 arr |= (1