-
동적 계획법 모델화하기
서론 세상에는 수없이 많은 알고리즘 문제가 있습니다. 그러나 새로운 문제를 볼 때마다 항상 지금껏 보지 못한 새로운 기법을 사용해야 하는 것은 아닙니다. 문제의 특성을 파악하고, 조건들을 이용하여 자신이 아는 문제로 변환한 뒤, 이전에 다른 문제를 풀 때 사용했던 기법을 비슷하게 적용하여 풀 수 있기도 합니다. 이처럼 많은 문제는 몇 가지 정해진 전형적인 형태로 모델화 되는 경우가 많습니다. 반면에 큰 알고리즘 분류 중에 많은 사람들이 처음 접할 때 큰 벽을 느끼는 분야가 있습니다. 바로 동적 계획법(dynamic...
-
SVP and CVP
서론 이번에 N1CTF에 Super Guesser 팀으로 참전해서 4등을 차지했습니다. (ctftime) 한국의 강력한 crypto hacker rkm0959님과 함께 할 수 있는 좋은 자리였는데요, N1CTF에 나온 한 문제가 SVP(Shortest Vector Problem)과 CVP(Closest Vector Problem)에 대해서 다루기 좋아서 이번에 이렇게 글을 작성하게 되었습니다. 본론 Lattice 우선 SVP와 CVP에 대해서 살펴보기 전에 Lattice에 대해서 알아봐야 합니다. Lattice는 이름에서 알 수 있듯이 격자 형태를 나타내는 수학적 개념입니다. Lattice는 서로 independent한 vector ${v_1, v_2, \ldots v_n}$이 있을 때 다음과 같은 집합을 의미합니다....
-
IOI 2020
IOI 2020 IOI 2020 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 최은수, 100 / 100 / 100 / 100 / 93.00 / 100, 593.00점, 2등 (금메달) 송준혁, 75 / 100 / 100 / 100 / 92.62 / 65.32, 532.94점, 12등 (금메달) 임성재, 44 / 100 / 41 / 100 / 92.24 / 100, 477.24점, 30등 (은메달) 반딧불, 32 / 100 / 53 / 21 / 80.14 / 100, 386.14점, 61등 (은메달) 올해 한국 학생들의...
-
Bairstow's method
안녕하세요? 오늘은 다항식의 근사해를 찾아내는 수치해석 알고리즘인 Bairstow’s method에 관해 알아보겠습니다. 다항식의 근사해 찾기 주어진 다항식의 해를 찾는 방법은 어떤 것들이 있을까요? 가장 먼저 생각해 볼 수 있는 것은 근의 공식입니다. 예를 들면 $ax^2 + bx + c = 0$이라는 다항식의 해가 $\frac{-b \pm \sqrt{b^2 - 4ac}{2a}}$라는 것은 잘 알려져 있습니다. 하지만 근의 공식은 몇 가지 문제점을 가지고 있는데, 첫째로 5차 이상의 다항식에 대해서는 근의 공식이 존재하지 않는다는 점과, 둘째로 3차 이상의 다항식에 대한 근의...
-
AI tutorial - Reinforcement Learning
AI tutorial - 2 . Reinforcement Learning Contents 들어가며 강화학습이란? CarRacing-v0를 이용한 강화학습 결론 참고 들어가며 앞서 AI tutorial 글로 Image Classification 에 대해 다루었습니다. 그 후에 AI 분야에 관련해서 입문하기 쉽고 재미있는 부분을 고르는데에 있어서 고민이 많았습니다. 이미지 분류기에서 파생되는 객체탐지(Object Detection), 감정분석(Sentiment Analysis) 같은 분야에서 다루는 자연어처리 기법, 시계열 예측, 적대적 신경망, 음성 변조 같은 곳에 유용하게 사용되는 VAE(Variational AutoEncoder) 등 여러가지가 존재하고 있습니다. 그러나 대부분의 AI분야가 이론과 실습 분야는 손쉽게 접근할 수...