-
Codeforces 레이팅
서론 현존하는 알고리즘 대회 사이트 중 최대 규모라고 할 수 있는 Codeforces는 유저들의 랭킹을 결정하기 위한 자동화된 레이팅 시스템을 가지고 있습니다. 각 유저가 대회를 참가할 때마다 그 성적에 따라 레이팅이 변화하는 방식으로, 비교적 합리적인 결과를 보여주지만 때로는 논란이 될 수 있는 행동을 보이기도 합니다. 이 글에서는 Codeforces의 레이팅을 산출하는 공식에 대해 분석해 보고, 이 공식이 가진 특징과 경향, 그리고 한계와 문제점을 예시를 통해 확인해 보도록 하겠습니다. Elo 레이팅 Codeforces의 레이팅은 Elo 레이팅에 기반을 두고 있습니다....
-
Huffman coding과 Data entropy
안녕하세요? 오늘은 압축 알고리즘에 대한 설명을 진행해보려 합니다. Lossless Data Compression 데이터 압축은 굉장히 중요한 기술 중 하나입니다. 데이터 압축의 가장 큰 장점은 뭐니뭐니해도, 사용하는 공간의 크기를 줄일 수 있다는 점입니다. 저장장치의 크기는 정해져 있는데, 이 곳에 데이터를 압축하여 저장한다면 같은 비용으로 더 많은 데이터를 저장할 수 있게 됩니다. 데이터 압축의 또 다른 장점으로는, Bandwidth를 높여주는 효과를 가져온다는 점입니다. 예를 들어서 통신을 할 때, 통신 속도가 충분히 빠르지 않다면 이 과정이 병목이 될 가능성이 높습니다....
-
SMT Solver in CTF - z3 vs Boolector
서론 SMT (Satisfiability modulo theories) Solver는 CTF에서 빠질 수 없는 존재입니다. SMT Solver가 무엇인지 구체적으로 설명하기 보다는, 다음 z3py 예시를 보는 것이 더 직관적일 것입니다. (Link) x = Int('x') y = Int('y') s = Solver() print s s.add(x > 10, y == x + 2) print s print "Solving constraints in the solver s ..." print s.check() print "Create a new scope..." s.push() s.add(y < 11) print s print "Solving updated set of constraints..." print...
-
visualizing data
Visualizing data Contents 탐색적 자료 분석 Data to Image 다양한 툴과 차트 마치며 참고자료 탐색적 자료 분석 “the greatest value of picture is when it forces us to notice what we never expected to see” 위는 ‘존 튜키’ 라는 통계학자의 발언으로, 그림의 가장 위대한 가치는 우리가 예상하지 못한 것을 알려줄 때 라고 말하고 있습니다. 탐색적 자료 분석 (Exploratory Data Analysis) 는 ‘존 튜키’ 라는 통계학자가 창안한 자료 분석 방법으로, 시각적 방법으로 주요 특성들을 알아내기 위해,...
-
양자 컴퓨팅 입문 (2) - Grover's Algorithm
Grover’s Algorithm은 정렬되지 않은 데이터베이스에 있는 $N$개의 항목 중 특정한 조건을 만족하는 항목을 $O(\sqrt{N})$에 찾는 알고리즘입니다. 고전 컴퓨팅에서 이 문제를 해결하려면, 간단하지만 느리게 갈 수밖에 없습니다. 전수 조사(brute force)가 유일한 해결책입니다. 당연히 시간 복잡도는 $O(N)$이며, 랜덤하게 셔플해서 순서를 바꾼다 해도 마찬가지입니다. 그리고 이보다 더 나은 시간복잡도로 찾을 수는 없습니다. Grover’s Algorithm은 이 시간복잡도를 $O(\sqrt{N})$으로 낮추는데 성공하였고, 이 시간복잡도가 최적이라는 것이 알려져 있습니다. 또다른 유명한 양자 알고리즘인 Shor’s Algorithm과는 달리 알고리즘 자체가 간단하면서도 심도 있기 때문에...