Code Sprint 2013 round 1 editorial

대회 소개

안녕하세요. 작년에 Code Sprint 라운드 2의 출제를 맡았던 정헌(a.k.a. blmarket) 입니다. 올해에는 라운드 1의 출제를 맡아 Skein mining 문제를 냈습니다.

대회 통계

3일 가량의 대회 기간동안 70명의 참가자가 총 685 건의 답안을 제출했으며, 이중 0점 이상의 점수를 받은 참가자가 49명 있었습니다. 작년 2회 연속 2등에 빛나는 Won-seok Yoo님께서 올해에는 1위 달성에 성공하셨습니다. 이어서 Chan Min Kim님, Jinho Kim님이 각각 2,3등을 차지했습니다.

출제 의도

BitCoin은 완전한 익명성을 보장하는 디지털 통화로 알려져 있으며, 다수의 인터넷 사이트에서 BitCoin을 사용해서 실제 통화와의 환전 및 거래를 하고 있습니다.

새 BitCoin을 만들기 위해 mining이라는 과정을 거치는데, 이는 hash 함수를 계속 돌려서 정해진 범위 이하의 낮은 값이 나오면 해당 값을 검증해서 새 BitCoin으로 인정하는 과정입니다. 이런 mining은 초창기 CPU mining 및 GPU를 활용한 병렬처리를 거쳐 아예 지금은 전용 프로세서(ASIC)를 만들어서 수행하는 것이 대세가 되고 있습니다. 전체 miner의 계산량 총합이 높아질수록 개인이 얻을 수 있는 기대수익은 떨어지도록 설계되어있기 때문에, 적은 비용으로 높은 계산량을 뽑아낼 수 있는 ASIC 기반 마이닝이 빠르게 유행할 것으로 보입니다.

문제 출제 당시에 BitCoin의 실물 환전 시세가 엄청나게 요동치고 있어서 개인적으로 관심을 갖고 이 mining 과정을 비슷하게 문제로 만들어본 것이 Skein mining입니다. 참가자의 CPU 성능에 따라 순위가 갈리는 문제가 있을 듯 하여 저희 시스템에서 바로 실행되도록 환경을 구성하였으며, 문제도 hash 계산만 하는것이 아니라, 두 개의 값을 XOR하도록 만들어서 기존 mining과는 다른 방법으로 접근해야 좋은 점수를 받도록 변경하였습니다.

풀이

상위권 참가자들의 답은 대부분 hash table과 비슷한 아이디어를 사용하고 있습니다. 주어진 prefix에 적당히 문자열을 붙여 적절한 값을 만든 다음, 적당한 bit 수만 남기고 잘라낸 다음, bucket에 넣으면서 충돌하는 녀석이 있는지 확인하는 식입니다.

 그림 1. Hash Table

다만 중간중간에 충돌 체크를 할 필요도 없으므로 모든 hash들을 다 계산해서 bucket에 몽땅 넣고, 이후 bucket들을 돌면서 충돌하는 녀석들에 대해 점수를 계산해보는 식으로 개선을 할 수 있습니다.

이때 시간 제한에 맞춰 얼마나 많은 수의 해쉬를 만들 것인가, bucket의 크기는 어느 정도로 하는 것이 좋은가 하는 것들을 가지고 튜닝을 해야 합니다만, 이건 파라미터 값을 변경시키면서 테스트해보면 금방 적당한 값들을 얻을 수 있습니다.

그 외에 주의해야 할 점으로 prefix들을 가지고 같은 문자열을 만들 수 있는 경우입니다. 이 경우는 아예 같은 hash를 만들어낼 수 있으므로, 이런 성질을 이용하지 않는 경우와 비교해서 엄청나게 좋은 점수를 받는 것이 가능합니다. 2등을 차지한 Chan Min Kim님께서는 이런 부분에 대한 처리가 없어 일부 케이스에서 큰 점수 차이가 났습니다.

3등을 차지한 Jinho Kim님께서 본인의 접근방법을 설명한 글을 http://algospot.com/forum/read/1850/ 에 적어주셨으니 풀이 참조에 활용하시면 좋겠습니다.

그 외에도 1,2,3등 참가자의 소스 코드가 홈페이지에 공개되어 있습니다(순위 공개 페이지에서 1,2,3등 참가자의 이름 부분 링크를 클릭하시면 됩니다).

개선해야 할 점

문제 특성상 자체 채점 시스템을 제공했습니다만,  hash 라이브러리의 문제도 있고 해서 여러 프로그래밍 언어를 지원하지 못한 점은 아쉬웠습니다.

그림 1: 위 이미지는 Wikipedia에 public domain으로 공개된 이미지입니다. 따라서 별도의 저작권 표기를 하지 않았습니다.

정헌 Platform software개발1팀

읽기 5분, 생각 5분, 코딩 1시간, 뿌듯해 하다가 더 쉬운 방법 발견하기 15분, 후회 1일, 다시 코딩 10분, 문제 해결…

공유하기