메뉴 건너뛰기

BLENDING

자유 게시판

간만에 퀴즈 하나

01오치문2014.02.11 08:18조회 수 7135댓글 18

    • 글자 크기

아래와 같은 상황이 있습니다.


1. 두 개의 파일이 있고, 각 파일에는 임의의 수가 100만개씩 저장되어있다. (편의상 file1, file2)

2. file1, file2에는 같은 숫자도 있고 다른 숫자도 있다.

3. 알고자 하는 것은 file1에는 있는데 file2에는 없는 숫자의 갯수, 반대로 file2에는 있는데 file1에는 없는 숫자의 갯수이다.

4. 파일을 구성하는 각 숫자는 1보다 크고 1억보다 작다.


자, 이 문제를 어떤 방법으로 해결할 수 있을까요? 


가장 쉬운 방법부터 생각해보시고, 더 좋은 방법은 없는지 고민해봅시다. 


이왕이면 직접 랜덤수로 구성된 파일을 만들고 실제로 프로그램을 만들어 돌려보길 권합니다.


방법론, 슈도코드, 또는 실제 코드를 댓글로 달아주세요. (한 명은 달겠지 설마..?)




힌트는... 안알랴쥼~ -_-;; 

01' 기장, 02년 회장, 지금은 그냥 마이너스 존입니다.

    • 글자 크기
03학번 오태원선배가 결혼하네요 (by 08이혜린) 2014년 새해 복 많이 받으세요 (by 07최윤수)

댓글 달기

댓글 18
  • 딱 보자마자 떠오른건

    1. Hash

    2. Sorting

    자세한 내용은 재학생분들이 해결해주리라 믿어여

     

  • 저도 떠오른건..

    윤수꺼에 tree 추가


    자세한 내용은 재학생분들이.....아?

  • 07서동민님께

    님 재학생이잖음!! ㄱㄱ

  • 01오치문글쓴이
    2014.2.14 20:00 댓글추천 0비추천 0

    드디어 댓글이 :)




    설마 "자세한 내용은.." 내려가다가 신입생분들까지 가는거 아닌지 ㅋㅋ

  • 자세한 내용은 이번에 들어올 신입.....죄송..

    실력은 안되지만 시도해보겠습니다..

  • 10김영훈님께
    01오치문글쓴이
    2014.2.18 11:00 댓글추천 0비추천 0

    : )

  • 치문이 얘는 가르치는거 하는게 딱 적성에 맞는데 왜 취업했어.

  • 99곽용우님께
    당첨! 99곽용우님에게 -5포인트 팡팡 쏩니다!
  • 99곽용우님께
    01오치문글쓴이
    2014.3.19 12:42 댓글추천 0비추천 0

    팡팡이는 아니라는데요..?? ㅋㅋ

    가르치는거 하려도 박사는 따야 하는데 그걸 하느니 개발이 더 좋습니다. :)


    그나저나 응답이 없으니 조만간 제 의견을 올려야겠군요.

  • 간만에 들러서 보니 재밌는걸 적어놨네 


    무식한 방법은 100만 x 100만번 비교하는 것일테고,


    생각해 본 방법은

    1. 일단 두 파일은 읽어와서 정렬후

    2. 각 파일데이터에 대한 카운터값을 하나씩 만든다. c1, c2

    3. file1의 데이터를 A, file2의 데이터를 B, 두 데이터뭉치에서 같은 원소의 개수를 n이라 하면

        A[c1]과 B[c2]를 비교해서 

        같으면, c1과 c2를 모두 1씩 증가시키고, n을 1증가

        다르면, 작은값을 가지는 쪽의 카운터값을 1증가함.

            A[c1]=10, B[c2]=12라면  c1++;

    4. 쭉쭉 가다가, 어느한쪽이라도 데이터뭉치의 전체 데이터수(100만)이 되면 루프종료.

       그리고 나서 n값을 읽으면 이게 두 집합간 교집합의 원소 개수가 되니까, 100만에서 n을 빼주면 문제에서 원하는 답을 얻을 수 있음.



  • 01오치문님께
    당첨! 01오치문님에게 1포인트 팡팡 쏩니다!
  • 01현태환님께
    01오치문글쓴이
    2014.3.21 00:00 댓글추천 0비추천 0

    연락해도 안되더니 문제를 내니까 나타나는구먼 ㅋㅋ

    살아있네 살아있어~ 안부 들으려면 문제를 많이 내야 하는 것이냐? ㅋㅋ

  • 01오치문글쓴이
    2014.3.20 23:58 댓글추천 0비추천 0

    이 문제는 제가 실제로 업무에서 경험한 것입니다.


    처음 떠오른 아이디어는 hash를 이용한 것이었죠.

    한 파일에서 숫자를 쭉- 읽어드려서 hash를 만듭니다. hash[number] = 1 이런식으로 표시를 해두는거죠.

    그다음 다른 파일을 열어서 hash[number] is 1?? 이것만 체크하면 쉽게 카운트가 가능하죠.


    그런데, 숫자가 몇억이 넘어가다보니 hash를 사용할 수 없었어요.

    (실제로 프로그램에서 메모리를 엄청나게 잡아놓고 실행시켜보세요. 메모리 제한때문에 실행이 안되는걸 볼 수 있습니다.)


    다음으로 생각한 아이디어는 "무식한" 방법입니다. 100만 x 100만 비교였죠.

    이게 돌려보면 알겠지만 생각보가 훨~씬 오래걸립니다. 이렇게 되면 더 좋은 방법을 찾아봐야겠지요?


    다음으로 생각한 것은 이진탐색입니다. 그리고 이걸로 충분히 해결이 가능했지요.

    이진탐색은 모두 알다시피 중간값을 계속 변경시키면서 내가 구하고자 하는 해에 접근하는 방식입니다.

    예를들면, 1부터 100까지 숫자가 해의 후보일때, 처음에 50을 시도해보고, 그보다 작으면 25를, 이것보다 크면 75를 시도해보는 방식이죠.


    한 단계 더 나아가면 위에 태환군이 말한 방식까지 접근할 수 있습니다. 

    그러면, 이 과정을 머리아픈 복잡도로 설명해볼까요?


    1. 가장 쉽게 생각할 수 있는 "무식한" 방법의 복잡도는 어떻게 될까요?

    100만 x 100만을 모두 체크해야 하니까, O(n^2) 이 되겠지요.


    2. 이진탐색은?

    생각해보면 한 번 시도할 때마다 확률이 절반씩 줄어드는 것을 알 수 있습니다.

    그러니까 복잡도는 O(n*log(n))이 되지요. n은 한번 훑는 시간, log(n)은 해를 찾는 시간입니다. (한 번 시도할 때마다 절반씩 떨어져 나가니까..)


    3. 마지막 방법은?

    쉽게 상상되듯이 이 방법은 한 번만 훑으면 되므로, O(n)이 됩니다.


    이제 n에 100만을 대입해보면, 얼마나 차이가 나는지 확인할 수 있겠지요.


    이것이 여러분이 배우게 되는 복잡도의 개념입니다. 안타까운 것은 실제로 피부에 느끼기전에, 먼저 가르쳐주기 때문에 실제로는 와닿지 않는다는 것이죠. 무엇이든 처음에는 무식한 방법으로 접근하고, 그 다음에 더 좋은 방법이 없나 고민해 보는 것입니다. 


    그러니까, 이런 문제가 주어졌을때 무식하게 보일지 걱정하지말고 일단 시도해보고, 더 좋은 방법을 찾아가는게 중요하다고 생각해요. :)

    사실, 동료들과 이런 문제로 토론을 펼치는 것도 정말 재미있는 일이랍니다.

  • 01오치문님께
    당첨! 01오치문님에게 5포인트 팡팡 쏩니다!
  • 10김시형님께
    01오치문글쓴이
    2014.3.27 00:09 댓글추천 0비추천 0

    아, 정렬된 상태에서 시작한다는 전제가 빠졌군요.

    모든 케이스에 대해서 우선 정렬된 상태라고 봐주세요.


    그렇게 보면, 마지막 케이스뿐만 아니라 다른 조건에도 정렬에 필요한 시간은 들어가겠네요 ^^


    잘 봤네요~ 감사감사.


  • 01오치문님께

    선배님 질문이 하나 있습니다.

    마지막 방법은 정렬하는 과정도 포함되므로 복잡도가 더 올라가지 않나요??

     

    막상 작년에 배웠던 자료구조가 여기서 이렇게 활용되는게 체감이 되네요 ㅇ.ㅇ!

  • 좀 휴리스틱한 방법이기도 하지만, 정렬하지 않는 방법도 생각해 봤음.


    1. 위에서 언급한 100만 x 100만번 무식하게 탐색하는 것에서 데이터뭉치를 반으로 나누면 어떨까 해서 생각해 본 방법인데,

    데이터의 범위가 1에서 1억까지니까 반으로 나눠서 숫자가 5천만보다 작은 그룹과 큰 그룹, 두 그룹으로 나눠보면

      

    file1에서 5천만보다 작은 그룹을 A, 큰 그룹을 B, file2에서 작은그룹을 C, 큰 그룹을 D라 하면 A는 C와, B는 D와 비교를 하면된다. 

    비교한다는 연산자를 @라 할 때, 이를 무식한 방법으로 하면, n(A+B @ C+D) = n(A@C + A@D + B@C + B@D) 가 된다.

    5천만 이상과 이하그룹으로 나눌때 탐색횟수는 n(A@C + B@D)가 될 것이다.

    즉, file1의 5천만 이상그룹과 file2의 5천만 이하그룹, 또 그반대의 경우는 애당초 고려할 필요가 없으니 탐색에서 제외된다.

    그리고 이 과정에서 러프하게 정렬되는 효과를 가진다.


    elementi =  read(file1);

    gid=elementi / 50,000,000; //5천만 이하는 0, 이상은 1

    file1.group[gid].insert(elementi  );   //group1은 리스트 정도면 될 듯.


    이후, file1과 file2의 같은 gid를 가지는 그룹을 비교탐색함.


    2. 또, 데이터뭉치를 여러그룹으로 나누면 나눌수록 제외하는 탐색이 늘어날 것이다.  그럼 몇개까지?

    그룹1개일때(안나누는경우) 106 * 106

    2개일때, E(106 /2) * E(106 /2) * 2 = 106 * 106 /2번

    3개일때, E(106 /3) * E(106 /3) * 3 = 106 * 106 /3번

    n개일때, E(106 /n) * E(106 /n) * n = 106 * 106 /n번

    n=105 이면, E(10) * E(10) * 105 = 107 번.

    n=106 이면, E(1) * E(1) * 106 = 106 번.


    즉, 1부터 10억까지 100단위로 총 100만개의 그룹을 만들면, 각 그룹에는 평균적으로 1개의 데이터가 들어가게 될 것이고,

    정렬에 첨자까지 맞춰진 상태가 된다. 예를 들면 다음과 같다.


    데이터뭉치가 이럴때, A[]={..., 234, ... , 102, ...}, B[]={..., 234, ..., 38, ... }


                     A           B

       0~ 99)      -           38

    100~199)    102          -

    200~299)     234       234  

     ...


    이런식으로 된다. 그래서 비교할때는 0~99그룹에는 A가 원소가 없으니 그냥 패스 다음그룹도 B가 원소가 없으니 그냥 패스 이런식이다.

    위의 예에서는 각 그룹에 원소1개가 있는 것을 예로 들었는데, 기댓값이 1개라는 것이지 그 이상들어갈 수도 있다.


    이렇게 하면 탐색횟수가 줄어들 수도 있을 것같다.
  • 1. 데이터를 한눈에 보기 쉽게 출력한다.

    2. 종이 상단 가운데에 점 두개를 찍는다.

    3. 적당히 간격을 두고 눈에 힘을 푼다.

번호 제목 글쓴이 날짜 조회 수
공지 [난해한코딩대회] 예시4 16황지우 2020.08.31 356
공지 회장님 훈화말씀16 16황지우 2020.03.16 8487
공지 스맛폰으로 BLENDING홈피 새글 알림 받기1 BLENDING 2011.06.25 195300
3362 내일 군대가네요 하하......3 13전성혁 2015.01.19 4011
3361 [알고리즘 문제] 풀어보세요~5 01오치문 2014.12.27 4253
3360 회장님 보세요 03김남균 2014.11.21 4382
3359 개미수열11 01오치문 2014.10.31 5718
3358 엔진 라이브러리 토론 99곽용우 2014.10.28 4691
3357 재영아 화이팅!4 09이혜성 2014.10.06 4812
3356 예전 팩맨게임 보기 싫어서 다시올려요.10 11이은정 2014.09.23 5021
3355 유니티 공부 하는것 같아서4 07최윤수 2014.09.16 4982
3354 홈페이지가 죽었구나..4 10박태수 2014.09.01 5124
3353 8월18일날 군대갑니다 ㅠ4 13황정우 2014.08.09 5212
3352 잊고 있던 것 수정! 08정호열 2014.06.11 4945
3351 iconshop??6 14최중원 2014.04.17 5435
3350 03학번 오태원선배가 결혼하네요5 08이혜린 2014.04.01 5875
간만에 퀴즈 하나18 01오치문 2014.02.11 7135
3348 2014년 새해 복 많이 받으세요4 07최윤수 2014.01.01 5163
3347 2013년 12월 4일 히터 구매 했습니다.1 13전성혁 2013.12.04 5264
3346 홈페이지 새벽 4시쯤에 약간 느려질 수도 있습니다.1 08정호열 2013.11.21 7215
3345 2013년 엔씨소프트 하반기 신입사원 공개채용이 시작되었습니다.!!! 03김상헌 2013.10.10 8772
3344 다들 아는지는 모르겠지만..4 97김민경 2013.09.11 8851
3343 굽신굽신 블렌딩 흥신소..4 00한우람 2013.07.09 11816
이전 1 ... 17 18 19 20 21 22 23 24 25 26... 190다음
첨부 (0)
위로