The Story of Joon

BOJ 11066 - 파일 합치기 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 이 문제는 2015년 ACM-ICPC 예선에 나왔던 문제로, DP 테이블을 정의하면 \(O(K^3)\)의 시간복잡도로 어렵지 않게 풀리는 문제다. 난이도는 solv..

Link/Cut Tree (1) 앞선 포스트에서 LCT에 대한 기본적인 내용을 다루었는데, 이번 포스트에서는 LCT가 어떻게 활용될 수 있는지 간단하게만 알아보려고 한다. 보충 자료 같은 느낌의 포스트이다. 1. Link 연산의 확장 원래의 Link 연산은 붙이는 쪽이 represented tree의 루트인 경우에만 가능했다. 그러나 실제로 루트가 아닌 노드를 붙이고 싶을 때도 있을 것이다. 이를 위해서는 represented tree의 루트를 변경하는 작업이 필요하다. 어떤 represented tree의 한 노드를 $v$라고 했을 때, access($v$)를 하면 v에서 루트로 연결되는 preferred path가 생긴다는 점은 이전 포스트에서 알아보았다. 그런데 여기서 주목할 점은 이 preferr..

고속 푸리에 변환(Fast Fourier Transform, FFT)은 convolution을 $O(N\log N)$에 구할 때 활용된다. 이 포스트에서는 코드 자체보다도 FFT 알고리즘의 원리를 알아보는 것이 목적이다. 코드만 보고싶다면 맨 아래로 내려가면 된다. 푸리에 변환은 수학에서 매우 중요한 개념이며 공학 분야에서도 중요하게 다루어진다. 일반적으로 푸리에 변환은 함수를 함수로 보내는 변환인데, PS에서 활용되는 푸리에 변환은 수열을 수열로 보내는 이산 푸리에 변환(Discrete Fourier Transform, DFT)이다. 주기가 $N$인 수열 $\lbrace a_j\rbrace_{j=0}^{N-1}$의 DFT $\lbrace A_n\rbrace_{n=0}^{N-1}$은 다음과 같이 정의된다..