쿠폰 수집 문제

쿠폰 수집 문제는 확률론에서 중요하게 다루는 문제 중 하나로, n종류가 있는 쿠폰을 임의로 수집해나갈 때, 모든 종류를 적어도 한 장 이상 수집하려면 몇 장이나 수집해야 하는지를 묻는 문제이다. 수학으로 분석해 보면 필요한 쿠폰 개수는 종류 수 n에 대해 O(n log n) 비율로 비례한다.

같이 보기

• 생일 문제