통계 (Statistics)

정의

통계 (Statistics) 는 데이터를 수집, 정리, 분석하는 학문. PS 에서는 주로 기술 통계 (Descriptive Statistics) 의 기본값들인 평균 (Mean), 중앙값 (Median), 분산 (Variance), 표준편차 (Standard Deviation) 와 스트리밍 통계 (Streaming / Online Statistics) 를 다룬다.

핵심 질문: “대량의 데이터(또는 무한 스트림)에서 평균과 분산을 얼마나 효율적으로 계산할 수 있는가?”

문제 상황과 동기

“N 개의 원소로 이루어진 집합에서 통계량을 계산” 또는 “데이터가 하나씩 들어올 때마다 통계량을 갱신”.

• Naive: 전체 데이터를 배열에 저장. 평균 O(N), 분산 O(N) (두 번 순회). 메모리 O(N).
• Online (Welford): 데이터가 한 개 올 때마다 O(1) 갱신. 메모리 O(1). 한 번만 순회.
• 중앙값: naive 는 매번 정렬 O(N log N). 힙으로 O(log N) 갱신.

핵심 통찰: 통계량을 점화식(재귀 관계)으로 표현하면 이전 값 + 새 값만으로 갱신 가능.

시각화

핵심 아이디어

평균 (Mean)

μ_n = (Σ x_i) / n

Online: μ_n = μ_{n-1} + (x_n - μ_{n-1}) / n

분산 (Variance)

모분산: σ²_n = Σ (x_i - μ)² / n

Welford’s online algorithm (1-pass, numerically stable):

δ = x_n - μ_{n-1}
μ_n = μ_{n-1} + δ / n
M2_n = M2_{n-1} + δ * (x_n - μ_n)    # sum of squared differences
σ²_n = M2_n / n                       # population variance

표본 분산: s²_n = M2_n / (n-1).

중앙값 (Median)

• 정렬 상태 유지: O(N log N) 초기 비용 + O(N) 삽입 (shift).
• Two-heap (max-heap + min-heap): O(log N) 삽입, O(1) median 조회.

알고리즘

# 평균 / 분산 (online streaming)
welford_update(μ, M2, n, x):
    n' = n + 1
    δ = x - μ
    μ' = μ + δ / n'
    M2' = M2 + δ * (x - μ')
    return μ', M2', n'

# 중앙값 (two-heap)
median_add(low_maxheap, high_minheap, x):
    if low is empty or x <= low.top():
        low.push(x)
    else:
        high.push(x)
    rebalance(low, high)       # ensure |low| == |high| or |low| == |high| + 1

median(low, high):
    return low.top()           # low has one more or equal

구현

// Welford online variance + two-heap median
#include <bits/stdc++.h>
using namespace std;
​
int main() {
  vector<double> data = {5, 8, 3, 9, 2, 7};
​
  // Welford online
  double mu = 0, M2 = 0;
  int n = 0;
  for (double x : data) {
      n++;
      double delta = x - mu;
      mu += delta / n;
      M2 += delta * (x - mu);
  }
  double variance = M2 / n;
​
  // Two-heap median
  priority_queue<double> low;
  priority_queue<double, vector<double>, greater<>> high;
  for (double x : data) {
      if (low.empty() || x <= low.top()) low.push(x);
      else high.push(x);
      if (low.size() < high.size()) {
          low.push(high.top());
          high.pop();
      } else if (low.size() > high.size() + 1) {
          high.push(low.top());
          low.pop();
      }
  }
  double median = low.top();
​
  cout << fixed << setprecision(4);
  cout << "Mean:     " << mu << "\n";
  cout << "Variance: " << variance << "\n";
  cout << "Median:   " << median << "\n";
}

# Welford online statistics + two-heap median
import heapq
import math
​
data = [5, 8, 3, 9, 2, 7]
​
# Welford online
mu = M2 = 0.0
n = 0
for x in data:
  n += 1
  delta = x - mu
  mu += delta / n
  M2 += delta * (x - mu)
​
variance = M2 / n
​
# Two-heap median
low = []   # max-heap via negative values
high = []  # min-heap
for x in data:
  if not low or x <= -low[0]:
      heapq.heappush(low, -x)
  else:
      heapq.heappush(high, x)
  if len(low) < len(high):
      heapq.heappush(low, -heapq.heappop(high))
  elif len(low) > len(high) + 1:
      heapq.heappush(high, -heapq.heappop(low))
​
median = -low[0]
print(f"Mean:     {mu:.4f}")
print(f"Variance: {variance:.4f}")
print(f"Median:   {median:.4f}")

// Welford + two-heap median
import java.util.*;
import java.io.*;
​
public class Main {
  public static void main(String[] args) {
      double[] data = {5, 8, 3, 9, 2, 7};
​
      // Welford online
      double mu = 0, M2 = 0;
      int n = 0;
      for (double x : data) {
          n++;
          double delta = x - mu;
          mu += delta / n;
          M2 += delta * (x - mu);
      }
      double variance = M2 / n;
​
      // Two-heap median
      PriorityQueue<Double> low = new PriorityQueue<>(Collections.reverseOrder());
      PriorityQueue<Double> high = new PriorityQueue<>();
      for (double x : data) {
          if (low.isEmpty() || x <= low.peek()) low.offer(x);
          else high.offer(x);
          if (low.size() < high.size()) low.offer(high.poll());
          else if (low.size() > high.size() + 1) high.offer(low.poll());
      }
      double median = low.peek();
​
      System.out.printf("Mean:     %.4f%n", mu);
      System.out.printf("Variance: %.4f%n", variance);
      System.out.printf("Median:   %.4f%n", median);
  }
}

Mean:     5.6667
Variance: 5.8889
Median:   5.5000

복잡도

변형 / 활용

함정

1. Naive 분산 (two-pass) 의 수치적 불안정

σ² = (Σ x²_i)/n - μ² 는 같은 부호 큰 수 끼리의 소거로 precision loss. 항상 Welford 권장.

2. 중앙값 two-heap rebalance

low 가 항상 high 보다 1 많거나 같도록 유지. 삽입마다 크기 비교 후 pop/push 교환.

3. Variance / std vs sample variance

σ² = M2 / n (population) vs s² = M2 / (n-1) (sample). PS 에서는 population 기준이 일반적.

4. 정수 데이터 분산

정수 평균이 실수면 정수 분산 공식 부정확. Σ (x_i - μ)² 를 double 로 계산.

5. 빈 배열 / 단일 원소

n = 0 이면 분산 undefined. n = 1 이면 분산 = 0 (population) 또는 undefined (sample). 경계 분기.

BOJ 연습 문제

참고

• 확률
• 정렬
• 우선순위 큐
• 자료구조