-
행렬 분해(Matrix Decomposition)
행렬 분해(Matrix Decomposition) 행렬 분해(matrix decomposition)는 여러 특정 구조를 가진 행렬들의 곱으로 기존의 행렬을 나타내는 것을 의미합니다. 예를 들어, $ A = \begin{bmatrix} 1 & 2 & 3 \ 2 & 4 & 6 \ 3 & 6 & 9 \end{bmatrix}$ 와 같은 행렬을 생각해 봅시다. 이 경우 $ A $를 아래와 같이 $ 3 \times 1 $ 크기의 두 행렬과 $ 1 \times 1 $ 크기의 대각 행렬 을 통해 나타낼 수 있습니다. $...
-
Berlekamp-Massey 알고리즘의 이해와 응용
Berlekamp-Massey 알고리즘의 이해와 응용 Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지...
-
Discriminator Rejection Sampling
Generative Adversarial Networks(GANs)는 머신러닝 기술의 일종으로 생성자(generator)와 판별자(discriminator) 두 네트워크를 적대적으로 경쟁시켜 학습시키는 프레임워크를 말합니다. 보통 GANs에서는 학습이 완료되면 생성자 네트워크만 사용하고 판별자 네트워크는 버리게 됩니다. 하지만, 학습 이후에 여전히 생성자 네트워크가 실제 데이터 분포를 완벽히 묘사하지 못하고 판별자 네트워크가 이에 대해 중요한 정보를 가지고 있을 수도 있습니다. 그렇다면 학습 이후에도 판별자 네트워크를 활용하여 생성자 네트워크의 성능을 높일 수 있지 않을까요? Discriminator Rejection Sampling(DRS)은 ICLR 2019에 accept된 논문으로 GANs 학습 이후에 판별자(discriminator)를 이용하여 생성자(generator)의 성능을...
-
문제 출제를 위한 플랫폼 - Polygon 사용하기
Polygon이란? Polygon이란 Codeforces에서 제공하는 Competitive Programming Contest를 위한 문제 출제를 위한 플랫폼입니다. 출제를 위해 필요한 과정 - 데이터 제작, 검증, 솔루션 검증 등에 굉장히 유용한 기능들이 많으며 그 과정을 다른 사람과 공유하며 협업할 수도 있습니다. 폴리곤에서의 작업은 각 문제 단위로 동작합니다. 문제를 등록하는 방법부터 완성된 문제를 패키지로 다운받는 방법까지, 필요한 기능들을 간략히 확인하고 언제 어떤 메뉴를 사용해야 하는지 문제 출제 단계에 따라 익혀봅시다. 아, 그 전에 회원가입은 다들 하셔야겠죠? 문제 등록하기 폴리곤에 로그인하면 아래와 같은...
-
Bloom Filter
안녕하세요, 오늘은 Bloom Filter 와 변종들중에 하나인 Scalable Bloom Filter 에 대해서 알아보는 시간을 가지려고 합니다. 너무 자세하거나 수학적인 설명은 배제하고 직관적인 이해를 기반으로 포스팅하겠습니다! 자세한건 그냥 논문을 보세요… » 이 글을 좀 더 좋은 가독성으로 읽기 « Bloom Filter 란? Bloom Filter 는 집합내에 특정 원소가 존재하는지 확인하는데 사용되는 자료구조입니다. 이러한 “membership test” 용도로 사용되는 자료구조들은 Bloom Filter 외에도 다양합니다. 대표적이고 널리 알려진 것으로는 Balanced Binary Search Tree (AVL, red-black tree 등) 과 해시...