World Final 뒤풀이 - shuffle 함수가 어떻게 O(N)에 돌아가지?

PS 인생의 종착점인 World Final이 끝나고, 곧바로 한국으로 돌아가는게 아쉬워서 Phoking 팀원들이랑 같이 molamola. 코치님의 거주지인 영국으로 2주간 침공여행을 갔다. 땅이 워낙 넓었어서 순수 이동시간이 꽤 많이 걸렸고, 덕분에 여행의 컨텐츠 상당수가 무지성 헛소리로 채워졌다. 이 글은 그 무지성 헛소리 중 하나이다.

 

영국 여행의 메인 이벤트였던 맨유 vs 맨시티 축구 경기를 보기 위해 맨채스터로 차를 몰고 가던 중, 점심을 떼우기 위해 잠시 휴게소에 들렀다. 그때 정확히 무슨 대화중이었는지는 모르겠으나 이런 떡밥이 갑자기 돌았다.

 

길이 N의 배열의 random shuffle이 어떻게 O(N)에 돌아가지?

 

이게 뭔 해괴망측한 떡밥인가 싶을 수 있지만, 의외로 재밌어서 주문한 KFC가 나오기 전까지 열심히 생각을 해봤다. 당시 본인 사고의 흐름은 이랬던 것 같다.

• 배열의 각 수를 적은 제비들을 상자에 넣고, (뽑은 제비를 다시 안넣는) 제비뽑기를 n번 연속 해서 나온 array는 random shuffle된 상태임을 쉽게 증명할 수 있다.
• "제비뽑기" 자체를 구현하는 것은 쉽다. 길이 N의 array가 있을때, i = randint(0, n-1)을 뽑은 후 a[i]를 return하면 된다.
• 하지만 "뽑은 제비를 다시 안넣기"가 의외로 어렵다. a[i]가 빠진 새로운 array B = {a[0], a[1], ..., a[i-1], a[i+1], ..., a[n-1]}을 다시 만들어야 하는데, 이걸 깡 vector로 하려고 하면 최대 O(N)이 걸리고, segtree나 pbds를 쓰면 각 턴의 뽑기를 logN에 관리할 수 있으니 될 것 같지만 결국 합치면 O(NlogN)이 걸리니 비효율적이다.
• 그럼 index i가 이전에 뽑혔는지를 관리하는 check 배열을 만들어서, 제비 안넣기를 생략할수 있을 것 같다. 매턴 i = randint(0,n-1)을 뽑은 후, i가 뽑히지 않았다면 a[i] return, i가 이전에 뽑혔다면 리트, 이런 식으로 말이다. 되게 그럴싸해 보이지만, 다시 생각을 해보면 이럼 리롤 횟수의 기댓값이 (N/N + N/(N-1) + N/(N-2) + ... + N/1) = NlogN이 되서 또 망한다. 흐음...
• 여기서 번뜩이는 생각을 하게 되는데, 위 2개의 tactic을 반반씩 조합하는 것이다. 이게 무슨 말이냐면, 성공한 리롤 횟수가 N/2가 될때까지 바로 위 randint->check->reroll or go 알고리즘을 돌리고, N/2번을 다 뽑으면 이제 남은 뽑히지 않은 array들을 차곡차곡 모아서 새로운 vector array를 만들어버린다. 이걸 하면 리롤 기댓값이 (N/N + ... + N/(N/2)) <= (2 * N/2) = N, 새로운 array vector를 만드는 데 O(N)이 걸린다. 따라서 도합 (amortized) O(N)의 연산으로 제비뽑기를 N/2번 할 수 있고, 이 과정을 마치고 남은 제비가 N/2개가 된다.
• 이제 방금 위의 알고리즘을 무한 반복하면 O(N) + O(N/2) + O(N/4) + ... = O(2N)의 시간복잡도로 모든 제비뽑기를 마칠 수 있다!

여기까지 사고의 흐름이 도달한 후, 나는 이 위대한 발견을 자랑스럽게 일행에게 공유했다. 그리고 이 무적의 알고리즘을 경청한 molamola.가 치킨을 뜯으며 약 10초 정도 생각을 하더니...

 

• 님 근데 a[i] 뽑고 나서 그냥 a[n-1]랑 a[i] swap하면 되는거 아닌가요? 차피 랜덤뽑기인데.

ㅋㅋ 님아 그런게 될리가..

 

..

 

엥?

 

..

 

역시 3000점은 똑똑하단 걸 또 한번 느낄 수 있는 시간이었다.

 

(번외) molamola. 의 씽크빅에 감동한 kwoncycle은 그만 맨시티 홈구장에 맨유 목도리를 차고 가는 블런더를 저지르고 말았고, 덕분에 경기장 출입금지를 당하고 말았다. 그런고로, 지금부터 여기는 맨채스터 유나이티드 갤러리이다.