-
Pix2Pix 이미지 변환 모델 소개 및 구현
소개 “Image-to-Image Translation with Conditional Adversarial Nets”은 CVPR 2017에 accept된 논문입니다. 이 논문은 이미지의 도메인간 변화를 다루는 문제인 image to image translation을 처음으로 정의했습니다. 이 변환에는 흑백 사진을 컬러화 시키는 것, 윤곽이 주어졌을 때 물체를 그리는 것 등이 포함됩니다. 이전까지는 각각의 변환 문제마다 다른 모델을 사용했었는데 해당 논문에서는 자신들의 Pix2Pix 모델이 대부분의 변환 문제를 잘 해결함을 보여주었습니다. 이미지 변환 예시 (출처: https://phillipi.github.io/pix2pix/) 이미 수많은 이미지 처리 문제는 convolutional neural nets(CNNs)를 사용해서 해결하고 있습니다. 하지만, 여전히...
-
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선의 최소 개수, 혹은 간선 가중치의 최소 합이다. 만약 간선의 최소 개수로 컷을 정의한다면, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래...
-
ROCA 취약점
안녕하세요, 이번 글에서는 2017년 2월에 제보된 RSA 구현에서의 취약점인 ROCA(Return Of Coppersmith Attack)에 대해 다뤄보겠습니다. RSA RSA는 별도의 설명이 필요없을 정도로 너무나 유명한 공개키 암호 시스템입니다. 암호화/복호화 과정이 헷갈리시는 분은 RSA_암호 위키를 참고하시는 것을 추천드립니다. RSA는 큰 소수 2개를 곱하는 것은 쉽지만 소인수분해하는 것은 어렵다는 사실을 이용한 암호 시스템입니다. 비록 소인수분해를 다항 시간에 처리하는 양자 알고리즘이 존재하지만 실제 양자컴퓨터가 개발되어 RSA가 무력화되기까지는 아주 긴 시간이 필요할 것으로 예상됩니다. 이외에는 RSA 암호 시스템 자체에 대한 취약점이...
-
Codeforces 레이팅
서론 현존하는 알고리즘 대회 사이트 중 최대 규모라고 할 수 있는 Codeforces는 유저들의 랭킹을 결정하기 위한 자동화된 레이팅 시스템을 가지고 있습니다. 각 유저가 대회를 참가할 때마다 그 성적에 따라 레이팅이 변화하는 방식으로, 비교적 합리적인 결과를 보여주지만 때로는 논란이 될 수 있는 행동을 보이기도 합니다. 이 글에서는 Codeforces의 레이팅을 산출하는 공식에 대해 분석해 보고, 이 공식이 가진 특징과 경향, 그리고 한계와 문제점을 예시를 통해 확인해 보도록 하겠습니다. Elo 레이팅 Codeforces의 레이팅은 Elo 레이팅에 기반을 두고 있습니다....
-
Huffman coding과 Data entropy
안녕하세요? 오늘은 압축 알고리즘에 대한 설명을 진행해보려 합니다. Lossless Data Compression 데이터 압축은 굉장히 중요한 기술 중 하나입니다. 데이터 압축의 가장 큰 장점은 뭐니뭐니해도, 사용하는 공간의 크기를 줄일 수 있다는 점입니다. 저장장치의 크기는 정해져 있는데, 이 곳에 데이터를 압축하여 저장한다면 같은 비용으로 더 많은 데이터를 저장할 수 있게 됩니다. 데이터 압축의 또 다른 장점으로는, Bandwidth를 높여주는 효과를 가져온다는 점입니다. 예를 들어서 통신을 할 때, 통신 속도가 충분히 빠르지 않다면 이 과정이 병목이 될 가능성이 높습니다....