본문 바로가기
반응형

컴퓨터 사이언스65

DFT 공부하다가 궁금했던 점 정리 Q. FFT size와 Window size의 차이는 무엇인가? FFT size는 실제로 DFT를 할 때 수식에서 N에 해당하는 값이다. DFT를 수행할 sample의 size와 같을 필요는 없고, DFT를 할 때 시간 복잡도를 줄이기 위해 2의 지수승으로 가급적 택한다. 실제 sample의 size보다 더 크다면 나머지 값을 0으로 패딩한다.(zero padding) Window size는 sample에서 어떤 부분에 DFT를 돌릴지와 관련이 있어서 sample 전체를 돌리고 싶다면 sample size로 지정하면 된다. Q. zero padding을 하면 좋은 점은 무엇인가? zero padding을 하면 기본적으로 DFT에서 N이 늘어나는 효과(sample의 개수가 증가)를 볼 수 있다. 그렇게 되.. 2020. 4. 13.
[c++] 백준 #16490 외계인의 침투 나는 이런 문제 푸는 걸 좋아한다. 물론 기하학을 잘하진 않는다. A를 (0, 0)으로 두자. 우리는 선분AB의 길이(t)를 알고 있으므로 이를 통해 외접원의 반지름을 구할 수 있다. 왜냐하면 삼각형이 정삼각형이므로 정삼각형의 무게중심과 원의 중심이 같기 때문이다. 이를 통해 원의 방정식을 세울 수 있고, 선분 AP의 길이 a를 알고 있으므로 두 식을 연립하면 P의 좌표를 구할 수 있다. B와 C는 정삼각형의 꼭짓점이므로 좌표를 쉽게 구할 수 있고 이를 통해 그냥 수학 식을 코딩으로 변환만 해주면 된다. - 다른 풀이 방법 점 P는 항상 점 B와 점 C 사이에 있을 것이므로 이분탐색을 하면서 점 P의 좌표를 구해도 된다고 한다. #include using namespace .. 2019. 11. 5.
[c++] 백준 #5000 빵정렬 정렬을 할 때마다 규칙성을 찾아야 하는 게 문제인데 나는 그걸 못 찾아서 친구의 풀이를 듣고 깨달음을 얻었다. 정렬을 할 때마다 역순 pair의 홀짝성이 유지가 된다는 것이 특징. 예를 들어 (4, 3, 2)는 (4, 3), (3, 2), (4, 2) 총 3개의 역순 pair를 가진다. 이를 빵정렬하면 (2, 4, 3)이 되는데 이거는 역순 pair를 (4, 3) 하나만 가진다. 그러면 역순 pair의 수가 홀수인 순열은 아무리 빵정렬을 해도 역순 pair의 수가 홀수개이다. 역순 pair 수가 짝수개가 죽어도 될 수 없다는 의미. 그러므로 주어진 두 input의 역순 pair 수를 세보고 둘다 짝수거나 둘다 홀수면 Possible, 아니면 Impossible을 띄우면 된다. 역순 pair를.. 2019. 11. 5.
[알고리즘 공부] 디닉 알고리즘(Dinic's Algorithm) Max flow를 구하는 데 있어, PS에서 쓸 수 있는 알고리즘 중 가장 빠르다고 한다. O(V^2 * E)의 시간복잡도를 가진다. 설명은 아래에. 1. BFS로 유랑이 남은 간선을 기준으로 src에서 dst 노드까지 최단 거리를 구한다.(이를 level graph라고 함) --> BFS라서 O(E)에 가능하다. 선형 시간! 2. DFS로 level graph에서 blocking flow를 흘려주면서 더 이상 못 보낼 때까지 반복한다. --> 생각하기 좀 어려웠는데 한 번 flow를 흘려줄 때마다 bottleneck은 막혀버리니까 최소한 edge하나는 막혀버림. 그리고 edge가 막힐 때 dead end(가다가 막혀버리는 vertex)를 최대 V번 만날 수 있으므로, 많아야 VE번 증가경로.. 2019. 10. 15.
반응형

티스토리툴바