-
Error-bounded Piecewise Linear Representation
안녕하세요? 오늘은 주어진 데이터를 여러 개의 선형 방정식으로 근사하되, 모든 점들마다 최대 오차가 $\delta$ 이하로 bound되도록 하는 Error-bounded Piecewise Linear Representation를 구하는 방법에 대해 알아보겠습니다. 이 글의 내용은 2014년 발표된 논문인 Maximum error-bounded Piecewise Linear Representation for online stream approximation을 참고하였습니다. PLR이란? Piecewise Linear Representation(PLR)은 주어진 데이터를 구간마다 여러 개의 선형 방정식으로 근사하는 방법입니다. PLR을 사용하면 얻을 수 있는 이점은 데이터의 절약입니다. 위 Fig 1는 총 11개의 데이터를 포함하고 있지만, 해당 데이터를 3개의 선으로 근사한다면...
-
동적 계획법 모델화하기
서론 세상에는 수없이 많은 알고리즘 문제가 있습니다. 그러나 새로운 문제를 볼 때마다 항상 지금껏 보지 못한 새로운 기법을 사용해야 하는 것은 아닙니다. 문제의 특성을 파악하고, 조건들을 이용하여 자신이 아는 문제로 변환한 뒤, 이전에 다른 문제를 풀 때 사용했던 기법을 비슷하게 적용하여 풀 수 있기도 합니다. 이처럼 많은 문제는 몇 가지 정해진 전형적인 형태로 모델화 되는 경우가 많습니다. 반면에 큰 알고리즘 분류 중에 많은 사람들이 처음 접할 때 큰 벽을 느끼는 분야가 있습니다. 바로 동적 계획법(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차 이상의 다항식에 대한 근의...