[Algorithm] 푸리에 변환(Fourier Transform)
.1차원 데이터에 대한 이산 푸리에 변환 .이산 푸리에 변환(Discrete Fourier Transform, DFT)- 원래 신호처리 분야에서 시간축에 따른 신호의 세기를 분석하기 위해 연구- 이산 함수에 대한 푸리에 변환- 푸리에 변환에 의해 생성된 함수는 복소수 공간에서 정의, 오일러 공식(Euler formula)- 복소지수함수를 삼각함수로 변환할 수 있도록 하는 식 - 실제 푸리의 변환 구현 시 함수 F(u)의 실수부(Re)와 허수부(Im)를 따로 고려하여 계산 - 입력 함수인 F(X)가 복소수 함수일 경우- .이산 푸리에 역변환(Invers Discrete Fourier Transform, IDFT)- 이산 푸리에 변환에 의해 생성된 함수 F(u)는 다시 역변환 과정을 거쳐서 원래의 함수로 변..
[C/C++] C++ PS Coding Tip (~ing)
.입출력 . 입출력 방식 속도- C 표준 입출력 함수 scanf, printf (적은 메모리를 사용하지만 아래 방법보다는 느림) 단, cin보다 대용량의 데이터를 input 할 수 있음 - std::cin, std::cout 사용 시 아래 코드 적용1 ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL) cs이 코드를 적용하지 않으면 입,출력시 사용하는 버퍼를 동기화하는 것인데,이럴 경우 C++ 표준 stream버퍼와 C 표준 stream 버퍼가 병행하여 버퍼를 사용하게 된다.C++, C 로 stream 버퍼를 모두 사용할 수 있지만, 버퍼를 병행하여 사용하기 때문에 속도가 느려지는 현상이 발생하게 된다. 그래서 이 코드로 동기화를 해제해주면서..
#. Problem https://www.acmicpc.net/problem/1904* The copyright in this matter is in BOJ 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, ..
#. Problem https://www.acmicpc.net/problem/1003* The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution plan (select Algorithm, Data structure) 4. Prove the plan (check performance time and usage memory) 5. Carry out the plan 6. Look back on the plan and find a way to improve it #. Solve 1. #. CodeCode 1) ..
#. Problem https://www.acmicpc.net/problem/2748* The copyright in this matter is in BAEKJOON 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. #. Resolution Process 1. Read and under..
#. Problem https://www.acmicpc.net/problem/11725* The copyright in this matter is in BAEKJOON 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. #. Resolution Process 1. Read and understand problem 2. Redefine the problem + abstract 3. Create solution ..
#. Problemhttps://programmers.co.kr/learn/courses/30/lessons/43162* The copyright in this matter is in Programmers 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함..
#. Problemhttps://programmers.co.kr/learn/courses/30/lessons/43165* The copyright in this matter is in Programmers n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. - 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. - 각 숫자는 1 이상 50 이하인 자연수입..