저수지 샘플링(Reservoir Sampling)은 무작위화(randomized) 알고리즘의 일종으로, 전체 크기를 미리 알 수 없거나 매우 큰 데이터 집합에서도 공평한 확률로 k개의 표본을 뽑을 수 있어 스트리밍 데이터 처리에 널리 활용됩니다. 즉, n개의 서로 다른 항목이 담긴 목록에서 k개의 항목을 무작위로 선택하는 알고리즘입니다.
단순한 접근 방식의 문제점
가장 직관적인 방법은 크기가 k인 배열을 '저수지(reservoir)'로 만들고, 메인 목록에서 항목을 하나씩 무작위로 골라 저수지에 채우는 것입니다. 단, 한 번 선택된 항목은 중복 선택되지 않도록 관리해야 합니다. 그러나 이 방식은 이미 선택된 항목인지 매번 확인해야 하므로 비효율적이며, 시간 복잡도가 증가하는 문제가 있습니다.
이를 개선한 방법은 다음과 같습니다. 먼저 목록의 처음 k개 항목을 저수지 배열에 그대로 복사합니다. 그다음 (k+1)번째 항목부터 하나씩 순회하면서, 현재 처리 중인 항목의 인덱스를 i라고 할 때 0부터 i 사이에서 무작위 인덱스 j를 하나 뽑습니다. 만약 j가 0 이상 k 미만의 범위에 있다면 reservoir[j]와 list[i]를 서로 교환(swap)합니다. 이 과정을 거치면 모든 항목이 동일한 확률(k/n)로 선택되는 것이 수학적으로 보장됩니다.
입력 및 출력 예시
Input:
정수 목록: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, k = 6
Output:
주어진 배열에서 k개 선택된 항목: 8 2 7 9 12 6알고리즘 의사코드
chooseKItems(array, n, k)
입력: 배열, 배열의 원소 개수(n), 선택할 원소의 개수(k)
출력: 무작위로 선택된 k개의 원소
Begin 크기가 [k]인 출력 배열을 정의한다 배열의 처음 k개 항목을 출력 배열에 복사한다 while i < n, do j := 0부터 i 사이에서 무작위로 하나의 값을 선택 if j < k, then output[j] := array[i] i를 1 증가시킨다 done 출력 배열을 화면에 표시한다 End
C++ 구현 예제
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void display(int array[], int n) {
for (int i = 0; i < n; i++)
cout << array[i] << " ";
}
void chooseKItems(int array[], int n, int k) { // 배열에서 k개의 항목을 선택
int i;
int output[k];
for (i = 0; i < k; i++)
output[i] = array[i];
srand(time(NULL)); // time 함수로 서로 다른 시드 값을 생성
while(i < n) {
int j = rand() % (i+1); // 0부터 i 사이의 무작위 인덱스
if (j < k) // i번째 원소를 출력 배열의 j번째 위치에 저장
output[j] = array[i];
i++;
}
cout << "K-Selected items in the given array: ";
display(output, k);
}
int main() {
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = 12;
int k = 6;
chooseKItems(array, n, k);
}실행 결과
K-Selected items in the given array: 8 2 7 9 12 6
복잡도 분석
저수지 샘플링의 시간 복잡도는 O(n)으로, 데이터 전체를 한 번만 순회하면 됩니다. 공간 복잡도는 선택할 표본 개수에 비례하여 O(k)입니다. 덕분에 전체 데이터를 메모리에 담지 않고도 스트림에서 실시간으로 균등 확률 표본을 추출할 수 있으며, 로그 데이터 샘플링, 대용량 데이터베이스 임의 조회 등 다양한 분야에서 활용됩니다.