박재율(jype@kakao.com)
쿠폰 수집가 문제는 N개의 서로 다른 쿠폰이 있고 한 번에 1개의 쿠폰을 획득할 때, 모든 종류를 수집하는 데 필요한 기대 시도 횟수를 구하는 문제다. 쿠폰을 획득할 확률은 모두 동일하다. 간단히 표현하자면 6면체 주사위를 굴려서 1부터 6까지의 숫자 여섯 개를 모두 나오게 하려면 몇 번을 굴려야 할지에 대한 내용으로 볼 수 있다.
상기한 예시는 아래 순서로 계산할 수 있다.
위에서 구한 식을 정리하자면, 6(1+1/2+1/3+1/4+1/5+1/6)으로 볼 수 있다. 여기서 6면체 주사위가 아니라 20면체라면, 6 대신 20(1+1/2+1/3+1/4+….+1/19+1/20)으로 계산할 수 있다. 1+1/2+1/3+… 으로 이어지는 수열의 합은 조화수(harmonic number)라고 불리며, H_n으로 표시할 수 있다. 선형 증가보다는 느리지만 무한히 발산하는 특징을 갖기 때문에, 로그적 증가를 갖는 기대값을 표현하는 데 주로 사용하고 엑셀로는 =sum(1/sequence(20))와 같은 함수의 조합으로 간단히 구할 수 있다.
하지만 실무를 위해 일반화시켜야 하는 부분은 단순히 가짓수만이 아니다. 대다수의 상황에서는 일부 종류의 확률을 의도적으로 낮춰, 완성 소요 시간을 확보한다. 그 케이스에서도 기대 시도 횟수는 계산이 가능하다.
단순화해서 60%, 30%, 10%의 세 종류가 있다고 가정했을 때, 나올 수 있는 모든 케이스를 계산해야 한다. 위에서 다룬 예시에서는 첫 시도에 어느 결과가 나오든 뒤 과정이 동일했지만, 종류에 따라 뒤에서 계산해야 하는 확률이 달라진다.
우선 각 종류를 A, B, C라고 했을 때, A를 획득하는 기대 시도 횟수, B를 획득하는 기대 시도 횟수, C를 획득하는 기대 시도 횟수를 구하여 더한다. 하지만 각 기대 시도 횟수에는 A/B 중 1개를 획득하는 기대 시도 횟수, B/C 중 1개를 획득하는 기대 시도 횟수, A/C 중 1개를 획득하는 기대 시도 횟수가 중복되어 포함되어있으므로, 그 합에서 뺀다. 그리고 뺀 내용 중에 A/B/C 중 1개를 획득하는 기대 시도 횟수(1)이 모두 빠졌으므로, 다시 더한다.
위 방법은 포함 배제의 원리라고 하며, 합집합의 원소 갯수를 구할 때도 주로 사용한다. 위 방법을 통해 계산한 결과는 (1/0.6+1/0.3+1/0.1) - (1/0.9+1/0.7+1/0.4) + 1로, 약 11이 나온다.
위 계산 방법은 이항 정리의 전개와 동일한 구성을 띄고 있으며, 각 기대 시도 횟수는 이항 정리의 최고차항을 제외한 각 항 계수를 따르게 된다. 그리고 이항 정리의 계수 합은 최고차항이 N일 때 2^N으로, 이는 종류가 하나씩 늘어날 때 마다 계산해야 하는 기대 시도 횟수가 두 배로 증가한다는 것을 뜻한다. 스무 종류의 서로 다른 확률을 갖는 경우를 계산할 때는, 백만 개 이상의 항을 구해서 더하고 빼야 한다.
실질적으로 컴플리트 가챠를 계산하는 데에는 사용하기 어려움이 있다. 몬테 카를로 방법을 사용할 수도 있지만, 관련 담당자가 일정 이상의 프로그래밍과 수학 지식을 필요로 하기에 보편적인 해결책이라고 볼 수는 없다.