가중 표본 추출은 “무엇을 얼마나 자주 선택할까”라는 분포를 코드로 만드는 문제입니다. 매번 전체 후보에서 다시 뽑는 복원 추출과 한 주기 안에서 후보를 없애는 비복원 추출은 같은 가중치를 사용해도 서로 다른 정책이므로, 구현 전에 원하는 것이 장기 빈도인지 순서 편향인지부터 고정해야 합니다.
빈도와 선행 확률의 구분
어려운 질문 B를 쉬운 질문 A보다 세 배 자주 보여 주고 싶다고 합시다. A=1, B=3의 가중치를 두고 매번 다시 뽑으면 B의 확률은 3/4입니다. 그러나 한 번 뽑은 질문을 덱에서 제거하면 B는 주기 안에서 여전히 한 번만 나옵니다. 이때 높아지는 것은 빈도가 아니라 앞에 나올 가능성입니다.
가중 복원 추출과 가중 비복원 추출을 먼저 구분해야 구현과 학습 정책이 일치합니다. 아래에서는 비음수 정수 가중치로 복원 추출을 만들고 그 위에 제약을 추가했을 때 무엇이 달라지는지 봅니다.
비중첩 구간으로의 가중치 변환
A=1, B=3, C=2이면 총 가중치는 6입니다. [0,6)의 정수 하나를 균등하게 고르고 해당 구간의 항목을 반환합니다.
| 항목 | 가중치 | 담당 구간 | 해당 정수 | 확률 |
|---|---|---|---|---|
| A | 1 | [0,1) | 0 | 1/6 |
| B | 3 | [1,4) | 1,2,3 | 3/6 |
| C | 2 | [4,6) | 4,5 | 2/6 |
그림을 글로 읽기
- r ∈ {0,1,2,3,4,5}: 각 정수 확률 1/6
- r < 4: r=0 → A · r=1,2,3 → B
- r ≥ 4: r=4,5 → C
- r ∈ {0,1,2,3,4,5} → r < 4: 앞 구간
- r ∈ {0,1,2,3,4,5} → r ≥ 4: 뒤 구간
누적 끝점은 [1,4,6]입니다. 예를 들어 r=1이면 첫 끝점 1은 r보다 크지 않으므로 이진 탐색은 오른쪽으로 가고, 4가 처음으로 r보다 큰 끝점이어서 B를 반환합니다. r=0일 때만 첫 끝점 1에서 멈춰 A를 반환하며, r=4는 4를 건너뛰고 6에서 C가 됩니다. 따라서 조건은 r 이상이 아니라 r보다 큰 첫 끝점이어야 하고, 경계를 손으로 추적할 때는 r의 가능한 값을 먼저 모두 나열하고, 각 누적 끝점에 대해 “처음으로 끝점 > r인 인덱스”를 찾습니다. Python의 bisect_right(누적끝점, r)는 r보다 큰 첫 끝점의 위치를 돌려주므로 이 정의와 맞습니다. bisect_left는 같은 끝점에서 잘못된 항목을 선택할 수 있습니다. 가중치 0인 항목의 누적 구간 길이는 0이므로 선택되지 않습니다. 작은 정수 영역에서 전수 결과가 맞은 뒤에야 큰 입력의 분포 검사를 추가하는 편이 경계 오류를 빨리 드러냅니다.
누적 가중치의 이진 탐색
prepare(weights):
require length(weights) > 0
require every weight is a finite nonnegative integer
cumulative = running_checked_sum(weights)
require cumulative.last > 0
return cumulative
pick(cumulative):
r = uniformBelow(cumulative.last)
lo = 0
hi = length(cumulative)
while lo < hi:
mid = lo + (hi-lo)//2
if cumulative[mid] <= r:
lo = mid + 1
else:
hi = mid
return lo
구성 O(n), 선택 O(log n), 저장 O(n)입니다. 누적 합이 넘치지 않아야 하며 원천 난수도 전체 가중치 범위를 편향 없이 표현해야 합니다. 실수 가중치를 사용하면 반올림 때문에 아주 작은 구간이 사라지거나 총합 경계가 틀어질 수 있습니다. 정책상 정수 비율로 바꿀 수 있는지, 실제 라이브러리의 수치 계약이 무엇인지 확인합니다.
모든 가중치가 0이면 선택할 분포가 없습니다. 오류를 반환할지 명시적인 균등 fallback을 쓸지 정합니다. 음수·NaN·무한대를 조용히 보정하면 설정 문제를 숨기므로 입력 단계에서 거절하는 편이 명확합니다.
가중치 변경과 자료구조 갱신 비용
A의 가중치를 바꾸면 뒤 누적 끝점들이 달라져 단순 배열은 O(n) 재구성이 필요합니다. 자주 바뀌면 Fenwick tree처럼 점 갱신과 누적 합을 유지하는 구조를 쓸 수 있습니다. 누적 위치 탐색에 단조성이 필요하므로 가중치를 음수로 낮추어서는 안 됩니다. 정적인 대량 추첨에서는 전처리 후 빠르게 뽑는 alias method도 대안이지만 다른 자료구조이므로 이 코드와 혼동하지 않습니다.
동시 갱신 중 누적 배열 앞부분은 새 값, 총합은 옛 값으로 읽으면 실제 없는 구간을 뽑을 수 있습니다. 한 선택은 일관된 가중치 버전을 읽어야 합니다. 불변 스냅샷 교체나 잠금으로 분포의 원자적 공개를 보장합니다.
항목 제거 후 조건부 분포
가중치 1·3·2에서 B를 뽑아 제거하면 남은 A와 C는 1/3, 2/3로 선택됩니다. 한 주기를 모두 끝내면 세 항목 모두 한 번씩 나옵니다. 가중치는 순서를 바꾸는 데 쓰였고 빈도는 같아진 것입니다.
| 정책 | 다음 선택의 후보 | 해석 |
|---|---|---|
| 복원 추출 | 매번 전체 | 장기 빈도가 가중치 비율에 가까움 |
| 순차 비복원 | 아직 안 뽑은 항목 | 남은 가중치에 조건부인 순서 |
| 최근 노출 제외 | 쿨다운 밖의 항목 | 원래 가중 분포와 다른 정책 |
| 일부 균등 탐색 혼합 | 가중 선택과 균등 선택 혼합 | 낮은 가중치 주제에도 노출 기회 |
주기 경계, 항목 추가·삭제, 가중치 0으로 바뀐 항목의 처리도 정해야 합니다. “최근 오답만 집중”하면 새 주제를 거의 보지 못할 수 있으므로 사용자 목표에 맞게 탐색 비율과 반복 피로를 함께 측정합니다.
가중치 경계 전수 검증
예제 r=0~5를 모두 넣어 결과가 [A,B,B,B,C,C]인지 확인합니다. 가중치 [0,2,0,1]에서는 첫째·셋째 항목이 절대 선택되지 않아야 합니다. 재현 연습으로 [0,2,0,1]의 총합 3에서 r=0,1,2를 차례로 넣어 결과가 둘째, 둘째, 넷째 항목인지 확인합니다. 모두 0이면 선택 함수가 임의 항목을 만들지 않고 명시된 오류나 fallback을 내야 합니다. 가중치 갱신을 선택 중간에 주입했을 때 반환값과 총합이 서로 다른 버전의 배열에서 나오면 스냅샷 원자성이 깨진 것입니다.
반복 빈도는 정책이 의도대로 작동하는지 살피는 보조 지표입니다. 비복원 덱에서 한 주기 빈도가 모두 같다고 가중치 구현이 실패했다고 판단하지 말고, 해당 정책에서 순서와 포함 확률 중 무엇을 바꾸려 했는지부터 확인해야 합니다.