분류 전체보기110 푸리에 변환(Fourier Transform) 푸리에 변환 푸리에 변환이란 시간에 대한 신호 함수를 주파수에 대한 식으로 변환하는 것을 말한다. 성공적으로 변환을 한다면 노이즈와 여러 주파수가 섞인 신호에서 특정 주파수를 추출해낼 수 있다. 이것 외에도 푸리에 변환의 그 성질을 이용해서 어떤 연산을 더욱 쉽게 풀어쓸 수도 있다. 푸리에 변환의 깊은 뜻 말고 단순히 문제풀면서 겪었던 몇 가지만 적어보면 다음과 같다. convolution 두 수열의 convolution을 구할때 일반적으로 n^2의 연산이 필요로 한다. fourier transform으로 변환 후 convolution을 빠르게 할 수 있다. 큰 수의 곱셈 곱셈은 일반적으로 자리수의 제곱에 해당하는 연산을 필요로 한다. fourier transform으로 변환 후 곱셈을 빠르게 할 수 있.. 2019. 10. 17. 오일러 피 함수(Euler's phi function) Euler's phi function 오일러 피(파이) 함수 $\phi (n)$ 란 1과 n까지의 정수 중 n과 서로소인 개수를 뜻한다. 거부감 없이 정의는 매우 쉽다. int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); } int getEulerPhiFunc(int n){ int cnt = 0; for(int i = 1; i < n; i++){ if(gcd(n, i) == 1) cnt++; } return cnt; } 대충 예외 생각 안 하고 구현하면 위와 같이 구하면 된다. 이 방법은 $ \phi (n) $ 의 성질을 하나도 안 따져보고 구했으니, 더 좋은 방법을 위해 성질을 알아보자. 일단 가장 간단하게 유추할 수 있는 것이 있다. $$ \phi(p).. 2019. 10. 17. 모듈러 나눗셈 Modular 사칙연산만큼 친숙한 모듈러지만 연산은 사칙연산만큼 심플하지는 않다. 정의 자체가 나눗셈을 한 후에 나머지를 가리키는 뜻이니 나눗셈 이상의 매력이 있다. 그럼 한번 사칙연산과 모듈러의 관계를 정리해보자. $$ \begin{align} (a + b)\ \%\ M & = ((a\ \%\ M) + (b\ \%\ M))\ \%\ M \\ (a - b)\ \%\ M & = ((a\ \%\ M) - (b\ \%\ M) + M)\ \%\ M \\ (a \times b)\ \%\ M & = ((a\ \%\ M) \times (b\ \%\ M))\ \%\ M \\ (a\ /\ b)\ \%\ M & = ((a\ \%\ M)\ /\ (b\ \%\ M)\ \%\ M \cdots ? \end{align} $$ 덧셈.. 2019. 10. 17. 이분 매칭 (Bipartite graph) 이분 매칭에 앞서 이분 그래프의 정의부터 알아보자. 이분 그래프란 아래 조건을 만족하는 그래프이다. 노드를 두 그룹으로 나누는데 각 그룹이 간선을 공유하지 않는 그래프 예를 들면 이런 그래프가 있다. 이분 매칭 이분 매칭이란 이분 그래프에서 서로 다른 그룹에 속한 노드를 매칭 할 때, 최대한 많이 매칭 하는 것을 말한다. 이때 하나의 노드는 최대 하나의 간선만 가지도록 구성되어야 한다. 예제 그래프를 가지고 이분 매칭을 하는 방법을 하나씩 살펴보자. 예제 1. 초기 그래프 2. 첫번째 매칭 위 그래프에서 이분 매칭을 하기 위해 먼저 빨간 노드를 차례대로 순회하면서 파란 노드랑 연결시켜주는 작업을 시작한다. 2-1. 첫번째 매칭 후처리 첫 번째 빨간 노드에서 그래프를 순회하다가 매칭 할 수 있는 파란 노드.. 2019. 10. 17. 벡터 외적으로 CCW (Counter ClockWise) 이해하기 기하에서 좌표를 다룰 때 각 점 또는 선분의 상대적인 위치를 구하는 것은 아주 중요하다. 이 작은 연산을 토대로 여러 가지 작업을 할 수 있기 때문인데, 먼저 선분과 점의 상대적인 위치를 구하는 ccw에 대해서 알아보고 이를 어디에 적용할 수 있는지 보자. CCW란 임의의 선분을 기준으로 하나의 점이 시계방향에 있는지, 반시계방향에 있는지 확인하는 수단이다. 그림으로 보면 가운데 선분을 기준으로 위의 점은 반시계 방향, 아래 점은 시계 방향임을 알 수 있다. 그럼 이제 각 선분을 벡터라고 보고 외적의 개념을 떠올려보자. 두 벡터를 외적하면 방향이 두 벡터에 수직이며 크기는 두 벡터를 변으로 갖는 평행사변형의 넓이를 갖는 벡터가 나온다. 첫 번째 그림의 외적 $\vec{a} \times \vec{b}$ 의.. 2019. 10. 17. 스킵 리스트 (skip list) 동작 방법 skip list는 linked list와 비슷하게 다음 원소를 가리키는 포인터를 가지고 있다. 그렇기 때문에 데이터의 삽입/삭제를 빠르게 할 수 있다. 이것은 linked list 특성상 당연해 보이는데 skip list는 여기에 검색 속도까지 책임진다. linked list부터 시작해서 어떤 방법으로 검색 속도를 향상시키는지, 부작용은 없는지 확인해보자. 시간 복잡도 $O(n)$ 공간 복잡도 $O(n)$ linked list를 먼저 그려보면 위와 같다. 삽입/삭제는 앞, 뒤 노드만 수정하면 되기 때문에 빠르게 할 수 있지만 역시 검색이 문제다. 다음 원소를 가리키는 포인터만 따라가서는 당연히 속도가 좋지 않기 때문인데, 포인터를 여러 개 두는 방향으로 이를 개선한다. 그러면 다음 원소뿐만 아니라 그다.. 2019. 10. 17. 이전 1 ··· 14 15 16 17 18 19 다음
