알고리즘 & 확률/Permutation (1) 썸네일형 리스트형 피셔-예이츠 셔플 (Fisher-Yates Shuffle) 우리는 종종 무언가를 잘 뒤섞을 필요가 있습니다. 예를 들어, 친구들과 여행을 가서 저녁을 맛있게 먹은 다음 설거지 당번을 뽑는 경우를 생각해 봅시다. 다양한 방법이 있겠지만, 가장 고전적인 방법 중 하나는 종이 조각을 사람 수만큼 준비하고 한 곳에 '꽝'을 적은 후 이를 잘 뒤섞고 한 명씩 종이 조각을 뽑는 것입니다. 이때 우리는 이 조각들이 잘 뒤섞여 있기를 바랍니다. 다른 예시로는 포커 게임을 들 수 있겠습니다. 딜러는 게임을 시작하기 전에 카드를 뒤섞습니다. 이때 게임 참가자들은 카드가 잘 뒤섞여 있기를 희망할 터입니다. 그렇다면, 과연 어떻게 하면 잘 뒤섞을 수 있을까요? 사실 이 주제는 처음부터 제가 정리하겠다고 염두에 둔 주제는 아니었습니다. 처음에는 쿠폰 수집가 문제(coupon colle.. 이전 1 다음
