-
Suffix Automaton 구현과 그 응용
목차 1. 개요 2. 구현 3. 응용 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 이번 포스트에서 살짝 양심고백을 한다면, 원리를 100% 이해하지 못하고 그 구현과 구현체만을 응용하는 것을 다루는 것을 리뷰하려고 합니다. Suffix Automaton의 구현과 동작이 모두 $O(N)$에 이루어지기 때문에 그 효율성 때문에 사용만 가능하다면 매우 유용할 것 입니다. Suffix Automaton의 원리를 전부 이해하고 구현한다면 참 좋겠지만, 아직 몇가지 소정리에 대해서 더 공부해야 이해가 제대로 될 것 같아서 구현방법만 집중적으로 설명하고, 응용에...
-
Linear Feedback Shift Register
안녕하세요, 이번 글에서는 Linear Feedback Shift Register에 대해 알아보도록 하겠습니다. Linear Feedback Shift Register Linear Feedback Shift Register(a.k.a LFSR)는 현재 상태에서의 선형 연산을 통해 다음 상태를 생성하는 레지스터입니다. 예를 들어 상태는 4비트이고 다음 입력값은 1-indexed 기준 4번째 비트와 3번째 비트의 XOR으로 생성된다고 해봅시다. 만약 현재 상태가 1011일 경우 $1 \oplus 1 = 0$이기에 다음 입력값은 0이고, 다음 상태는 0101이 됩니다. 그 다음 입력값은 $0 \oplus 1 = 1$이고, 다음 상태는 1010입니다. 아래의 그림을 참고해보세요. 4번째...
-
AtCoder Grand Contest D Median Pyramid Hard 풀이
문제 요약 문제 링크 $N$층의 피라미드가 있다. $i$번째 층에는 $2i - 1$개의 칸이 있다. 피라미드의 $N$층에 $1, 2, \cdots, 2N-1$을 적절히 섞은 순열이 쓰여 있다. $1$층 부터 $N-1$층 까지의 칸에 숫자를 채우는 규칙은, 그 칸에 있는 수가 그 칸 아래쪽에 있는 $3$개의 수의 중앙값이라는 것이다. 위 방법에 따라 피라미드를 채웠을 때, $1$층에 있는 칸에 쓰인 숫자를 구해라. $ 2 \le N \le 10^5 $ 풀이 1. $O(N^2)$ 규칙에 맞춰서 모든 칸의 값을 구해본다. 공간복잡도가 $O(N^2)$라고...
-
WAVENET: A GENERATIVE MODEL FOR RAW AUDIO
소개 2016년 구글 딥마인드에서 오디오 생성 모델인 wavenet에 관한 논문을 공개했습니다. 이 당시 대부분의 TTS 모델은 녹음된 음성 데이터를 쪼개고 조합해서 음성을 생성하는 방식인 Concatenative TTS를 기반으로 구현되었습니다. 이 방식은 기본적으로 많은 양의 데이터를 필요로 했고, 화자나 톤을 바꾸는 등의 변형을 할 때마다 새로운 데이터가 필요했습니다. 이에 따른 대안으로 통계적인 방법으로 음성을 생성하는 parametric TTS 방식이 주목받았지만 Concatenative TTS에 비해서 생성된 음성이 덜 자연스러웠습니다. wavenet은 기존의 방식과 다르게 오디오의 파형을 직접 모델링하여 훨씬 자연스러운 음성를...
-
Soft Actor-Critic
Goals 본 논문은 “Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor” 논문의 확장판으로, continuous action space 환경에서 동작하는 off-policy 알고리즘인 SAC를 소개합니다. 주된 목표는 다음과 같습니다. Off-policy 알고리즘을 통한 sample inefficiency 해결 On-policy 알고리즘의 경우 업데이트에 쓰이는 데이터가 항상 현재 학습 대상인 policy에서 생성되어야 하기 때문에 한번 사용한 데이터는 다시 쓰지 못하는 단점이 있습니다. Objective에 Entropy term을 추가를 통한 near-optimal policy 고려와 exploration 능력 향상 Policy의 엔트로피가 클수록 특정 행동의 확률이...