공지사항

• 와우~ 오로지 실력 위주로만 뽑겠다는 말씀이신데.. 괜찮은데요^^
  재직중만 아니라면 허접한 실력이지만 한번 도전해보고 싶어질정도로요^^
  한가지 홈피랑 다른점은 홈피는 석사학위 이상이거나 그에 준하는 경력 -0-;이 자격요건이라고 되어있고.. 상세 복리후생에 대해서는 나와있지 않네요^^
• MK.love
• 2007-05-03 17:33:32
• x

• 개발팀 2번 문제는 이해가 안감 -_-
• Q u i c K
• 2007-05-03 17:59:10
• x

• 큐브리드 홈페이지에 올라가 있는 채용공고의 자격요건(석사 운운)은 무시하시기 바랍니다. 홈페이지는 현재 변경 중입니다. 복리후생 정보는 JobKorea(http://www.jobkorea.co.kr/List_GI/GIB_Read.asp?GI_No=3618960)에 올려 놓았습니다만, 정리하면 다음과 같습니다.
  
  연금•보험 : 국민연금, 고용보험, 산재보험, 건강보험
  휴무•휴가 : 주5일근무, 연차
  보상제도 : 인센티브제, 우수사원 표창/포상, 스톡옵션, 퇴직금
  생활편의 지원 : 석식제공
  경조사 지원 : 각종 경조금, 경조휴가제
  교육•여가 지원 : 교육비 지원, 자기계발비 지원
• 김평철
• 2007-05-03 19:28:16
• x

• 지원해보고 싶지만;;
  너무 어렵;;; ㄷㄷㄷㄷ;
  
  결국 잘하는분들만 뽑는...;; 털썩;
• 별이총총
• 2007-05-03 19:40:39
• x

• (개발팀) 2번 문제에 대하여 좀 상세하게 설명하지요. 예를 들어, int GetNextNumber(Stream *p)라는 함수가 있는데, 한번 호출할 때마다 음수가 아닌 하나의 숫자를 복귀합니다. 그러다가, 끝이 되면 음수를 복귀합니다. 마치, fgetc(fp)와 유사하지요. 그런데, 문제는 이 함수가 몇 개를 복귀한 후 음수를 복귀할 지 끝까지 가 봐야 안다는 것입니다. 제가 원하는 것은 이 함수가 복귀하는 숫자들 중에 무작위로 1000개를 고르고자 하는 것입니다. 만약, 이 함수가 1000개를 복귀하고 음수를 복귀한다면, 1000개 그대로가 원하는 데이터이겠지만, 만약, 이 함수가 1억개를 복귀한다면 1억개 중 1000개를 랜덤(무작위)하게 뽑아야겠지요. 그런데, 문제는 1억개를 저장할 공간이 없다는 것입니다. 따라서, 1억개를 모두 받아놓은 후 1000개를 추출할 수 없고, 하나씩 보면서 결국 끝을 보았을 때, 1000개가 1억개의 임의추출 결과가 만들어지는 방법이 필요합니다. 이 문제는 제가 MS-SQL 데이터마이닝팀에 있을 때, 방대한 데이타의 샘플분석을 위해 해결해야 했던 문제이고, 실제로 그 결과가 SQL 2005 DM의 데이터탐험 기능에 탑재되어 있습니다. 수학적으로 맞는지를 증명하는 것은 좀 어려울지 몰라도, 방법을 찾는 것은 그리 어렵지 않을 것입니다. ^^
• 김평철
• 2007-05-03 19:47:39
• x

• 오~ 어느분이신가 했는데....
  엊그제 검색하다가 기사에서 뵌 분이시네요...
  하시는일 아주 잘되길 빌겠습니다....
  
  엠파스에서 "박대연 김평철" 이렇게 검색하면 디지털 타임스 기사가 나오네요...
  
  http://news.empas.com/show.tsp/cp_dt/20070427n04156/?kw=%7B%B9%DA%B4%EB%BF%AC+%B1%E8%C6%F2%C3%B6%7D+%7B%B9%DA%B4%EB%BF%AC+%B1%E8%C6%F2%C3%B6%7D+%7B%B9%DA%B4%EB%BF%AC+%B1%E8%C6%F2%C3%B6%7D+%7B%7D
  
  티맥스의 티베로는 soa지원 모듈이라나?
  여튼 국산 상용DB가 잘 성장했으면 하는 바램입니다....
  .
  
  
  
• 사이보그
• 2007-05-03 20:12:38
• x

• 한번 호출할 때마다 음수가 아닌 하나의 숫자를 복귀합니다. 그러다가, 끝이 되면 음수를 복귀합니다.
  
  여기서 '복귀'한다는게 뭔소린지 궁금하네요.'
  
  면접비도 못받고 집에간다는 뜻인가요?
• 초보만뽑나봐요
• 2007-05-03 22:19:40
• x

• 1. tic-tac-toe 게임을 안해봐서 pass
  ( 바둑이나 오목처럼 게임룰대로 비교해서 끝내면 되겠죠 ㅡ.,ㅡ; )
  
  2. 1000 개를 기억할수 있는 배열을 만들어..
  음수가 나올때까지 돌리면서 넣고.. 1000 개가 다 찬 순간부터..
  복귀된 숫자와 1000 개의 데이타를 비교하여 영역이 뭉치지 않도록 재배열하고 근사값을 버리는 식으로 돌려야 하지 않을까요?
• hiherod
• 2007-05-03 22:53:33
• x

• 이거... 세대차이인가요?? 저 때는 함수의 return을 복귀 혹은 반환이라고 했었는데... ^^
• 김평철
• 2007-05-03 23:08:58
• x

• tic-tac-toe 게임은 http://blog.naver.com/aphro21?Redirect=Log&logNo=100014243872 에서 play할 수 있군요. 게임은 너무 간단합니다. 오목보다 훨씬 쉬운... ^^
  그런데, 원래 tic-tac-toe는 3x3 보드인데, 제가 NxN으로 확장한 것 뿐입니다.
  이 문제는 가로/세로/대각선이 모두 채워졌는지를 검사하는 데, 배열의 첨자(인덱스)를 꼼꼼하게 사용해야 오류없이 작서할 수 있습니다. 보통 많은 개발자가 O(N) (N이 증가하면서 수행시간도 N에 비례하여 증가함) 기법을 사용하는데, O(1) (N이 증가하더라도 같은 성능을 발휘)을 갖는 기법을 찾을 수도 있습니다. 거의 면접을 진행하는 느낌이군요... ^^
• 김평철
• 2007-05-03 23:21:15
• x

• 김평철 박사님 직접 왕림해주셔서 감사합니다.
  공지사항으로 올립니다.
• kenu
• 2007-05-03 23:25:16
• x

• "초보만뽑나봐요"님께,
  "영역이 뭉치지 않도록 재배열하고 근사값을 버리는 식"을 조금만 더 구체적으로 설명해주실래요? 즉, 1001번째 숫자를 받으면, 기존의 1000개 중 하나를 random하게 뽑아서, 교체한다는 뜻인가요? 그것도 방법이긴 한데, 그럼, 2000개쯤 되었을 때 음수가 나오면, 결과가 2000개 중 1000개를 무작위로 추출한 결과와 같아지나요? 그럴 것 같기도 하고, 아닐 것 같기도 하고...
• 김평철
• 2007-05-03 23:29:39
• x

• 아... 돈 문제 고민 안하고 이런 문제 고민하면서 살고 싶습니다.
• anonymous
• 2007-05-03 23:36:53
• x

• anonymous // 진짜 개발을 시작하고 싶었던건 그것때문이었는데 ㅠㅠ 지금도 업무시간에 다소 길게 걸리더라도 끝까지 파해쳐볼려고는 하는뎅ㅠㅠ 것두 한계가 있고..
  게다가 지금은 돈의 노예가 되어서 -0-;;에휴..
• MK.love
• 2007-05-03 23:44:54
• x

• 사이트 운영자로서 한 말씀 드리겠습니다.
  문제는 저도 풀기 힘들 것 같습니다.
  okjsp 사이트는 JSP를 시작한 사람들이 입문에서 중급까지의 과정에서 겪는 일들에 대한 정보공유의 장으로 만들었습니다. DBMS 설계나 Production 레벨의 문제를 푸는 일들은 솔직히 제 사이트에 오시는 분들에게 벅차다는 생각이 듭니다. 오히려 http://kldp.org 나 http://www.devpia.com 에서 한 가지 언어로 오래오래 프로그래밍한 사람들 중에서 찾는 것이 더 나은 확률을 보장할 것이라 생각됩니다.
  웹 관련 개발은 PM팀이나 QA팀에 관련된 문제들에는 접근가능하지만 개발팀과 같은 알고리즘 추론에는 취약하다고 개인적으로 생각하고 있습니다. DBMS는 웹의 여러 Tier중에 핵심위치에 있지만 브라우저까지 도달하는데 필요한 여러 언어들의 계층도 무시할 수 없기 때문입니다.
  
  okjsp에 오시는 분들에게서는 완숙미보다는 가능성을 찾아보심이 좋다고 말씀드리고 싶습니다. 물론 이희승님같은 아파치 커미터도 방문하고 글을 남기지만 저희 사이트 방문자의 반응은 이러했습니다.
  "어제 짬을 내 Lorentz 2.0을 릴리즈하고, TheServerSide.com, JavaService.net, OKJSP.pe.kr에 발표했다. 만 하루가 지난 지금 JavaService.net 과 OKJSP.pe.kr 에 달린 답글은 0, TheServerSide.com 에 달린 답글은 내 것을 제외하고는 8개다. 이 작은 숫자의 차이는 한국의 오픈 소스 문화, 나아가 소프트웨어 개발 문화의 현재와 미래를 보여준다." - from: http://blog.gleamynode.net/2005/08/lorentz-20.html
  
  예전 삼성계열의 UNISQL로 시작해서 계속 이어오다가 최근 Mysql과 같이 듀얼라이센스로 오픈소스의 개발방식을 도입하신 것을 높이 평가하고 있습니다.
  cubrid 는 지난 번 저희 회사에서 브리핑을 들을 기회가 있었습니다. 좋은 소프트웨어 회사가 되기를 진심으로 기원합니다. 공부하지 않는 개발자는 도태시키고, 끊임없이 자신을 패치하면서 업그레이드 시켜나가는 개발자들이 있는 곳으로, 물론 칼퇴근같이 인간다운 삶을 영위할 수 있는 곳. 그리고 제니퍼( http://www.jeniffersoft.com/ ) 처럼 세계로 뻗어나가는 좋은 제품을 만들게 되시길 바랍니다.
  행복하세요.
• kenu
• 2007-05-03 23:47:15
• x

• MOVED FROM recruit
• kenu
• 2007-05-03 23:47:32
• x

• bool IsWinningMove(int **board, int n)
  {
  int i,j;
  int xy, count;
  
  for (i=0; i<n; i++) // 가로 체크
  {
  xy = board(i*n);
  count = 1;
  for ( j=1; j<n; j++ )
  {
  if ( board(j+i*n) == xy )
  {
  count++;
  if ( count == n ) return true;
  }
  else break;
  }
  }
  
  for (i=0; i<n; i++) // 세로 체크
  {
  count = 0;
  for ( j=0; j<n; j++ )
  {
  if ( count == 0 )
  {
  xy = board(i);
  }
  else
  {
  if ( board(i+j*n) == xy )
  {
  count++;
  if ( count == n ) return true;
  }
  else break;
  }
  }
  }
  
  // 대각선 체크
  count=1;
  xy = board(0);
  for (i=1; i<n; i++)
  {
  if ( board(i+i*n) == xy )
  {
  count++;
  if ( count == n ) return true;
  }
  else break;
  }
  
  count=1;
  xy = board((n-1)*n);
  for (i=1; i<n; i++)
  {
  if ( board(i+(n-i-1)*n) == xy )
  {
  count++;
  if ( count == n ) return true;
  }
  else break;
  }
  
  
  return false;
  }
  요렇게 하면 맞는건지 모르겠네요 ㅡ,.ㅡ;( 너무 무식한가요? )
  그리고 1000 개중 무작위로 추출하는게 아니라 포문을 돌려서 가장 가까운 근사치 값을 찾아 버려야 한다는 의미였구요.. 저 부분은 실제로 구현하게 된다면 상당히 많은 생각을 해야 최적화 할수 있을것 같네요...
• hiherod
• 2007-05-03 23:48:02
• x

• "anonymous"님. 그럼, 큐브리드 지원하세요... ^^ DBMS는 가장 복잡한 시스템 SW의 하나로서 항상 이런 문제를 "즐기면서" 살 수 있습니다. 큐브리드는 철저하게 개발자 중심의 문화를 지향하고 있고, 50세가 되어도 개발자로 공헌할 수 있으며, 급여도 직위/직책과 관계없이 공헌도 중심으로 되어 있습니다. SI 회사가 아닌 10년 이상의 패키지 제품을 추구하는 회사이기 때문에 가능하겠지요.
• 김평철
• 2007-05-03 23:50:58
• x

• 조엘테스트를 언급하고 있다는 것만으로도 끌리는 회사입니다..
• ㅇㅇ
• 2007-05-03 23:58:06
• x

• "hiherod"님, 공력이 대단하십니다. 그런데, 마지막 플레이한 위치 (제가 IsWinningMove(... int i, int j)라고 했을 때, i, j)를 알면 모두 검사할 필요없이 board[i][j]부터만 검사하면 편할 것 같습니다. 그러면, O(1)도 가능할 것입니다. 흐음... 정식면접에서 응해보실 생각 없어요?
  
  그리고, 2번은 random 조건에 대해 약간 오해가 있으신 듯합니다. 근사치를 찾을 이유를 모르겠거든요. 예를 들어, 숫자가 "소득"라고 하고, 처음 1000개가 공교롭게도 3천만원 이하의 값들이 나왔다가 1001번째 Bill Gates가 나와 40조(맞나요?)라면, 근사치를 찾아 없앤다는 것은 어떻게 한다는 것인지? 참고로, 무작위의 특성은 어느 숫자든 선택된 1000개에 남아 있는 확률이 같아야 한다는 뜻입니다.
• 김평철
• 2007-05-04 00:13:31
• x

• "후니"님, 기발한 아이디어입니다만, 역시 님께서 지적하신대로 후반부의 숫자가 많이 선택되는 쏠림현상이 있습니다. 문제점을 바로 찾아내시는 것도 공력이지요. ^^
• 김평철
• 2007-05-04 00:19:31
• x

• ^^; 제가 너무 소극적이 되었네요.
  화이팅!
• kenu
• 2007-05-04 00:19:36
• x

• 1000개의 요소를 갖는 배열을 생성한다.
  스트림에서 1000개가 될 때까지 순차적으로 채워넣는다.
  두번째 1000개의 요소는 1/2의 확률로 생존하게 되고 랜덤하게 배열에 삽입한다.
  세번째 1000개의 요소는 1/3의 확률로 생존하게 되고 랜덤하게 배열에 삽입한다.
  스트림이 끝날 때까지 이것을 반복한다.
  
  단점: (스트림의길이 % 1000)가 0이 아니라면 마지막 요소들의 생존확률의 보정이 필요하다.
• 바람따라..
• 2007-05-04 00:25:55
• x

• "바람따라"님... 무서운 공력. 면접하다가 이런 분 만나면 등골이 짜릿함을 느낍니다. ^^
  갯수가 1000의 배수가 아닌 경우는 정식면접에서 보여주실 수 없나요? 실은, 수학적으로 맞는지 증명하는 것도 물어보고 싶은데. 시간되면 1000개씩 처리하지 않고 1개씩 처리하면서 같은 효과를 같는 방법이 있는지도 묻고 싶고...
  흐음... 결국, 우리나라에 유능한 개발자 없다는 것은 헛소리 같습니다. 단지, 이런 분들에게 경력경로를 보장해줄 수 없는 업계현실이 문제이겠지요. 노력하겠습니다.
• 김평철
• 2007-05-04 00:48:11
• x

• "후니"님, 저도 이제 졸려서 후니님의 복잡한(?) 알고리듬을 이해할 수 없군요. ^^ 그러지 말고, 회사에 다시한번 지원하시지요. 이정도의 열정을 저희가 전화면접만으로 탈락시켰다는 것이 실수였을지 모릅니다. (제가 전화면접한 것 아니지요? 설마...).
• 김평철
• 2007-05-04 00:53:55
• x

• 개발팀2번은 수학적으로 다음 문제로 축소해 볼 수 있습니다.
  
  임의의 숫자 연속 S에서 임의의 숫자 Ak를 뽑아야 합니다.
  
  방법은 weighted random sampling을 하면 됩니다.
  
  A1, A2 두개 중에서 임의의 숫자 하나만 골라서 그걸 저장합니다. 그 숫자를 A(2)라고 하겠습니다. 이 숫자가 선택된 확률은 1/2입니다. 이제 A3라는 숫자와 A(2) 중에서 하나를 고르는데, 그냥 고르지 않고 weight를 주고 고릅니다. A(2)는 2를 주고 A3은 1을 줍니다. weight는 룰렛 휠에 화살을 쏠 때 타겟 면적의 개념으로 보면 쉽습니다 -- 예를 들어 0부터 1사이의 랜덤 리얼 넘버를 구하고 [0,2/3)는 A(2)선택, [2/3,1)은 A3선택으로 합니다. 이렇게 하면 이 과정을 통해 얻어진 숫자를 A(3)라고 하면 A(3)가 선택될 확률은 1/3이 됩니다.
  
  이제 A(3)와 A4 중에서 하나를 골라야 합니다. A(3)는 3만큼 weight을 주고 A4는 1만큼 weight을 줍니다. 그러면 역시 이 과정에서 선택된 숫자 A(4)는 무조건 1/4의 확률로 뽑히게 됩니다.
  
  이 과정을 수열의 끝까지 반복합니다.
  
  이 구조를 1000개를 뽑는 문제로 확장하는 것은 "left as an exercise for the reader".
  
  http://agile.egloos.com
• 김창준
• 2007-05-04 01:00:04
• x

• 출근의 압박으로 Z z .
• 후니
• 2007-05-04 01:12:18
• x

• "김창준"님, "바람따라"님이 남겨 놓은 loose-end를 모두 해결하신 것 같군요. 수학적 증명도 거의 straigtforward한 수준까지 된 것 같습니다. 저라면 바로 코딩해보고 싶은 충동이 생기는군요. 그런데, 혹시, multi-thread를 이용한 parallel 버전을 만들 수도 있을까요? 뭐, 하실 필요는 없고, 면접에 오신다면 그렇게 물을 것 같다는 것입니다. ^^
  아, 그리고, 님의 애자일이야기 블로그는 잘 보았습니다. 개발속도는 팀간 커뮤니케이션(연결고리)이 핵심이라는 부분에 100% 동의합니다. 혹시, 큐브리드에 talk해주실 기회를 주실 수는 있는지요?
• 김평철
• 2007-05-04 01:23:08
• x

• "후니"님... 잠자리 들기 전에 한가지 더... 큐브리드는 자율출퇴근시간제, 재택근무제를 시행하고 있습니다. 출근의 압박을 없애기 위해... ^^
• 김평철
• 2007-05-04 01:24:48
• x

• 김평철님. 다른 분들의 답글은 보지 않고 제 글을 작성해서 바람따라님이 어떤 해법을 제시했는지는 모르고 있었습니다.
  
  parallel 구현을 할 수 있냐 없냐는 큰 문제가 아닐 것 같은데(예컨대 N개의 worker thread가 숫자들의 chunk들을 처리하도록 하고 그 결과를 애그리게이터에게 async 메시지 패싱하고 결과를 join해서 다시 worker를 돌리고), optimal한 parallel 구현을 하는 것은 간단한 문제가 아닐 것 같습니다.
  
  사실 이 문제를 푼 것은 큐브리드에 입사할 생각으로 푼 것은 아니고 우연히 okjsp에 들어왔다가 재미있는 문제 같아서 머리를 식히려고 한 번 풀어본 것입니다. 이런 기회를 주셔서 감사드립니다.
  
  원글에 올리신 큐브리드의 프로세스 ppt는 잘 보았습니다. 아주 견고한 프로세스 같다는 생각이 들고 제가 배우고 취할점도 많은 것 같습니다만, 아쉽게도 고객의 관점보다 engineer-centric하다는 면이 조금 아쉽고 cycle-time이 고려된 dash board가 있으면 어떨까 합니다. 그리고 개발자들이 "실제로" 일주일에 평균 몇시간을 근무하는지도 궁금합니다.
  
  꼭 job에 대한 것이 아니더라도 한 번 뵙고 여러가지 말씀을 나눌 기회가 되면 좋겠습니다.
  
  감사합니다.
• 김창준
• 2007-05-04 01:46:37
• x

• "김창준"님, 회사에 지원하기 위해 답변하신 것은 아니라는 것 알고 있었습니다. pckim at cubrid.com으로 연락 주셔서 한번 만날 기회를 주시면 감사하겠습니다. 저 뿐만 아니라 제품팀 직원 모두가 배움으로 굶주려 있습니다. ^^
• 김평철
• 2007-05-04 01:54:36
• x

• 재미난 게 있었네요;; ㅎㅎ;;
• 임은천
• 2007-05-04 04:19:14
• x

• 김창준님// 아주 쉽게 해결되는 문제였군요.
  저는 논리보단 직관이 먼저 움직이는 편이라 논리적으로 재정립하는데 더 많은 노력이 필요합니다.^^
  제가 생각한 걸 아주 쉽고 명확하게 풀어주셨군요. 역시 공부가 부족함을 절감합니다.
  
  제가 접근한 방법은, '결과블럭'에서 블럭 b(1) ~ b(n)이 고르게 분포되어 있다면 b(n+1)이 1/(n+1)*블럭크기만큼 대체한다면 b(1) ~ b(n+1)이 고르게 분포된다는 사실에 기반합니다.
  
  *하나의 블럭을 채우지 못하는 마지막 요소들의 확률보정문제
  스트림에서 읽은 요소의 수를 기록한다.
  나머지가 0이 아닐 때, 마지막 요소들은 각각 (블럭크기)/(스트림의길이)의 생존확률을 갖는다.
• 바람따라..
• 2007-05-04 04:27:05
• x

• package kr.ac.sunchon.random;
  
  import java.util.*;
  
  public class ConstantRandom implements Iterator<Number> {
  private static final int threshold = 1000;
  public int count = 0;
  
  public static void main(String[] args) {
  ConstantRandom rand = new ConstantRandom();
  while(rand.hasNext()) {
  System.out.print(rand.count + " : ");
  System.out.println(rand.next());
  }
  }
  public Number next() {
  double rand = new Random().nextGaussian();
  while(rand < 0) {
  rand = new Random().nextGaussian();
  }
  synchronized (ConstantRandom.class) {
  ++count;
  }
  return rand;
  }
  public boolean hasNext() {
  return count != threshold;
  }
  public void remove() {
  }
  }
  
  여기에서 고객이 만족을 하면, 그냥 둡니다. 하지만, 만족을 하지 않고, 우리 만의 알고리즘을 만들어야 겠다. 라고 한다면, 그 때부터는 Random 관련한 논문과 인터넷 자료를 수집합니다. 여기에서 구현해야 하는 문제는 new Random().nextGausian() 이겠죠. 논문을 읽고 나서 논문에 있는 것을 구현할 것인지 생각을 합니다. 논문에 있는 것보다 더 좋은 게 생각나면 구현할 것이고, 생각 안나면, 일단 논문에 있는 것을 구현합니다. 더 좋은 설계나 생각은 어차피 써봐야 느는 거기 때문에.. 뭐 이건 어쨌든 그냥 제 생각..
• 임은천
• 2007-05-04 04:56:30
• x

• 아
  무슨 말씀들 하시는지 모르겠다
  공부가 넘 부족해 ㅠ.ㅠ
  부끄러버라
• 후니
• 2007-05-04 06:47:30
• x

• 아직 신입이라 공부가...
  아니면 노력이 부족 ㅎ
• 후니
• 2007-05-04 07:59:26
• x

• 유능한 분들이 정말 많으시네요..
  처음엔 구인글이였는데.. 하나의 배움과 토론의 장이 된듯한 느낌이예요.
  이 바닥에 발 담군지가 십년도 더 되었는데...
  업무에 지쳐 무지해진 자신을 발견하니 정말 부끄럽군요.
  자신을 되돌아 보고 앞으로 나아갈 방향을 제시해주셔서 감사합니다.
  창의력과 스킬을 올려 내년쯤 지원해보겠습니다 ^^
• hiherod
• 2007-05-04 08:19:57
• x

• 제가 쓴 위의 리플이 약간 오해의 소지가 있을 수 있는데요..
  마지막 요소들은 각각 (블럭크기)/(스트림의길이) ...
  ==> 마지막 요소들은 각각 (블럭크기)/(스트림의 총길이)의 생존확률을 갖습니다.
  스트림의 총길이는 카운트해서 따로 구하고요.
• 바람따라..
• 2007-05-04 09:55:03
• x

• 김창준 // 써놓은것을 읽다가 제 나름대로 이해를 해보는데 순간 엉뚱한데로 빠져 나갔었습니다..
  A1,A2 중 A(1)을 구하고 A(1)과 A3 중 A(2)를 구하는데 weight를 준다는것을..
  3등분된 다트판에 [A(1)][A(1)][A3] 이런식의 2:1 비중으로 구역을 할당한 상태에서 다트를 던진다는 의미로 해석했습니다. 즉 A3는 A(1) 에 비해 절반의 확율, 전체의 1/3 확율로 선택 되어질 가능을 가지게 되는것이구요.. 그렇게 구해진 A(2)가 선택될 확율이 1/3이 된다는게 이해가 되지 않습니다. A3가 선택될 확율이 1/3가 아닌지요?..
  
  또 하나의 궁금증은 두번째로 구해져야할 A(2)의 값은 A(1)의 값이 될 확율이 2/3가 되며 만약 A(1)의 값이 된다면 A(2) = A(1) 이 되어서 중복되어지는것 아닌지요?
  
  다른분들 답을 안보고 풀려다가 그만 김평철님 댓글을 봐버리는 바람에 같이 보게 되어서 이 의문점에 꽂혀서 답을 못풀고 있습니다 ㅠㅠ
  첨부터 다른의미이었던것인지 다르게도 생각해서 계속 해석할려고 노력중인데..
  음..혹시나 보게되면 ^^ 의미를 한번더 설명해주실수 있는지요?..
• MK.love
• 2007-05-04 11:10:41
• x

• 문재풀다 잼나서
  잠안자고 시간내서 풀어봤는데
  아침에 다른분 해답보니
  부끄러워저서 제 해답은 삭제
  아 부끄러운 아침이었음다
• 후니
• 2007-05-04 11:21:35
• x

• 무섭다..
• 찔러야
• 2007-05-04 11:51:24
• x

• 2번문제는
  우선 최초 1000개를 받고,
  그후 한개씩 받으면서
  1000+1개중 랜덤하게 한개씩 버리면 되겠네요. ㅋㅋ
  잼따. ㅋㅋㅋㅋ
• skyer9
• 2007-05-04 12:46:46
• x

• 아닌가... 1000+"가중치변화준1개"에서 랜덤하게 한개 버려야 하나 ㅡㅡ;;
• skyer9
• 2007-05-04 12:51:59
• x

• 가중치 = 1000/(1000 + n)
  n = 입력받은 전체 수 - 1000
  위 가중치에 의해 새로 들어온수를 사용할것인지 아닌지를 결정하고
  사용할 경우
  이전 1000개중 한개를 랜덤하게 제거하고 배열에 추가하면 될듯 하네요.
• skyer9
• 2007-05-04 13:05:35
• x

• 바람따라// 지금보니 님이 한거하고 똑같네요.
  댓글이 넘많아 보지도 않고 써버렸네요. ㅡㅡ
• skyer9
• 2007-05-04 13:07:31
• x

• skyer9님, 예, 그래야 할 것 같은데요? 결국, 새로 받은 1개가 생존할 확률은 앞에서 "바람따라"님과 "김창준"님이 정리한 대로 1000/<지금까지 본 갯수>일 것이고, 그렇게 해서 생존된다면 기존의 1000개 중 무작위로 하나를 버리면 될 것 같습니다.
• 김평철
• 2007-05-04 13:08:47
• x

• 네 가중치에 대한 검증은 실제 프로그램을 작성해서 확인해야 겠지만요. ^^
• skyer9
• 2007-05-04 13:17:01
• x

• 검증방법은...
  1000개를 100개로 바꾸고,
  입력받는수를 랜덤이 아닌 1-10000 의 순차적인 수로 바꿔서
  10000개까지 받은후에 최후 100개를 출력해서 눈으로 확인 ㅡㅡ;;
  
  단순 단순, 내머리는 넘 단순해 ㅡㅡ;;
• skyer9
• 2007-05-04 13:22:46
• x

• skyer9님, 아니 위에 모든 분들... 큐브리드에 지원할 생각 없어요? 원래 채용하려고 올린 글인데... ^^ ^^
• 김평철
• 2007-05-04 13:24:46
• x

• 김평철 // 흠 제가 적은 댓글에 대해서도 확인이 가능할러진요?.. 김평철님 께서는 김창준님이 하신 말씀을 이해하고 계신듯 한데.. 제가 다른측면으로 해석을 해서인지 아니면 최초 문제를 잘못 이해해서인지.. 선뜻 의미가 이해가 가질 않네요
• MK.love
• 2007-05-04 13:25:50
• x

• 1번 문제 O(1)인 알고리즘을 생각해봤습니다.
  
  --------------------------------------------------
  사용자마다 크기가 n인 배열 2개(X,Y), 크기가 2인 배열 1개(Z)를 가지고 있게 하고...
  
  포인트 [i,j]를 선택 할 경우
  
  X[i]++, Y[j]++, 만약 [i,j]가 대각선에 위치했으면 Z[a]++
  (Z[0]:오른쪽 상향, Z[1]:오른쪽 하향이라 정의합니다.)
  
  상대방 X[i]--, Y[j]--, 만약 [i,j]가 대각선에 위치했으면 Z[a]--
  
  내 X, Y, X 중 count가 n이면 승리
  --------------------------------------------------
• 조영운
• 2007-05-04 13:32:25
• x

• int[] block = new block[blockSize];
  for (int value, n = 1; (value = stream.getNextNumber()) > -1; n++) {
  int randomValue = (int)(n * Math.random());
  if (randomValue < blockSize) {
  block[randomValue] = value;
  }
  }
• 바람따라..
• 2007-05-04 13:43:02
• x

• 공지사항에 왠 [구인]이란 글이 올아와있나 했더니..
  오옷 +_+.. 좋군요~
• 옆차기
• 2007-05-04 14:08:40
• x

• 제가 생각한 답만 산으로 가는거 같네요
  
  long [] main_array = new long[1000]; // 분포된 수열을 넣을 배열
  long [] temp_array = new long[999]; // 조정되는 수열을 임시로 넣어둘 배열
  int set_point, del_point; // 값을 삽일할 위치와 버릴 위치
  long return_num,split_num; // 복귀된 수를 임시로 넣어두는 변수
  저는 1000번째까지는 main_array에 차곡차곡 넣고
  10001번째부터 return_num에 넣어두고
  java.util.Arrays.binarySearch(main_array,return_num) //이하 binarySearch()
  로 들어갈 위치를 찾아 set_point에 넣습니다.
  그후 main_array[0]값과 main_array[99]의 값의 합을 2로 나누어
  split_num에 넣습니다.
  그값의 위치를 binarySearch(main_array,split_num)로 찾아서
  그 값을 기준으로 양 길이를 비교하여
  긴쪽의 최소값과 최대값의 평균으로 다시binarySearch()를 반복합니다.
  {//만약 복귀값이 split_num을 기준으로 밀도가 높은쪽이면 스킵
  (예를들어 main_array[30]라면 중간값이 앞쪽에 위치
  즉 뒤쪽의 배열이 밀도가 높으로 binarySearch를 반복하여 버릴 위치를 찾습니다)
  최종적으로 찾아진값을 del_point에 넣고
  main_array[del_point+1]부터 main_array[set_point] 까지의 배열을
  temp_array에 넣은후 main_array[del_point]부터 temp_array를 덮어씁니다.
  }
  그후 main_array[set_point = return_num 후 음수가 나올때 까지반복합니다.
  이 방법이 않좋은 방법인가요?
• 후니
• 2007-05-04 14:37:56
• x

• 델마당에서도 활발하게 토론중입니다(...)
  
  아래는 제가 짠 의사 코드. (파스칼 문법입니다--;)
  
  Const
  ArrayMax = 1000;
  DataCnt = 100000;
  var
  DataArray : Array[1..ArrayMax] of Integer;
  ArrayCnt, I : Integer;
  begin
  ArrayCnt := 1;
  for I := 1 to DataCnt do
  begin
  if ArrayCnt <= Length(DataArray) then
  begin
  DataArray[ArrayCnt] := I;
  end else
  begin
  randomize;
  if Random(ArrayCnt) > (ArrayCnt - Length(DataArray)) then
  begin
  DataArray[Random(Length(DataArray))+1] := I;
  end;
  end;
  inc(ArrayCnt);
  end;
  end;
  
  분포를 보기 위해서 1부터 100000 까지 순차적으로 넣어 봤습니다.
• PE
• 2007-05-04 17:03:15
• x

• bool IsWinningMove(int **board, int row, int column)
  1. 가로계산
  row 번째 가로의 체크된 가로인덱스의 합 % N 이 == 0 true
  else
  2. 세로계산
  column 번째 세로의 체크된 세로인덱스의 합 % N 이 == 0 true
  else
  3. 대각
  체크된 대각인덱스의 합이 ( 가로든, 세로든 ) == SUM( 1 ~ ( N-1) ) true
  else
  false
  
  이럼 될꺼 같은뎅
• simz
• 2007-05-04 17:30:26
• x

• simz님//인덱스의 합 % N 하면...
  
  n이 4면
  인덱스가 0부터 시작 할 경우 : (0+1+2+3=6)%4 = 2
  인덱스가 1부터 시작 할 경우 : (1+2+3+4=10)%4 = 2
  
  false
  
  이렇게 되는거 아닌가요?
• 조영운
• 2007-05-04 17:37:09
• x

• 음 가로계산때는 가로 인덱스 만 합하고
  세로계산때는 새로 인덱스 만 합친다 는의미였습니다.
  
• simz
• 2007-05-04 17:44:14
• x

• 1. 배째
  2. 배째
  3. 배째
  4. 배째
  5. 배째
  6. 배째
  모두 해결하였습니다. 연봉 1억주세요
  어느 플젝이건 배째는 사람 있어야 합니다. ^^
  6월달 부터 뭐하징.....^^ 배째,,,,,
• nettop
• 2007-05-04 17:51:43
• x

• simz님// 4x4게임에서 지금 [2,3]을 체크했다면...
  
  index가 2인 row에서 체크된 column index 들을 더하고,
  index가 3인 column에서 체크된 row index 들을 더한다는 의미시죠?
  
  그렇다면, index가 2인 row에서 모든 column이 체크 되어 있어야 승리하는데...
  그렇다면, column 인덱스들의 합은 0+1+2+3 = 6 이고...
  (6 % 4 = 2) != 0 이기 때문에 승리가 아닐까 하는 질문이었습니다.
• 조영운
• 2007-05-04 17:57:24
• x

• n=4 이면
  [2,3] 이면
  가로 2+2+2+2 % 4 == 0 이면 승리
  세로 3+3+3+3 % 4 == 0 이면 승리
  대각 0+1+2+3 == SUM( 1 ~ ( 1-N ) ) 이면 승리
  이런뜻입니다.
• simz
• 2007-05-04 18:02:41
• x

• simz님// 인덱스의 합을 이해했습니다. ^^
• 조영운
• 2007-05-04 18:06:32
• x

• 영훈님
  (3,0),(3,1),(3,2),(3,3) 일때 (3,0)과 (3,2) 만 체크되어고 % 4 == 2 이기뗌에 모두 합치는것은 안되는것 같아요.
• simz
• 2007-05-04 18:11:28
• x

• 틱택토는... 사실 (2n+2)n 회 비교라고 생각했는데 설명을 잘 읽어보니
  최대 3n 회 비교 였네요
  n이 홀수인 경우에는 네 귀퉁이와 정 중앙만 3n회이고 나머진 2n회 비교
  n이 짝수인 경우에는 네 귀퉁이와 중앙의 네개만 3n회이고 나머진 2n회 였네요
  역시 시험문제는 잘봐야
  ㅡ,.ㅡ
  덜렁덜렁~
• 죠쉬
• 2007-05-04 18:42:07
• x

• 음음... 도배도배...
  다른건 잘 모르겠는데... 개발 프로세스가 잘 잡혀 있는 회사라니 부럽네요
  프로젝트 일정에 쫓겨 개발 프로세스는 늘 뒷전인데
  부러워요~
• 죠쉬
• 2007-05-04 18:43:20
• x

• 음... 2번문제...
  n개중에 1000개를 선택하는 문제가 아니라
  n개중에 1000개를 남기고 나머지를 쫓아내는 문제였던거 같네요
  예를들어 1번부터 1000번까지가 100%들어간다면
  1001번부터 2000번 까지는 50%확률에 수렴되는 확률을 갖게하고 배열에 넣으면 되겠죠
  그럼 있는놈들은 대략 1/2000 에 수렴되는 확률로 쫓겨날거고
  들어가는 놈들 역시 1/2000에 수렴되는 확률로 배열안의 특정위치에 입성할 수 있겠죠
  결국 n번째 놈이 배열안에 들어갈 확률은 대략 1000/n 이 되겠죠
  그리고 n번째 놈이 들어갈때 있는 놈들은 동일하게 1/1000의 확률로 쫓겨 나갈겁니다.
  다시 이야기 하자면 먼저 들어온 놈이 쫓겨날 확률은 뒤로 갈수록 점점 낮아지게 될거구요
  쫓아낼 놈을 랜덤하게 선택한다면 나중에 들어온놈은 먼저들어온 놈보다 수가 적으니
  쫓겨날 확률이 먼저들어온 놈보단 낮을거구요
  먼저 들어온 놈들도 쫓겨나다 보면 수가 점점 적어져서
  결국엔 나중에 들어온 놈들과 같은 확률로 쫓겨나겠죠
  이 문제를 수학과에 던져줬더라면 훨씬 더 많은 사람들이 풀었을 거라는 생각이드네요
  이런문제를 많이 해결해야 한다면, 프로그램 짤줄 모르는 수학과를 데려다가
  교육시키는것도 괜찮지 않을까 싶은데요 ^^;;
  프로그래머를 뽑기 위한 문제로는 약간 부적절했다라고 생각되는데요
  ㅡ,.ㅡ
  다시 읽어보니 약간씩 틀려서 수정하고, 또 수정한다음에
  메모장으로 옮겨서 다시 수정해서 올렸습니다.
  덜렁덜렁~
• 죠쉬
• 2007-05-04 18:55:49
• x

• 뒤늦게 김창준님의 알고리즘을 봤습니다...
  먼저 푸셨군요 ㅡ,.ㅡ 부끄~
  그런데 "left as an exercise for the reader" <- 이게 뭔 뜻인가요?
  해보라는 건가요? 아님 다른 뜻이 있는건가요?
• 죠쉬
• 2007-05-04 19:15:55
• x

• 개발팀 2번 문제의 요지는 모든 stream이 같은 확률을 갖도록 해야한다 같습니다.
  스트림의 갯수가 n개라면 모든 스트림이 배열에 들어갈확률 1000/n을 가져야하겠죠.
  그렇기 위해선
  먼저
  1~1000개의 스트림을 배열[1000]에 넣고
  1000번째 이후의
  n번째의 스트림부터
  1000/n의 확률을 부여하면 됩니다.
  
  그렇기 때문에 새로운 n번째의 스트림이 들어오면
  
  랜덤함수를 사용해서 1000/n 보다 클경우 false ---> 새로운 스트림 삽입않음
  다음 스트림으로 ....
  
  1000/n 보다 작을 경우 true ---> 새로운 스트림 삽입
  
  기존의 배열에서 1/1000 의 확률로 1개의 스트림을 선택후 그위치에 n 번째 스트림을 삽임하면 가능할것같습니다.
  
  이렇게 되면 모든 스트림의 삽입 확률이 같아지겠죠.
• 효준
• 2007-05-04 19:51:29
• x

• 부끄럽지만 수학과 출신이라 저 문제 새벽 4시경까지 생각 했는데..
  아직도 저 문제 자체를 이해 못한거 같습니다.
  stream의 특정 지역에 집중되면 안된다는 말에... 전 표준 편차의 값이 작아야 한다고
  생각 했었습니다.
  1 1000개의 값 중에 max, min, avg 값을 구한다.
  2 1001번째 입력 받는 수가 max, min 보다 크거나 작은지를 검사한다.
  3 max 값보다 크거나 min 값보다 작은 값이면 무조건 입력 한다.
  4 버리는 수에 대해서는 평균 값을 구해서 이진트리 검색을 응용해서
  평균 값을 기준으로 어느쪽에 분포 갯수가 많을지를 찾아서... 이걸 재귀 용법으로
  찾으면 가장 밀접 되어 있는 구간을 찾을수 있지 않을까 생각 했습니다.
  5 물론 1000개의 데이터가 같은 분포도 등차 수열 같은 분포도를 가질 경우는
  random 방식으로 하나를 버린다. 단 max,min은 제외
  대충 이런식으로 생각 했습니다만... 위에 문제 푸신 분들과 너무 달라서
  쪽팔려서 지웠습니다.
• 수학과출신
• 2007-05-04 19:54:04
• x

• 흠 저도 '수학과출신' 님 말처럼 문제 자체를 이해못하고 표준편차값이 작아야 한다
  또는 1 ~ 1억이면 1000개의 숫자는 골고루 분포해야 된다라고 받아들였습니다.
  그러다 '김창준'님 말을 얼핏보고 읽어가다 댓글이 오타같기도 하고 갑자기 아리송해져서 ㅡ.ㅡ 급헷갈리기 시작 -0-;; 갸우뚱하다 '바람따라'님의 댓글이랑 몇개의 댓글을 프린트해서
  집에오는 쟈철안에서 읽어보고는 바로 이해가 오더군요 ㅠㅠ
  결국 모든 스트림들이 같은 확률로 선택되어져야 한다는게 문제의 뜻이었음 ㅡㅡ;;
  
  이제 문제를 풀려고 해도 답을 알아버려서 -0-;; 풀기도 힘드네요 ㅠㅠ
  완전 색 다른방법을 연구해도 원리는 같을거 같고 ㅎ
  고수분들 많으시네요 ㅎㅎ 바로바로 답이 나오시공 ㅎㅎ
  내공을 더 쌓아야 겠습니다 ^^
• MK.love
• 2007-05-04 20:32:08
• x

• 수의 분포가 아닌 스트림의 분포도 이군요.
  ㅠ.ㅠ 완전 좌절 모드네요.
  문제 자체도 이해를 못하다니.. 언제 초보를 벗어 날지... 부끄럽네요.
• 수학과출신
• 2007-05-04 20:45:01
• x

• 오 2번 문제 재밌습니다. 화장실에 앉아서 생각했는데 가중치 부분이 핵심이군요. 값을 고루 분포시키기 위해선 반드시 가중치가 필요하군요. 처음엔 weight이 뭔지 한참 생각했다는...^^ 다만 스트림의 길이를 알 수 있다면 미리 가중치를 설정할 수 있지만 모르기 때문에 김창준님 답변같이 1씩 증가하는 가중치를 적용해야 하네요. n번째 1000개 스트림일 때, 타겟이 되는 1000개의 가중치는 n, 바꿀 소스 스트림의 가중치는 1... 역쉬~ 가중치는 발생시킨 난수값에 배수룰을 적용하면 돼겠네요.
  위에 두분~ 수정하는데 웬 리얼댓글? ^^
• 힘내자!
• 2007-05-04 20:47:13
• x

• 공고 올린지 이틀만에 조회수 2천 돌파, 댓글 70 돌파... 제가 이것을 어떻게 해석해야 할지... 어줍잖은 문제라 생각했는데, 이렇게 많은 개발자들을 자극할 줄은 몰랐습니다. 그 만큼 국내에는 실력도 좋고 열정도 많은 개발자가 많다는 뜻이겠지요? 그럼에도 불구하고 국내SW사의 개발자 조직문화는 걸음마 수준... 다시 한번 책임을 느끼는군요. 많은 관심에 깊은 감사드립니다. 저는 월요일 온라인 입사지원이 몇건이나 왔는지 기대하고 있겠습니다. ㅎㅎㅎ
  좋은 주말 되십시요.
• 김평철
• 2007-05-04 22:09:37
• x

• 아마 조회수 2~300개는 제가 올린거라 생각이 ㅡㅡ;; 문제의 뜻에 관련되서 질문드려놓고..
  답변이 나오길 기대하며 계속해서 리프레쉬 한지라..
  (사설로.. 저도 저희 회사 모집공고 올려놓고 엄청난 조회수와 댓글에 엄청 당황했습니다..ㅎ)
  딸리는 실력으로 어디 한번 과감히 지원해볼까하지만.. 이직한지 몇달되지않아서..고민이 많이 되긴하네요^^ 딴회사들은 오~괜찮네 하고 넘어갔는데.. 김평철님의 댓글에서 솔직히 개발자들을 인정해주고 제대로 대우해줄것같은 포스가 느껴지는데다 개발을 즐기면서 할 수 있다는 말에도 들뜬 마음 가라앉히지 못하고 있구요..~^^
  좋은 사람 많이 구하시고 발전하시어 국내SW사의 하나의 파동을 일으켜주시길~^^
• MK.love
• 2007-05-04 23:04:40
• x

• 아 퇴근후 여적 혼자 삽질하면서
  제가 생각한 방법으로 코딩해서 해답을 찾아봤는데
  분포가 양끝쪽으로 밀집하는 경향이 있네요
  수정하다가 이방법으론 안될거 같아서 ㅈㅈ
• 후니
• 2007-05-05 00:23:14
• x

• 죠엘테스트 12점만점이라니 부럽습니다.^^
  저번 코엑스 발표 때 개발 및 관리 프로세스를 보여주셨는데...
  정말 좋아 보였습니다. (특히 발표 처음에 해외 유명 벤더들 마크를 깨버릴때 정말 짜릿..ㅋㅋ)
  이번 7.0은 너무 만족스러웠습니다.
  Oracle이 점령한 대용량 DBMS시장에 파란을 일으켜주세요~!!
  소프트웨어 엔지니어들이 대우 받을 수 있고
  한국산 고품질 소프트웨어가 많이 생겼으면 좋겠습니다.
  대한민국 개발자 화이팅~!!
• Log4J
• 2007-05-05 00:45:02
• x

• 아 수의 분포가 아니고 스트림의 분포인가요
  왜 해답이 산으로 갔나했는데
  문재부터 이해를 못했네요
• 후니
• 2007-05-05 02:34:47
• x

• 2차시도 아잣
• 후니
• 2007-05-05 05:31:50
• x

• 1번 문제는 현재 위치를 기준으로, 가로/세로/대각선을 검사해 주면 될 것 같습니다.
  중복 포문이 없으므로 O(1)이라고 하면 맞을라나 모르겠네요 ;;
  
  bool IsWinningMove(int** board, int row, int column)
  {
  
  // save value of cell;
  int currentValue = board[row][column];
  
  
  // check column
  int count = 0;
  for(int i=0; i<N; i++)
  {
  if(board[row][i] == currentValue)
  count++;
  }
  
  if(count == N)
  return true;
  else
  count = 0; // reset
  
  
  
  // check row
  for(int i=0; i<N; i++)
  {
  if(board[i][column] == currentValue)
  count++;
  }
  
  if(count == N)
  return true;
  else
  count = 0; // reset
  
  
  
  // check diagonal
  for(int i=0, j=0; i< N; i++, j++)
  {
  cout << board[i][j];
  if(board[i][j] == currentValue)
  count++;
  }
  
  if(count == N)
  return true;
  else
  count = 0; // reset
  
  
  for(int i=N, j=N; i>0; i--, j--)
  {
  if(board[i][j] == currentValue)
  count++;
  }
  
  if(count == N)
  return true;
  
  return false;
  }
  
  2번 문제의 핵심은 끝을 모르는 데이터(스트림) 에서부터 어떻게 고른 분포(모든 데이터를 다 포함할 수 있는)의 표본을 얻느냐 라고 해석했는데 맞게 해석을 한건지 모르겠네요 ..
  
  끝을 모른다면 결국 일정한 크기로 잘라야 할 것 같습니다.
  
  가정치.
  #데이터의 크기 = 2,500
  #버퍼의 크기 = 1,000
  
  위와 같이 가정할때.
  
  먼저 버퍼를 2개 둡니다.
  
  First. 값을 읽어서 첫번째 버퍼를 먼저 채웁니다.
  Second. 값을 읽어서 두번째 버퍼를 마저 채웁니다.
  
  두 버퍼가 모두 가득 차게 된다면(데이터가 더 남아있다면)
  
  1. 첫번째 버퍼를 고르게 분포시킨 후 절반을 버립니다.
  2. 두번재 버퍼의 고르게 분포시킨 후 절반을 버립니다.
  3. 첫번째 버퍼로 두번째 버퍼를 복사시킵니다.(첫 버퍼는 1000개 유지)
  4. 두번재 버퍼를 다시 채워줍니다.
  
  만약 두번째 버퍼가 가득 찼다면 1번으로 돌아가 반복합니다.
  그렇지 않다면,
  
  _1. 두번째 버퍼를 고르게 분포시킵니다.
  _2. 첫번째 버퍼와의 비율을 고려하여 둘을 합쳐줍니다.
  
  _3. 결론적으로 N 개에 데이터에 대한 목표치 평균값 1000을 찾아줍니다.
  
  
  어째 허접하네요 ;;;
  정식으로 수학 공부를 안해서인지 멋지게 설명을 못하겠네요^^;;
  
  항상 알고리즘을 고민하며 코드에 만족하는 프로그래머가 되고 싶었는데 ..
  실력만 된다면 꼭 지원해 보고 싶은 회사네요 ..
  
  한 1년 경력 쌓고 도전을 ;;
  
  언제 IT 뉴스에서 국산 DBMS 오라클을 누르다!
  뉴스 한번 기대해 보겠습니다.
• blueiur
• 2007-05-05 06:47:39
• x

• 진행 과정을 살펴보고 있습니다.
  
  저는 답에 문제 해결의 시발점으로써 Java의 Random클래스를 Wrapping하는 것으로 잡았습니다.
  이런 책을 참고할 수 있겠더군요.
  
  http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521474655
  
  패러럴에 대한 답은 적지 않았는데, 사실 제가 적은 답에는 결과를 저장하는 공간을 만들지 않았습니다. 이는 패러럴 때문이죠. 패러럴을 처리하기 위해서는 단일 노드 컴퓨터에서는 의미가 없고, linux의 MPI API와 같은 구현을 해야 합니다. 즉, 전체 노드의 중간에서 스케줄링과 락을 관리해주는 메시지 처리자를 두고, 여러 노드 간의 자료를 합산해서 결과를 합쳐주는 식의 API가 존재해야 한다는 뜻입니다. 이것은 저도 아직 하드웨어와 OS에 그리 자신이 없어서 쉽게 하지는 못하겠습니다.
  
  김창준 님께서는 쉽다고 하셨는데, 내공이 대단 하신 것 같네요. 제 지금 수준으로는 솔직히 어렵군요. 5년 뒤라면 어느 정도 가능할 것 같습니다.
  
  서비스를 생각한다면, 알고리즘 만으로만 따질 것이 아니라 실제 하드웨어와 OS 측면도 고려 해야 하겠죠. 알고리즘을 만드는 것 자체가 서비스하기 위하기 때문에, SOA 적인 관점에선 그러합니다. 위의 질문은 DBMS를 만들기 위한 질문이겠죠. 특히 제가 풀려고 했던 문제는 DBMS에서 사용자에 대한 응답을 할 때 특정 Disk 영역에 IO를 집중시키지 않기 위해서 Random 함수를 만들려고 하는 것으로 보입니다. 다만, 스트림이라는 것은 버퍼를 사용하게 될 것이고, 이 안에서 Random을 잡는다는 게 서비스 관점에서 어떤 의미를 두고 하는 건지 잘 모르겠군요. 디스크 IO 쪽이라면, 확률적으로 수를 감소시켜가는 것은 끝으로 가면서 IO에 대한 응집이 더 될 수밖에 없지 않은지요.
  저수준 IO를 하더라도 메모리 주소로 접근을 할 것인데, Random을 통해 나온 값을 어떻게 주소에 Mapping하는 것인지 궁금합니다. 직관적으로 수를 분할 시키는 과정은 나선형의 모양을 만들 것이다라고 추측합니다. ConstantRandom 형태입니다. 수학적 해결이 시스템적 해결이 될 수 있는 기반이 되지만, 여전히 넘어야될 산은 많군요..
• 임은천
• 2007-05-05 13:10:41
• x

• 임은천님, 큐브리드에서 일해 보실 생각 없으신지요?
  참고로, 저희 면접은 DBMS와 무관하게 합니다. 위의 문제도 문제해결 능력, coding 능력 등 기초적인 경쟁력을 시험하기 위한 것이지 DBMS 회사라서 선택한 것은 아닙니다. 유능하고 열정이 있는 개발자는 6개월 후면 어느 분야든 전문가 수준이 되는 것을 저는 수도 없이 보아왔습니다. 실제로 큐브리드 엔진을 만드는 핵심 개발자 중에는 DBMS와 전혀 관계없는 전공자도 많습니다. 저희의 인력관리 목표도 개발자의 성장이지 아는 지식을 써먹는 것이 아닙니다.
• 김평철
• 2007-05-05 19:11:01
• x

• 말씀 감사합니다. 저도 가고 싶지만.. 대학원 졸업할 때까지는 교수님을 도우면서 경력과 경험을 더 쌓고 개인적으로 하고 싶은 공부를 한 후에 나중에 뵙도록 하겠습니다.
• 임은천
• 2007-05-05 20:52:30
• x

• 저도 함 해봐야지 하다가,
  강의 준비 때문에 미루던 차에 잠자다가 갑자기 생각나서 정리해봤습니다.
  
  풀이?? 증명은 http://ryujt.springnote.com/pages/208012 에 올려놨습니다.
• 꿈꾸는바보
• 2007-05-06 00:46:46
• x

• 큐브리드..좋은 회사라고 들었습니다.
  
  같이 자바공부한 친구중에 저기 들어간 친구가 있는데
  
  다들 초봉 1400~1800할때 그친군 2700+-로 들어가더군요
  
  그후 진짜 열심히 일하고 회사에 대한
  
  자부심 넘쳐 흘러서 보기좋더군요.
  
  뭐 가끔 술먹다가 회사가 코스닥우회상장때문에 잘못돈쓴애기할땐 열불나 하지만 기타 회사내
  
  분위기라든가 비전 같은거 애기할땐 참 좋아보였습니다.
  
  최근에 듣기로는 네이버도 중하단에서 사용하던 기존db들이 큐브리드로 바뀐다고 들었습니다.
  
  기타 공공기관에서도 많이 들어가고 있는중이구요
  
  전 지금 다른플젝 한창 진행중이라 아쉽게 지원못하지만
  
  제가 알기론 저기서 이런식으로 뽑는것도 첨이라고 들었는데
  
  다른분들 들어가심 어중간한 si업체에있는것보다 훨씬 나을거라고 생각듭니다.
• 웅
• 2007-05-06 22:16:34
• x

• 6개월 후면 그렇게 된다고 저도 확신합니다.. CTO님..^@^
• Log4J
• 2007-05-07 00:14:33
• x

• 아... 큐브리드...
  
  유니sql에서 변신을 시도한 이래 좋은 모습을 보여주는것 같습니다.
  
  저도 DB와 비슷한 (트랜잭션이 빠진) 제품군(검색엔진)을 개발하는 개발자로서...
  
  개발자의 로망을 꿈꾸는 회사가 큐브리드가 아닌가 생각이 됩니다.
  
  (솔직히 티맥스는 로망이 아니라 욕망으로 느껴지는 회사입니다...)
  
  좋은분 많이 지원했으면 좋겠군요...
  
  오픈된 것을 써본 입장에서 좀 아쉬운점은...
  
  국산은 품질이 떨어진다는 선입견을 깰 수 있는...
  
  좀더 세밀한 퀄리티를 올리는게 무엇보다 중요한것 같습니다.
  
  제품기획/개발자의 귀차니즘 하나가 사용자에게는 큰 아픔이 된다는거... 너무 뼈저립니다...
• 세영아범
• 2007-05-07 01:06:33
• x

• 개인적으로...
  네이버에 님의 이름을 검색해봤다는 ㅡㅡㅋ
  솔직히 말해서... 넘 기대 마세요. 지금의 수래기같은 상황에
  좋은 개발자들은 많이 사라졌어요.(다른 분야로)
  
  그럼에도 신규 개발자들은 계속 충전되고 있고(개발의 매력!!)
  그 신규 개발자들을 잘 발굴하시길 바랍니다.
  아... 물론 지금의X같은 상황을 참고 계속 개발을 하고 있는 분들도
  있고요.
  
  여튼 개인적으로 좋은분과 온라인 상으로라도 대화한거
  감사히 생각합니다. ^^
• skyer9
• 2007-05-07 01:40:38
• x

• 오랫만에 코딩의 즐거움에 빠져 봤네요, 맨날 그림만 그리다보니 코딩이 즐거웠다는 사실 자체를 잊어버리고 있었는데... 이런기회를 마련해주신 (의도적이든 아니든) 김평철님께 감사드립니다.
• 죠쉬
• 2007-05-07 08:36:17
• x

• 저도 감사드립니다.
  저도 퀴즈푸는 맘으로 금요일날 퇴근후 2시까지
  저의 엄한해답으로 구현을 해봤습니다.
  간만에 머리가 핑핑 돌아가는 느낌 좋았습니다.
• 후니
• 2007-05-07 08:57:10
• x

• 그냥 저 문제 풀고 구글 지원하십시오. 구글도 저런 비슷한 문제로 채용합니다.
  근데 구글은 연봉 1억은 진짜 우습고 그보다 더한 환상적 사무실 환경이 기다립니다.
  무한음식제공, 무한시간자유, 무한대규모시스템등등..
• 구글빠
• 2007-05-07 09:47:38
• x

• 저도 지금 쉬면서 취업을 준비중이다가 우연찮게 글을 보게되어 나도 모르게(개발자의오기??) 생각을 하고 있네요..ㅎㅎ 그런데 이글을 읽으면서 참 이제까지 제가 개발자로서 살아왔지만(현재 7년?楹六?.세월빨러) 이렇게 깊게 생각해보면서 일을 해본적은 별로 없는거 같네요..
  처음시작할때는 개발에 대한 희망도 있었고 오기도 있었는데 세월이 지나면서 개발자로서의 회의만 남을뿐..ㅠㅠ
  저만 이렇게 살아온건지..푸념만 하네요..ㅎㅎ
  
  50이넘어 개발할 수 있는 회사라니 궁금해 지기도 하네요.
  
  여기 글남기신분들 보면 역시 대한민국 개발자들의 포스를 다시 한번 느끼네요.
  저도 취업준비중이라 도전해 보고 싶긴 하네요..ㅎㅎ
  3시간 인터뷰에서 과연 내가 가진 것을 프로그램이 아닌 말로 표현을 잘할 수 있을까?
  고민 많이 되네요..ㅋㅋ
  
  요청하신 질의에 대한 답이 아니 푸념만 하고 가네요..ㅋ
  
  이제 문제 풀러 ㅋㅋ 오랫만에 머리굴려가면서 고딩한번하겠네요..
  맨땅에해딩만 해온 프로그래머라 ㅎㅎㅎ
  
  모두들 대한민국이 개발자로서 긍지를 가집시다..아자 화이팅
• mymee
• 2007-05-07 10:07:04
• x

• 흠.. 첨에는 전혀 이해할수 없었는데....
  
  글들을 계속 읽다 보니 조금식 이해가 됩니다..
  
  우선 문제 자체... 국문을 이해할수 없다라는 이유로... 역시 난 이것 봤에 안되나 싶었습니다.
  
  휴..그래서 시간 날때 마다.. 다시 읽고 다시 읽고 하다 보니...
  
  문제가 다시 제 머리에 그려 지더군요.. 아직 초보라서... 해결할수 있는게 없지만.. 적어도... 아.. 개발의 로망이 저런 문제로 저를 설레게 하고 그런 것들을 하나하나식 풀어 가는 모습이 아닐까 생각해보았습니다.
  
  좋은 모습 보고 갑니다.. 모두 행복하세요.
• 아름다운음악
• 2007-05-07 10:40:54
• x

• 왜 랜덤을 만드는데 랜덤함수를 쓰려고 하는 걸까요..ㅡㅡ?
• asdf
• 2007-05-07 11:59:01
• x

• 오홋.
• 전관장
• 2007-05-07 17:11:19
• x

• 공지사항은 처음 봤는데 글도 좋고 답변도 좋고..~~
  저도 2번을 봤는데 어떻게 구현할 지는 감이 잡히는데..
  설명이 더 어렵게 느낀건 저 뿐인가요..이넘의 용어에 약한 초보 개발자 ㅡㅡ;;
  많이 배우고 갑니다..~~
• 고흐
• 2007-05-07 18:33:33
• x

• int AVIL_BUF_SIZE; //버퍼 크기
  int arr[1000] //결과가 저장될 1000개의 배열
  int* buf; //버퍼
  int bufsize; //읽어온 버퍼 크기
  int tmpsize = 0; //사용된 stream값
  
  (1). buf에 stream에서 읽어온 값을 buf의 AVIL_BUF_SIZE까지, 또는 stream의 끝까지 넣는다. (bufsize = 읽어온 수)
  (2). for(i=0;i<1000;i++;) arr[i] = buf[random(bufsize)];
  (3). buf를 비우고 (1).항목 처럼 이후의 stream에서 값을 읽어온다. (tmpsize += bufsize)
  (4). t = (1000*bufsize+.5)/(tmpSize+bufsize);
  for(i=0;i<t;i++;) arr[random(1000)] = buf[random(bufsize)];
  (5). (3).부터의 과정을 stream이 끝날때 까지 반복 한다.
  
• 신동엽
• 2007-05-08 11:29:52
• x

• 아.. (2).에서 스트림이 끝났으면 바로 종료와, t가 0일때 예외처리를 안했군요.
  뭐.. 위분들 내용과 크게 차이가 없는듯.
• 신동엽
• 2007-05-08 11:36:32
• x

• 뭐.. 가용 버퍼가 없거나 buf를 꽉 채웠을때도 t가 0이 될만큼 buf크기가 작다면.. 효준님 방법이 제일 좋을것 같네요...
  
  역시 답보고 문제풀기는 의미가 없다는.. ^_^
• 신동엽
• 2007-05-08 11:41:48
• x

• 주로 쓰는 로직만 쓰다보니 쉽지가 않네요^^;
  암튼 좋은내용 잘 배웠습니다.
  그런데 개발쪽 얘기밖에 없어서 PM쪽에 꼬리하나 달까합니다.
  SI라면 제품의 범위가 명확하지 않아서 고객의 당혹한 요구사항이 나올수 있는경우가
  한두가지가 아니지만, DBMS라면 어느정도 제품의 범위가 명확히 설정되어 있으므로
  고객과 첨예한 의견충돌이 나는 경우는 제품의 범위를 넘어서는 요구를 고객이 했을경우와
  제품설계 기초를 흔드는 요구사항일거라 생각됩니다.
  전자의 경우는 고객을 어떻게 설득시킬것인가를 중심으로 접근하는게 좋을 것 같고,
  후자라면 비용대비 고객과 제품이 얻을수 있는 이득과 손실에 대해서 따져보고
  접근하는것을 좋을것 같습니다.
  문제를 인식하고, 거절할것인지 타협할것인지 수용할것인지 판단하고,
  대응을 합니다.
  대응은 아주 고단수의 심리적, 정치적 기술이 필요하므로
  많은 경험을 필요로 하지요^^
  
  두번째 문제는 mssql 의 top 키워드처럼 rand 5 요렇게 하면 좋겠네..ㅋ
• 박종복
• 2007-05-08 17:34:09
• x

• 아, 참고로, 저희가 말하는 PM은 보통 국내 SI업체에서 말하는 PM (project manager)가 아닙니다. Joel on Software에서도 언급되었고, 저희 회사 개발프로세스 자료 (홈페이지의 ITrack 코너 참조)에서 언급된 "program management"입니다. PM은 팀장(관리)이 아니고, 제품과 사용자간의 인터페이스 역할을 합니다. 즉, 고객의 목소리를 제품개발로 끌어들이고 (스펙작업), 제품 릴리스를 관리하며, 제품관련 대 내부(예, 기술지원, 마케팅), 외부(고객) 커뮤니케이션을 담당합니다. 핵심 경쟁력은 커뮤니케이션 (프리젠테이션, 설득, 타협, 협업), 문제해결, 우선순위의 일정관리, 판단력, 결과중심의 업무 등이고, 입사 시에는 필요하지 않아도 조만간 제품의 대하여 누구보다 잘 알고 있어야 합니다. PM 포지션은 미국에서 소프트웨어 분야에 도입된지 10여년 지났고, 이제는 모든 패키지 SW회사가 가지고 있는 포지션입니다. 우리나라의 경우, 많은 경우 팀장(인력관리)이 그 역할을 같이 수행하고 있는 것 같습니다만, 큐브리드는 이를 분리하고 있습니다.
• 김평철
• 2007-05-08 18:36:25
• x

• 드디어 리플이 100개가 넘었네여
  뜨거운 감자입니다.
  
  로또 처음산 심정으로 기다리는중입니다. ^^;
• 후니
• 2007-05-08 19:20:02
• x

• 그 동안 온라인으로 입사 지원을 해주신 많은 분들께 감사 드립니다. 이번 주부터 검토하여 연락드리도록 하겠습니다. 상시 채용이니만큼 (최소한 작년 2월 창업 후 현재까지는 계속 채용 중입니다), 마감날짜 없이 언제든지 관심있으신 분들은 회사 홈페이지 (http://www.cubrid.com)에서 온라인으로 입사지원하여 주시기 바랍니다.
• 김평철
• 2007-05-08 23:10:50
• x

• 와 너무 늦게봐서 @_@
  
  출근해야되는데 재미있게 ?f습니다
  
  2번에 1번 문제 같은경우
  
  마지막으로 돌은 둔 주변부터 검사하는게 퍼포먼스에 좋을꺼 같습니다.
  
  n이 늘어나는거에 비해 루프를 조금 돌 가능 성이 크기 때문입니다 ( 물론 게임의 승리 패턴에 대해서 분석후 이를 기반으로 검색하는게 조금더 좋습니다.)
  
  2번에 2번문제는 많은 분들이 답변해주셔서 생각에 많은 도움이 되었습니다 멋져요 ^_^ㅋ
• 욱이
• 2007-05-15 08:10:56
• x

• //수학과출신
  저도 님이랑 같은 풀이방식으로 접근했는데
  창피해서 지웠음다 ㅋㅋㅋ
  수의 분포가 아니고 스트림에 분포 ㅠ.ㅠ
• 후니
• 2007-05-15 08:17:31
• x

• 어렵네..라고 페이지를 닫았지만, 계속 생각하게 되는것이;;
  김창준님 댓글보니, 답이 나왔네요.
  1, 2 둘 중 하나가 선택될 확률은 1/2 ---> 선택된 값 a1
  a1, 3 줄 중 하나 선택. 단, 확률은 a1==>2/3, 3==>1/3. ---> 선택된 값 a2
  (a1이 되기위해 1/2의 경쟁을 거쳤으므로, a1이 a2가 되기 위해서는 1/2 * 2/3 = 1/3으로 3과 동일 확률)
  a2, 4 둘 중 하나 선택. 단, 확률은 a2==>3/4, 4==>1/4 ---> 선택된 값 a3
  
  이렇게 N번째 까지 진행후, 상위 1000개 획득. (물론 1001번째로 밀리면 삭제하면서 진행했어야 함.)
  
  재밌습니다. 이런 문제 출제하는 사이트를 하나 만들어보면 어떨까하는 생각이 드네요. (누군가 만들어주기를 기대+_+)
  
  저도 자극 받았으니, 더욱 정진해야겠습니다.
• 삽질후허리삐끗
• 2007-05-15 09:15:27
• x

• 그런데 생각해보니 1개의 숫자가 아닌 1000개의 숫자라는게 문제가 될것도 같습니다.
  1위의 숫자는 확실한데, 2위~1000위의 숫자를 어떻게 찾아낼 것인가. 흐음;
  N번째 까지 진행하고, 뽑힌 숫자를 제외, 다시 N 까지 진행하고를 1000번 해야하는가 하는 의문이 생기네요. 더 좋은 방법은 없는지 고민해봐야겠습니다.
• 삽질후허리삐끗
• 2007-05-15 11:03:44
• x

• 삽질후허리삐끗//
  저도 1개일때는 알겠는데 1000개일때
  는 문재가 되는거 같았습니다.
  식으로 풀어보려해도 헷갈리고
  대신 이런 방법을 생각했습니다.
  1번째는 1,1001,2001,...1000*n+1순으로 생존확률계산
  2번째는 2,1002,2002,...1000*n+2...
  . . . . . .
  1000번째는 1000,2000,...1000*n+1000 식으로 해서 생존확률계산
  
  1000짜리 배열에 각각 한칸 위의 식대로
  생존확률을 계산하면 될거같습니다.
• 후니
• 2007-05-15 12:36:47
• x

• 후니//음, 잘 모르겠지만 약간의 문제가 생길것 같습니다.
  1000*n+1의 배수가 반드시 포함되어야하지는 않을거 같습니다.
  물론 1000*n+2도 마찬가지이고, 분포가 랜덤하지 않다는 점이 문제가 될듯 합니다.
  예를 들어 랜덤한 1000개의 숫자라면 1, 1001, 2001일 모두 들어갈 수도 있는데 후니님 말씀처럼 하면 이건 불가능하겠죠.
  또한 N의 카운트를 미리 알 수 없는 것도 문제가 될거 같습니다. 미세한 차이겠지만, 1000의 배수가 아닐경우에 오차도 생각할 수 있겠죠.
  오랫만에 생각을 많이 하네요 ^^
• 삽질후허리삐끗
• 2007-05-15 13:48:07
• x

• 음 제가 설명을 이상하게 썼네요
  어쨋든 결과적으로 1000의 배수가 아닐경우가
  오차가 생기는건 문재네요
• 후니
• 2007-05-15 13:54:15
• x

• 후니님 지원하신거 같은데.
  
  면접 잘 보셨나요? 궁금.. ^^
• t_chart
• 2007-05-16 10:48:33
• x

• t_chart//
  ??
  먼산
  버럭!!
• 후니
• 2007-05-16 13:40:43
• x

• 먼산 이라는게 무슨뜻인가요?
  지원하신게 아니란 뜻인가요?
  흐흐;
• t_chart
• 2007-05-16 19:10:22
• x

• 삽질후허리삐끗//
  음 결국 문재가 스트림이라는걸 알고
  처음 생각한게 답인거 같네요.
  3가지 케이스를 고민해 봤는데
  1. 1000/n로 계속 생존률을 누적해서 n이 -1이 복귀될때
  전체 확률을 같게 해주는 방법
  2. 1000개 배열 2개(a,b)에 a에는 걍 넣고
  b에는 1/(n/1000)의 확률에 각 자리에 넣고 1000개 를 확인하고
  다돌면 대응대는 a의 자리에 넣는식을 반복하는거
  3. 배열 a에 1000개를 넣고
  1001번째는 a[0]에 1001의 배수를 출현수 n/1000만큼 1000/n의 확률로
  10002 a[1]
  ..... .....
  2000번째는 a[999] 2000의 배수를 출현수 n/1000만큼 1000/n의 확률로
  각 번지마다 따로 계산하는 방법
  
  생각날때마다 a4지에 공식을 적어가면서 했는데
  
  2,3번째 방법은 각각 1000의 배수가 아닐경우의 수정치를 못구했고
  1번째 방법은 수식상으로 맞고
  이슈가 먼저 선택된녀석의 생존 확률에 대한 의문이었는데
  결국 먼저 선택된 수는 끝까지 간다면 1000/n은 수식으로 증명되었고
  중간에 버린다면 1000/n보다 큰활률일때 버려진거므로
  결과적으로 1000/n의 확률에는 영향을 주지 않네요.
  내일은 시간이 나면 실제로 짜서
  n=100000000정도로 잡고
  100번정도 해봐서 분포도 보고
  일정치 않으면 random()메서드를 다시 만드는걸 고민해봐야
  될듯해요
• 후니
• 2007-05-17 01:45:26
• x

• 누구의 예기인지 모르겠지만.... 위에 중에 아래의 것이 분포는 고르게 되내요....
  신기해...ㅎㅎㅎ
  랜덤이라면 한곳이 집중도 되야 되지않을까요...ㅎㅎㅎ
  <script type="text/javascript">
  var steam = new Array(1000);
  var n = 10000;
  var start_time = new Date();
  var end_time;
  var return_time;
  var j;
  for(var i=0;i < 1000; i++){
  steam[i]=i+1;
  }
  j=1;
  for(var i=1001;i <= n; i++){
  if(Math.round(Math.random()*j) == Math.round(j/2))
  steam[Math.round(Math.random()*1000)] = i;
  if(i%1000 == 0)
  j++;
  }
  
  for(var i=0;i < 1000; i++){
  for(var j = i+1;j < 1000; j++){
  if(steam[j] < steam[i]){
  tmp = steam[j];
  steam[j] = steam[i];
  steam[i] = tmp;
  }
  }
  }
  
  end_time=new Date();
  return_time = end_time.getTime() - start_time.getTime();
  document.write(return_time +" : 밀리초");
  document.write("<br>");
  for(var i=1;i < 1001; i++){
  document.write(steam[i-1]+", ");
  if(i%20 == 0)
  document.write("<br>");
  }
  </script>
• asdf
• 2007-05-19 02:14:08
• x

• 랜덤을 사용하면 편차도 랜덤해서
  일정한 편차를 보장하는걸 다시 만들어봤습니다.
  
  import java.util.Arrays;
  public class StreamDistribute
  {
  static int array_range = 1000;
  static int stream_range = 200000;
  static long min_mid = -1;
  static int min_pos = -1;
  static long num_stream = 0;
  static long num_array [] = new long[array_range+1];
  static long mid_array [] = new long[array_range-1];
  
  public static void main(String[] args)
  {
  System.out.println("Hello World!");
  distribute();
  // printNum();
  // printMid();
  averageMid();
  }
  static long getNum(long num){
  return ++num;
  }
  static void distribute(){
  long temp_num = 0;
  num_array[0] = num_stream;
  
  for (int i=1;i<array_range+1 ;i++)
  {
  num_stream = getNum(num_stream);
  num_array[i] = num_stream;
  }
  num_stream=getNum(num_stream);
  initMid(-1, -1);
  //printMid();;
  for (int i = (int)num_stream;i<stream_range+1 ;i++ )
  {
  //System.out.println(i+"번째 입력,입력수: " + num_stream+" ");
  temp_num = num_stream - num_array[num_array.length-2];
  //System.out.println("temp_num = num_stream - num_array[num_array.length-2] : "+temp_num+" = "+num_stream+" - "
  //+num_array[num_array.length-2]);
  //System.out.println("temp_num>min_mid " + temp_num+">"+min_mid+" "+(temp_num>min_mid));
  if (temp_num>min_mid)
  {
  initArray(num_stream,temp_num);
  }
  
  for(int j = 1;j<num_array.length;j++)
  {
  //System.out.print(num_array[j]+",");
  }
  //System.out.println();
  //printMid();;
  //System.out.println();
  num_stream=getNum(num_stream);
  }
  }
  static void initMid(int pos,long min){
  if(pos<0){
  for (int i = 0;i < num_array.length-2;i++ )
  {
  mid_array[i] = num_array[i+2]-num_array[i];
  }
  min_mid = 2;
  min_pos = array_range-1;
  }
  else{
  for (int i = pos-2;i < num_array.length-2;i++)
  {
  if(i>-1){
  mid_array[i] = num_array[i+2]-num_array[i];
  //System.out.println(i+": "+ mid_array[i]+",");
  }
  }
  //System.out.println("min : "+min);
  long ll_temp = num_array[num_array.length-1];
  for(int y = mid_array.length-1;y>-1;y--){
  if(mid_array[y]<min){
  min_pos = y+1;
  min_mid = mid_array[y];
  break;
  }
  else if(mid_array[y]>=min&&mid_array[0]>=min){
  //System.out.println(ll_temp);
  if(mid_array[y]>ll_temp){
  for(int z = y;z>-1;z--)
  {
  if(min_mid>mid_array[z]){
  min_pos = z+1;
  min_mid = mid_array[z];
  ll_temp = min_mid;
  //System.out.println("gg");
  continue;
  }
  }
  break;
  }
  else if(mid_array[y]==ll_temp){continue;}
  else {
  min_pos = y+1;
  min_mid = mid_array[y];
  ll_temp = min_mid;
  //System.out.println("gg");
  }
  //break;
  
  }
  }
  //System.out.println("min : "+(min)+", min_pos : "+min_pos+", min_mid : "+min_mid);
  for(int z = mid_array.length-1;z>-1;z--)
  {
  if(min_mid>mid_array[z]){
  //System.out.println(z);
  //printMid();;
  System.exit(1);
  }
  }
  
  
  }
  }
  static void initArray(long num,long temp){
  int pos = min_pos;
  //System.out.println("min_pos : "+min_pos);
  for (int i = min_pos;i < num_array.length -1 ; i++)
  {
  num_array[i] = num_array[i+1];
  }
  num_array[array_range] = num;
  initMid(pos,temp);
  }
  static void printMid(){
  for(int j = 0;j<mid_array.length;j++)
  {
  System.out.print(j+":"+mid_array[j]+", ");
  }
  System.out.println(" mid_array");
  }
  static void printNum(){
  for(int j = 0;j<num_array.length;j++)
  {
  System.out.print(j+":"+num_array[j]+", ");
  }
  System.out.println(" num_array");
  }
  static void averageMid(){
  long avg = 0;
  for(int j = 0;j<mid_array.length;j++){
  avg+=mid_array[j];
  }
  avg = avg/mid_array.length;
  System.out.println("평균 편차 : "+avg+", 기대 편차 : "+ (stream_range/array_range*2));
  Arrays.sort(mid_array);
  System.out.println("최소 편차 : "+mid_array[0]+", 최대 편차 : "+mid_array[mid_array.length-1]);
  }
  }
• 후니
• 2007-05-29 18:58:01
• x

• 랜덤쓰면 편차도 랜덤>.<b
  import java.util.Arrays;
  public class StreamDist {
  static int array_range = 100;
  static int stream_range = 2000;
  static long num_array [] = new long[array_range+1];
  static long mid_array [] = new long[array_range-1];
  static long num_stream;
  
  public static void main(String[] args) {
  run();
  java.util.Arrays.sort(num_array);
  for (int i = 0;i < num_array.length-2;i++ )
  {
  mid_array[i] = num_array[i+2]-num_array[i];
  }
  printNum();
  printMid();
  averageMid();
  }
  static long getNum(long num){
  return ++num;
  }
  static void run(){
  num_stream=0;
  num_array[0]=num_stream;
  for(int i = 1; i<array_range-1;i++){
  num_stream=getNum(num_stream);
  num_array[i]=num_stream;
  }
  
  for(int j = array_range;j < stream_range+1;j++){
  long pos=(long) (java.lang.Math.random()*j+1);
  //System.out.println(pos+"/"+j);
  num_stream=getNum(num_stream);
  if(array_range>=pos){
  num_array[(int) pos]=num_stream;
  java.util.Arrays.sort(num_array);
  
  //printNum();
  }
  }
  
  
  }
  static void printMid(){
  for(int j = 0;j<mid_array.length;j++)
  {
  System.out.print(j+":"+mid_array[j]+", ");
  }
  System.out.println(" mid_array");
  }
  static void printNum(){
  for(int j = 1;j<num_array.length;j++)
  {
  System.out.print(j+":"+num_array[j]+", ");
  }
  System.out.println(" num_array");
  }
  static void averageMid(){
  long avg = 0;
  for(int j = 0;j<mid_array.length;j++){
  avg+=mid_array[j];
  }
  avg = avg/mid_array.length;
  System.out.println("평균 편차 : "+avg+", 기대 편차 : "+ (stream_range/array_range*2));
  Arrays.sort(mid_array);
  System.out.println(" 최소 편차 : "+mid_array[0]+", 최대 편차 : "+mid_array[mid_array.length-1]);
  avg = 0;
  for(int j = 1;j<mid_array.length-1;j++){
  avg+=mid_array[j];
  }
  avg = avg/(mid_array.length-2);
  System.out.println("안정 평균 편차 : "+avg+", 기대 편차 : "+ (stream_range/array_range*2));
  System.out.print("편차 오차 : " +(-mid_array[0]+mid_array[mid_array.length-1]));
  System.out.println(", 오차 분포 : +"+((stream_range/array_range*2)-mid_array[0])+" "+
  ((stream_range/array_range*2)-mid_array[mid_array.length-1]));
  }
  }
  
  
  
• 후니
• 2007-05-29 21:02:43
• x

• 호기심 천국 끝>.<b
• 후니
• 2007-05-29 21:04:18
• x

• 2번문제를 김창준님이 말씀한 weighted_random_sampling을 적용해서 한번 풀어 봤는데
  제대로 구현 했는진 정확히 모르겠네요.^^
  하지만 추출되는 값들이 일정하게 추출되는거 같네요
  
  Perl코드 입니다.
  
  sub weight_to_dist {
  my %weights = @_;
  my %dist = ( );
  my $total = 0;
  my ($key, $weight);
  local $_;
  
  foreach (values %weights) {
  $total += $_;
  }
  
  while ( ($key, $weight) = each %weights ) {
  $dist{$key} = $weight/$total;
  }
  
  return %dist;
  }
  
  
  sub weighted_rand {
  my %dist = @_;
  my ($key, $weight);
  
  while (1) {
  my $rand = rand;
  while ( ($key, $weight) = each %dist ) {
  return $key if ($rand -= $weight) < 0;
  }
  }
  }
  
  
  
  sub getNextNumber {
  #알수없는 stream크기
  my $size = int(rand(10000));
  my $idx = 0;
  my @stream = (1..$size);
  print "stream size: ", scalar @stream, "\n";
  return sub { # this is a closure
  return $stream[$idx++];
  };
  }
  
  my %sample_weights = ();
  sub weighted_random_sampling {
  
  my($oldValue, $at, $newValue) = @_;
  my %weights = ($oldValue => $sample_weights{$at} || 1,
  $newValue => 1);
  
  my $result = weighted_rand(weight_to_dist(%weights));
  $sample_weights{$at}++ if ($result == $newValue);
  return $result;
  }
  
  
  my $stream = getNextNumber();
  my @random = ();
  my $randomSize = 1000;
  while (my $nv = &$stream()) {
  if(scalar @random < $randomSize) {
  push @random, $nv;
  } else { #weighted random sampling
  my $randomIdx = int(rand($randomSize));
  my $old = $random[$randomIdx];
  $random[$randomIdx] = weighted_random_sampling($old, $randomIdx, $nv);
  }
  }
  
  print "result ", scalar @random, "\n";
  my $div=1;
  for(@random) {
  print "$_\t";
  print "\n" if($div++ % 10 == 0);
  }
• goeasylife
• 2007-06-13 15:29:00
• x

• 근데,
  답들이 입력스트림이 white noize인것을 가정한거 아닌가요?
  물론, 입력스트림이 많아지면 수렴하겠지만..
• permedia
• 2007-07-10 16:16:57
• x

• 글쎄요 정말 훌륭한 대답들도 많이 있고 저에겐 코딩의 압박이 오는 느낌이네요 ^^; 아직 신입이라 문제가 뭔지 어떤식으로 풀어야 할지 전혀 모르겠습니다.
  
  연봉하니 생각하는 것이 있습니다만...
  
  한국에는 자기 사업을 하려는 사람들이 점층적으로 줄고 있다고 합니다. 다들 공무원 시험만 보려고 하고 안정적인 직장만 찾으려하고 젊은 시절에 모험이라든지 뭔가 도전하려는 정신은 없는 것 같습니다. 저만해도 도전이 싫어 대학시절 잠깐했던 프로그래밍에 몸을 담은 거죠. 나름대로 무역과 영업에 자신이 있는데도 불구하고 불안전한 생활이 싫어 때려치고 프로그래밍에 몸을 담았습니다만 요즘들어 생각하는 것은 저에게 1년 정도의 안정적인 생활 자금이 있다면 한번쯤은 도전해보고 싶다 입니다.
  
  먹고살기 바쁜 와중에 중요한 것이 무엇인지 잊고 사는 거 같습니다. 위에 댓글로 해당 문제를 열심히 푸신 분들은 정말 유쾌한 도전을 해 보신거 같습니다. 하지만 저는 그 도전 이라는 것 자체도 이미 생각을 잃은 것 같습니다.
• 랏츠
• 2007-07-13 11:54:26
• x

• 오랫만에 문제나 풀어야 겠다.
• 늙은이
• 2007-10-22 19:27:58
• x

• 내가 뭔얘기를 써논거지-_-;;
• 후니
• 2008-04-21 16:49:05
• x

• //
  // row,column 파라메터는 새로 찍힌 좌표로 이해함
  // N = 가로,세로 길이
  // board[][]의 값: 초기값=0, O=1,X=-1
  //
  bool IsWinningMove(int **board, int N, int row, int column)
  {
  int val = board[row][column];
  int sum1 = 0;
  int sum2 = 0;
  int sum3 = 0;
  int sum4 = 0;
  
  for(int i = 0; i < N; i ++)
  {
  sum1 += board[i][row]; //가로합
  sum2 += board[column][i]; //세로합
  sum3 += board[i][i]; //대각선합
  sum4 += board[N-i-1][i]; //대각선합(반대)
  }
  
  if((sum1 == (N * val)) || (sum2 == (N * val)))
  return true;
  
  
  if(column == row)
  {
  if((sum3 == (N * val) || (sum4 == (N * val))
  return true;
  }
  
  return false;
  }
• 우뇌형개발자
• 2008-05-29 12:54:22
• x

• 써놓고 날짜를 보니 작년거네...
• 우뇌형개발자
• 2008-05-29 12:58:23
• x