[editorial] CYRAM SNA competition

  • nocut98
    nocut98

    먼저 결과는...
    http://www.cyram.com/bbs/view.php?id=Announce&page=1&sn1=&divpage=1&sn=off&ss=on&sc=on&select_arrange=headnum&desc=asc&no=4
    1. 수상자 발표
         - 최우수상(1팀) : 그물(KAIST)
         - 우 수 상 (1팀) : 듣보잡(일반)
                                  (※ 심사 결과의 편차가 큰 관계로 우수상을 1팀으로 확정함)
         - 장 려 상 (3팀) : GooGooGooMassiZzo(연세대학교)
                                  AndromedaExpressSoloJM(연세대학교)
                                  HelloWorld!(POSTECH)
    이고, 저는 듣보잡이라는 4명(nocut98, dgsquare, ...)의 팀으로 등록했습니다
    [문제]
    댄스 수업에서 커플 댄스를 추고
    1) 주로 이성과 춤을 추고
    2) 같은 과 끼리 춤을 춤니다.
    기록으로 남은 매칭 데이터만 가지고, 과와 성별을 분리해 내는 게 문제입니다.
    [문제 분석]
    나와 가까운 사람은 누구인가? 나와 여러 번 춤을 춘 사람?

    • 나와 춤을 춘 사람을 가깝다고 하기에는 다른 과의 사람이나 동성하고도 춤을 추므로 가중치를 주기 어렵습니다. 다른 과의 누구와도 사실 2번 정도 춤을 출 수도 있으니까요. 저의 아이디어는 "나랑 춤을 춤 N명과 제일 많이 춤을 춘 사람은 매우 높은 확률로 아마 나와 같은 반이라고 생각할 수 있다. 그리고 그 사람은 동성이다"라는 점이었죠(N자체가 너무 작은 사람은 뺏습니다) 그래서 나와 춤을 한번도 추지 않았더라도 내 파트너들과 주로 춤을 춘 사람을 나의 Best Friend로 정의 했습니다. 그렇게 그룹을 만들면(나의 Best Friend가 어느 그룹안에 있으면 글루 들어가고, 아니면 내가 최초의 그룹을 만들구요) 동성의 그룹이 만들어 집니다. 아래 처럼요 101 88 72 70 69 68 65 61 57 54 51 42 42 38 37 35 34 34 33 33 32 32 31 31 31 29 28 26 25 24 23 23 23 22 21 21 21 20 20 20 20 19 19 19 19 19 19 18 18 18 17 17 17 16 15 15 13 13 13 13 13 13 13 12 12 12 12 12 12 11 11 10 10 10 10 9 9 9 9 8 8 8 8 8 8 8 8 8 8 8 7 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

    그럼 우리 그룹과 가까운 그룹은?

    • 이제는 그룹이 형성되어서 매칭하는 건 쉽습니다. 그냥 우리 그룹과 제일 춤을 많이 춘 그룹이 있으면 합칩니다. 그룹 자체가 크기 때문에 가중치가 충분히 형성되죠. 만약 같은 과의 사람이 아니라면, 합칠 정도로 연관관계가 없을테구요. 그럼 점차 그룹이 합쳐지면서 줄어들고... // 동성 그룹을 합치기 시작한다. // 처음에는 주로 남성/여성 그룹을 합치기 위해서 0.5의 값을 준다. // 과의 숫자가 줄어드는 것을 볼 수 있다. makeClass start: 521 0.5 makeClass start: 318 0.5 makeClass start: 282 0.5 makeClass start: 277 0.5 // 작은 과들 간의 병합을 위해서 0.15의 값을 준다. makeClass start: 277 0.15 makeClass start: 26 0.15 makeClass start: 24 0.15 이고, 데이터의 특성이 같은 과는 연관관계가 20% 이상이고 다른 과와는 연관관계가 3% 이하여서 분리하기가 쉽더군요.결국 아래와 같은 24개의 과 데이터가 최종적으로 나옵니다.   300 (142,158), 0.0128914 2   200 (113,87), 0.0179469 0   200 (90,110), 0.0202816 0   200 (86,114), 0.0161961 0   200 (104,96), 0.0156417 0   200 (105,95), 0.0196062 0   200 (94,106), 0.0189008 0   150 (75,75), 0.0196771 0   140 (70,70), 0.0209997 0   130 (62,68), 0.0203709 0   120 (59,61), 0.0159978 0   100 (54,46), 0.0176757 0   100 (51,49), 0.0209792 0   100 (46,54), 0.0191237 0   100 (51,49), 0.0154912 1   100 (48,52), 0.016502 0   80 (45,35), 0.0193599 0   70 (33,37), 0.0211685 0   60 (37,23), 0.020114 0   50 (21,29), 0.02193 0   50 (24,26), 0.0163903 2   50 (30,20), 0.0198655 0   50 (28,22), 0.0198275 0   50 (31,19), 0.0188405 0 각 그룹도 10으로 자동으로 나눠 떨어지고, 남녀 성비도 대충 맞는 군요. cyram.cpp 하나에 모든 코드가 (주석 포함) 400줄 정도로 간단한 편이고, 수행 시간도 1분 안쪽이면 다 끝나서 .추가적인 최적화나 다른 일은 안했습니다. [후기] 아마 일루님이 나오셨으면 당연히 밟힐 준비를 하고 있는데, 개인적인 사정으로 참가를 안해주셔서(?) 참 다행이라고 생각했구요 일루님이 "MM은 최적화가 아니라 아이디어 싸움"이라는 요지의 말씀을 하셨었는데, 공감합니다. 왜냐면 사실 저도 한다리 건너서 동성끼리 그룹핑한다는 아이디이가 운좋게 떠오르지 않았다면, 제 실력과는 별개로 더 어려운 길을 걸었을 테니까요;;; 저는 다행히 초기에 데이터가 잘 나온 편이어서 이후에는 그냥 코드를 정리하고 잔버그를 잡으며 참가자가 없기만 바랬구요. 결과적으로는 생각되로 된 듯 합니다. 아마 많은 분들이 참여하셨으면 우수상도 타기 어려웠겠죠. 결과 데이터는 혹시 24개의 과 이상으로 분리할 수 있는지 좀 더 분석해 봤지만, 아닌 거 같았구요. 남녀 비율도 더 정확하게 맞춰 볼려고 했는데, 데이터를 어떻게 바꿔도 별 차이는 없더군요. 아마 최우수상팀도 과는 24개로 분리했을거라고 생각합니다. 그 팀은 어떻게 문제에 접근하고 어떻게 데이터가 나왔는지 궁금하네요^^ 그리고 데이터 뽑는 것은 지금 이상으로 더 나올 것이 별로 없고 남녀중에서 제일 춤을 많이 춘 사람만 출력하면 되는 것이라서 심사하기 좀 까다롭겠다는 생각이 들었습니다. 그래서 Q&A에도 비슷한 내용의 글을 올렸었는데, 결국 싸이람에서 정밀 심사를 한다고 발표를 늦춰서 애간장이 좀 탔습니다. 
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    12년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    후럴, 간단하네요 orz난 왜 그 삽질을 했단 말인가? ㅠㅠ 멋있어요~ :)


    12년 전 link
  • 일루
    일루

    축하드려요 ^^;;


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.