랜덤순열 (2) 썸네일형 리스트형 피셔-예이츠 셔플 (Fisher-Yates Shuffle) 우리는 종종 무언가를 잘 뒤섞을 필요가 있습니다. 예를 들어, 친구들과 여행을 가서 저녁을 맛있게 먹은 다음 설거지 당번을 뽑는 경우를 생각해 봅시다. 다양한 방법이 있겠지만, 가장 고전적인 방법 중 하나는 종이 조각을 사람 수만큼 준비하고 한 곳에 '꽝'을 적은 후 이를 잘 뒤섞고 한 명씩 종이 조각을 뽑는 것입니다. 이때 우리는 이 조각들이 잘 뒤섞여 있기를 바랍니다. 다른 예시로는 포커 게임을 들 수 있겠습니다. 딜러는 게임을 시작하기 전에 카드를 뒤섞습니다. 이때 게임 참가자들은 카드가 잘 뒤섞여 있기를 희망할 터입니다. 그렇다면, 과연 어떻게 하면 잘 뒤섞을 수 있을까요? 사실 이 주제는 처음부터 제가 정리하겠다고 염두에 둔 주제는 아니었습니다. 처음에는 쿠폰 수집가 문제(coupon colle.. 비서 문제 (Secretary Problem) 여러분이 다음 뽑기 게임에 참가했다고 가정해 봅시다. 안을 볼 수 없는 상자가 여러분 앞에 놓여 있습니다. 여러분은 상자 안에 총 \(n\) 개의 공이 들어 있다는 것과, 공에는 서로 다른 숫자가 적혀 있다는 것을 알고 있습니다. 이제 여러분은 상자에서 공을 하나씩 무작위로 뽑고 공의 숫자를 확인할 것입니다. 만약 숫자가 마음에 든다면 여러분은 이 공을 선택할 수 있고, 만약 마음에 들지 않는다면 이를 버리고 새 공을 뽑을 수 있습니다. 다만 한 번 버린 공은 다시 주울 수 없죠. 가장 큰 숫자가 적힌 공을 선택해야 뽑기 게임에서 이긴다고 할 때, 과연 여러분은 어떤 전략을 취해야 할까요? 이 문제는 1950-60년대 여러 수학자들과 통계학자들 사이에서 매우 깊이 연구되었던 비서 문제(secretary .. 이전 1 다음
