Code Sprint의 round 1 행사를 준비하며

안녕하세요. 저는 SK플래닛 Data Platform팀에 근무하는 이채현입니다. 올해 11월에 성황리(?)에 종료된 Code Sprint 에 대한 후기를 남기기 위해 글을 적어 봅니다.

초기 Code Sprint 행사에 제안된 문제는 현재와 많이 달랐답니다. Netflix Prize 형태로 T Store 구매데이터를 제공하여, 개인화 추천의 품질을 끌어올리는 알고리즘 문제부터, 통계를 기반으로 한 띄워쓰기 교정 문제, 대용량 데이터에 대해 정수형 아이디 빠르게 만드는 문제 등등.. 간단한 문제부터 복잡하지만 참신한 문제까지 다양한 형태의 문제들이 제안되었습니다.

그런데 고객 데이터 제공에 따른 법률적 이슈, 한글 혹은 영어를 사용할 경우, 언어적 지식을 사용한 어뷰징 이슈, 대용량 데이터를 처리하기 위한 Hadoop과 같은 인프라 제공 이슈 등, 현실적인 장벽에 가로 막혀 결국 살아 남은 문제가 바로 round 1 경로찾기 문제와 round 2 라이프 게임 문제입니다.

Round 1의 초기 문제는 실제 출제된 문제보다 더 단순한 형태였는데요. 서울의 각 동이름과 동 사이의 이동 시간, 친구들의 출발 위치가 주어졌을 때, 어느 동에서 만나는 것이 가장 빠를까? 를 묻는 간단한 문제였습니다. 거기에 T map으로부터 실제 데이터를 제공 받아, 조금 더 현실감 있게 만들 계획이었죠.

Round 1 부터 너무 복잡한 문제가 제시되면, 일부 개발자들만이 참가하는 행사가 되지 않을까 하는 걱정에, round 1은 최대한 쉬우면서도 흥미로운 문제를 제시하여, 보다 폭 넓은 개발자들의 참여를 유도하고, round가 진행되면서 조금씩 난이도를 조절할 생각이었습니다. 그런데 SF 공상 과학을 좋아하시는 전윤호 원장님께서 이왕 하는 거 “서울시 행정동 보다는 우주 스케일로 끌어 올려서 난이도를 좀 더 어렵게 하는게 어떨까?” 라고 제안을 주셔서 현재와 같은 round 1 문제가 탄생하게 되었답니다.

먼저 목표로 한 데이터의 크기는 한 번에 메모리에 올라가지 않을 정도인 10 GB정도였고, 데이터의 형태는 방향성이 있는 weighted graph를 만드는 것이었습니다. 몇 번의 고민 끝에, 아래와 같은 규칙에 따라 데이터를 생성하였습니다.

  1. 랜덤은 Gaussian 분포를 사용
  2. 각 점 당 평균 연결선의 개수는 1000개
  3. Connected graph임을 확인하기 위해 모든 점 i와 점 i+1은 무조건 연결됨
  4. 0214로 끝나는 점은 행운의 점으로 연결선의 개수가 늘어나고, 이 점에서 출발하거나 도착하면 이동시간이 1/10로 감소
  5. 10000, 20000, 30000, … 점들은 교차로로써, 연결선 개수가 늘어나지만, 이 점에서 출발하거나 도착하면 이동시간이 증가
  6. 50000~70000 구간은 교통 체증 구간으로 이동 시간이 증가
  7. 소수에서 출발하면 이동시간이 증가
  8. 2000~4000번 구간은 방향성이 있는 구간으로, 반대방향으로 이동하면 이동 시간이 감소

이렇게 100 만 개의 점들과 약 6억 개의 연결선으로 이루어진 9.9 GB 용량의 데이터 파일이 생성되었습니다.

대회를 준비하면서, 이 정도 크기의 데이터를 메모리에 올리지는 못할테고, 파일로 나눠서 풀거나, DB에 올려서 최적화를 하지 않을까 궁금해 했었는데, 뚜껑을 열어보니, 1등 류원하님과 3등 최백준님 모두 데이터를 메모리에 올려놓고 계산을 하셔서 맥이 좀 풀렸습니다. (원장님~ 저희 개발 PC도 좀 업그레이드를.. )

아직도 솔루션을 궁금해 하시는 몇몇 분들을 위해 깔끔하게 하나의 파일로 솔루션을 제출해 주신 류원하님과 최백준님의 소스코드와 round 1 최적의 해를 공유해 드리니 참고 하시기 바랍니다.    codesprint_round1 자료 다운 받기

1등 류원하님의 문제해결 흐름도와 수행결과가 궁금하신 분들은 류원하님이 작성하신  Code Sprint Round1 우승후기를 참고하시면 됩니다.  상품 수상하시던날 발표해주신 자료도 같이 보세요~

Code Sprint에 참가해 주신 모든 개발자 여러 분께 감사드리며, 여러 분들의 참여와 피드백으로 인해 내년에는 좀 더 알찬 행사가 될 수 있지 않을까 하는 예상을 해 보며, 이 글을 마칩니다.

NASA Ames Research Center 인턴, LG 유플러스, NHN을 거쳐 현재는 SK planet에서 대용량 데이터 처리 시스템을 개발하고 있으며, 요즘은 오픈소스인 Hadoop과 Mahout을 주로 사용하고 있습니다.

공유하기