IT › 컴퓨터 시스템 › 알고리즘 › 알고리즘 설계 기법

몬테카를로 방법Monte Carlo Method

난수로 뽑은 표본마다 계산한 값의 평균으로 적분 · 확률 · 기댓값을 근사하는 계산 방법이다. 오차는 표본 수의 제곱근에 반비례해 줄고 문제의 차원 수와 무관하다.

1요약

  1. 몬테카를로 방법은 계산하기 어려운 적분 · 확률을 난수 표본의 평균으로 바꿔 푸는 방법으로, 1949년 Metropolis · Ulam 이 이름을 붙였고 그 위에서 위험 분석의 일정 · 비용 분포, 소수 판정, 물리 · 금융 모의 실험이 돈다.
  2. 격자로 나눠 더하는 구적법은 차원이 d 이면 오차가 O(n^−4/d) 로 느려져 고차원에서 쓸 수 없지만, 몬테카를로의 오차는 차원과 무관하게 O(n^−1/2) 로 준다(Owen 2013 2장).
  3. 결과를 믿을지는 표준 오차와 편향을 따로 보고 정한다 — 실행마다 값이 흔들리면 표본이 모자란 것이고, 표본을 늘려도 한쪽으로 어긋나면 모형이나 난수가 틀린 것이다.

2등장 배경

1946년 병상에서 카드놀이를 하던 Ulam 은 52장 캔필드 솔리테어가 풀릴 확률을 조합 계산으로 구하다 막히자, «100번 펼쳐 보고 성공 횟수를 세는 편이 빠르다»는 생각을 했다(Eckhardt 1987). 이 생각은 중성자가 핵분열 물질 안에서 퍼지는 확산 문제처럼 식으로는 풀리지 않는 계산에 바로 쓰였다.

1947년 3월 von Neumann 은 Los Alamos 의 Richtmyer 에게 중성자 경로를 난수로 따라가는 계산을 ENIAC 에서 돌리는 편지를 보냈고, 1949년 Metropolis · Ulam 은 JASA 에 실은 논문 「The Monte Carlo Method」로 이 계산법을 통계학계에 알렸다(Metropolis · Ulam 1949). 1953년 Metropolis 등이 마르코프 연쇄로 표본을 뽑는 방법(MCMC)을 더했다(Owen 2013 1장).

지금은 난수 생성기가 표준 라이브러리에 들어 있어 몇 줄로 쓸 수 있고, RSA 키의 소수를 고르는 밀러-라빈 판정도 같은 원리의 무작위 알고리즘으로 FIPS 186-5(2023) 부록 B.3 에 들어 있다.

3쉽게 이해하기 — 전화 1,000통으로 지지율을 재는 여론 조사

선거를 앞둔 조사원이 시민 4,000만 명에게 다 물을 수 없어 전화번호 명부에서 번호를 무작위로 뽑아 1,000통을 돌린다. 찬성이면 1, 반대면 0 을 적고, 1 의 비율로 지지율을 52% 라고 발표하면서 «± 3.1%p» 를 함께 붙인다. 인원을 4배로 늘리면 그 범위가 절반으로 준다. 다만 집 전화만 돌리면 아무리 많이 걸어도 결과가 한쪽으로 쏠린다.

조사 본부 추정하는 쪽 조사원 추정 프로그램 번호 추첨 난수 생성기 · 시드 전화번호 명부 확률 분포 명부 전체가 뽑힐 후보 시민 응답하는 쪽 뽑힌 1,000명 표본 x₁ ~ xₙ 찬성 · 반대 함숫값 f(xᵢ) = 1 · 0 한 사람 = 표본 하나 1 번호대로 무작위 전화 표본 추출 2 찬성 1 · 반대 0 응답 함숫값 평가 3 찬성 응답 비율 계산 표본 평균 μ̂ 4 지지율 52% ± 3.1%p 로 발표 표준 오차 · 신뢰구간 5 집 전화만 돌리면 결과가 한쪽으로 쏠림 편향된 표본 1,000명 · 52% = 설명용 가정 값 · ± 3.1%p = 1.96 × √(0.52 × 0.48 ÷ 1,000) · %p = 퍼센트포인트

그림 1 · 무작위로 뽑은 표본의 응답 평균이 전체 값을 추정하고, 표본 수가 오차 범위를, 뽑는 방법이 편향을 정한다.

명부 준비누구를 뽑을 수 있는지 정함
번호 추첨명부에서 무작위로 1,000개
전화 걸기뽑힌 사람에게만 물음
응답 적기찬성 1 · 반대 0
비율 내기1 의 평균 = 지지율
범위 붙이기± 오차와 함께 발표
비유 — 조사 인원과 오차 범위 실제 — 표준 오차 100명 ± 9.8%p n = 100 → SE 5.0%p 400명 ± 4.9%p n = 400 → SE 2.5%p 1,600명 ± 2.5%p n = 1,600 → SE 1.3%p 30% 50% 70% 인원 4배 → 오차 범위 절반 SE = s ÷ √n 막대 = 지지율 50% 가정의 95% 범위(± 1.96 × SE) · s = √(0.5 × 0.5) = 0.5 · 설명용 가정 값

그림 2 · 조사 인원을 4배로 늘릴 때마다 오차 범위가 절반이 된다 — 실제로는 표준 오차가 표본 수의 제곱근에 반비례한다.

비유 속 역할실제 이름실제로 하는 일
전화번호 명부확률 분포 · 정의역표본이 나올 수 있는 범위와 각 값의 확률을 정한다
번호 추첨난수 생성기 · 시드시드에서 시작해 균등 난수열을 만들고 분포에 맞게 바꾼다
뽑힌 사람에게 전화표본 추출분포에서 서로 독립인 표본 x₁ ~ xₙ 을 뽑는다
찬성 1 · 반대 0 응답함숫값 평가표본마다 f(xᵢ) 를 계산하거나 모의 실험을 한 번 돌린다
찬성 비율표본 평균 μ̂f 값의 평균으로 기댓값 · 적분 · 확률을 추정한다
± 오차 범위표준 오차 · 신뢰구간s ÷ √n 으로 흔들림을 재고 μ̂ ± 1.96 × SE 를 붙인다
집 전화만 돌림편향분포 · 모형 · 난수가 틀리면 n 을 늘려도 오차가 남는다

⚠ 비유가 맞지 않는 곳: 여론 조사는 이미 있는 사람 가운데서 뽑지만, 몬테카를로 방법은 원래 확률과 무관한 적분 · 결정적 문제도 확률로 바꿔 푼다. 또 컴퓨터의 난수는 시드로 정해지는 의사 난수라 같은 시드면 같은 표본이 다시 나온다(Python random).

4구조 — 표본에서 추정까지의 구성 요소

몬테카를로 계산은 «문제를 기댓값 μ = E[f(X)] 꼴로 바꾸기 → 표본 n 개의 평균 μ̂ 로 추정 → 표준 오차로 멈출지 판정» 세 단계로 짠다(Owen 2013 2장). 알고리즘 설계에서는 정해진 시간 안에 끝나되 작은 확률로 틀릴 수 있는 무작위 알고리즘을 같은 이름(몬테카를로 알고리즘)으로 부른다.

확률 모형 분포 · 범위 정의 난수 생성기 시드 · 주기 표본 추출 xᵢ ~ 분포 함수 평가 f(xᵢ) · 실험 1회 μ̂ = Σf ÷ n SE = s ÷ √n 한 번의 추정 고리 정지 규칙 SE ≤ 목표 오차 ε ? 아니오 — 표본 추가 예 보고 μ̂ ± 1.96 × SE 편향 원인 — 모형 오류 · 난수 품질 · 시드 겹침 난수 · 시드 표본 · 실험 추정 · 오차 정지 규칙 편향 원인 반복 경로 영향

그림 3 · 난수 생성기가 만든 표본을 함수로 평가해 평균과 표준 오차를 내고, 목표 오차에 못 미치면 표본을 더 뽑는다 — 편향 원인은 이 고리 밖 모형과 난수에서 들어온다.

요소역할값 · 근거
난수 생성기균등 난수열을 만든다Python = 메르센 트위스터 · 주기 2^19937 − 1 · 53비트 실수(Python random)
시드난수열의 시작 값같은 시드 = 같은 결과 · 병렬 작업은 시드 + 작업 번호 금지(NumPy parallel)
표본 · 함숫값f(xᵢ) 를 n 번 계산표본끼리 독립 · 같은 분포(Owen 2013 2.1절)
추정량 μ̂f 값의 평균불편 추정 · 큰 수의 법칙으로 μ 에 수렴
표준 오차추정의 흔들림SE = s ÷ √n · 95% 구간 μ̂ ± 1.96 SE · 99% 는 2.58(Owen 2013 2.2절)
정지 규칙표본을 언제 멈추나목표 오차 ε 이면 n ≥ (1.96 s ÷ ε)²

🔑 표본 수는 흔들림(분산)만 줄이고 편향은 줄이지 못한다 — 모형 · 분포 · 난수가 틀린 계산은 n 을 백만으로 늘려도 같은 쪽으로 틀린다.

5동작 — 점 10,000개로 원주율을 추정하는 계산

단위 정사각형에 고르게 뿌린 점이 사분원 안에 들 확률이 π/4 라는 점을 써서 π 를 추정한다. 사례는 Python 3.14.0 random.Random(0) 으로 직접 실행한 값이다.

  1. 문제를 기댓값으로 바꾼다 — X, Y 가 [0, 1) 균등 분포이면 f = 1(X² + Y² ≤ 1) 의 기댓값이 π/4 이므로 π = 4 × E[f] 다.
  2. 시드 0 으로 난수 생성기를 만든다 — 시드를 기록해야 같은 결과를 다시 낼 수 있다(Python random).
  3. 점 하나에 난수 두 개를 쓴다 — 첫 점 (0.8444, 0.7580) 은 x² + y² = 1.29 라 밖(0), 둘째 (0.4206, 0.2589) 는 0.24, 셋째 (0.5113, 0.4049) 는 0.43 이라 안(1)이다.
  4. 10,000점 가운데 7,838점이 안에 들어 π̂ = 4 × 0.7838 = 3.1352 다(참값과 차 0.0064).
  5. 표준 오차를 붙인다 — s = 4 × √(0.7838 × 0.2162) = 1.647, SE = 1.647 ÷ √10,000 = 0.01647 이라 95% 구간은 3.1029 ~ 3.1675 이고 π 를 품는다.
  6. 목표 SE 0.01 이하로 정하면 n ≥ (1.647 ÷ 0.01)² ≈ 27,100 이므로 40,000점으로 늘린다 — π̂ = 3.1484 · SE = 0.00819 로 흔들림이 절반이 된다.
  7. 구간을 검증한다 — 시드 1 ~ 100 으로 10,000점 계산을 100번 돌리면 95% 구간이 π 를 품은 횟수가 97번이다.
0 1 1 x y x² + y² ≤ 1 = 안 P1 밖 P2 안 P3 안 단계별 값 — 시드 0 3 P1 1.29 → 0 · P2 0.24 → 1 · P3 0.43 → 1 4 n = 10,000 → 안 7,838개 π̂ = 4 × 0.7838 = 3.1352 5 SE = 1.647 ÷ √10,000 = 0.01647 95% 구간 3.1029 ~ 3.1675 6 n = 40,000 → π̂ 3.1484 SE 0.00819 — 4배 표본, 절반 오차 번호 = 동작 목록 단계 · 점 = 첫 점 셋만 표시 · 판정 값 = x² + y²(소수 둘째 자리)

그림 4 · 첫 점 셋 가운데 둘이 사분원 안에 들었고, 10,000점의 비율 0.7838 이 π̂ 3.1352 ± 0.0323 을, 40,000점이 흔들림 절반을 주었다.

오차(로그 눈금) 1 0.1 0.01 0.001 0.0001 10² 10³ 10⁴ 10⁵ 10⁶ 표본 수 n(로그 눈금) 기울기 −1/2 n 4배 → SE 절반(0.01647 → 0.00819) 표준 오차 SE = 1.642 ÷ √n 95% 한계 1.96 × SE 실제 |π̂ − π|(시드 0) 1.642 = 4 × √(π/4 × (1 − π/4)) · 각 n 은 같은 난수열의 앞 n 점

그림 5 · 표본 수를 100배 늘려야 오차가 10배 준다 — 실제 오차 점들은 기울기 −1/2 인 표준 오차 선 둘레에서 95% 한계 아래에 머문다.

🔑 몬테카를로의 정확도는 «몇 번 돌렸나»가 아니라 «√n 이 얼마인가»로 정해진다 — 자릿수 하나를 더 얻으려면 계산이 100배 든다.

6비교 — 라스베이거스 알고리즘 · 구적법 · 준몬테카를로와의 차이

기준몬테카를로라스베이거스 알고리즘결정적 구적법(심프슨)준몬테카를로(QMC)
점 · 선택난수 표본난수로 피벗 · 순서 선택정해진 격자저불일치 수열(결정적)
답의 보장확률적 오차 · 오답 확률답은 늘 맞음오차 한계 식결정적 오차
실행 시간표본 수로 정해짐난수에 따라 변함격자 수로 정해짐점 수로 정해짐
오차 수렴O(n^−1/2) · 차원 무관해당 없음1차원 O(n^−4) · d 차원 O(n^−4/d)(Owen 2013 2.1절)매끄러운 함수에서 몬테카를로보다 빠름
오차 추정표본으로 SE 계산필요 없음도함수 크기를 알아야 함어려움 → 무작위화 QMC(Owen 2013 1장)

분석차원이 3 ~ 4 이하이고 함수가 매끄러우면 구적법, 차원이 높거나 함수가 불연속 · 모의 실험 형태면 몬테카를로, 정답이 꼭 맞아야 하고 시간이 흔들려도 되면 라스베이거스 알고리즘을 고른다. 근거는 표의 「오차 수렴」 행 — d 차원 심프슨 O(n^−4/d) 는 d = 8 에서 몬테카를로와 같은 O(n^−1/2) 가 된다.

7실무 진단 — 믿기 어려운 추정값의 원인 가르기

분석같은 입력을 시드만 바꿔 여러 번 돌려 «흔들림»과 «어긋남»을 먼저 가른다. 흔들림은 SE 로 설명되고(Owen 2013 2.2절) 어긋남은 SE 로 설명되지 않는 편향이기 때문이다.

#증상의심 원인단계확인 자료판정 기준(근거)
1실행마다 값이 크게 다름표본 수 부족 · 분산 큼표본 수시드별 μ̂ 의 퍼짐 · SE퍼짐 ≈ SE 면 정상 → n 을 (1.96 s ÷ ε)² 로(Owen 2013 2.2절)
2n 을 늘려도 한쪽으로 어긋남분포 · 모형 오류모형답을 아는 문제(π · 평균)로 같은 코드 시험오차 > 3 SE 가 되풀이되면 편향
3병렬 작업 결과가 서로 겹침시드 + 작업 번호로 시드를 만듦난수작업별 첫 난수 비교같은 결과가 나오면 독립 스트림(SeedSequence.spawn)으로(NumPy parallel)
4같은 설정인데 재현이 안 됨시드를 기록하지 않음난수실행 기록의 시드 필드시드를 고정해 같은 값이 나와야 정상(Python random)

가려내는 순서는 시드 → 표본 수 → 모형이다. 시드 문제는 실행 기록만 보면 바로 끝나고, 표본 수 문제는 계산을 늘리면 풀리지만, 모형 문제는 답을 아는 시험 문제를 따로 만들어야 하기 때문이다.

8시험 대비

출제 정보 정보관리(123회, 117회, 113회, 80회) · 컴퓨터시스템응용(135회, 131회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 원리 · 절차 · 오차 특성을 묻는 정의 · 특징형이 나올 수 있고, 라스베이거스 알고리즘이나 결정적 수치 적분과의 차이를 묻는 비교형이 나올 수 있다. 밀러-라빈 판정처럼 무작위 알고리즘의 예를 함께 쓰면 «알고리즘 설계 기법» 관점이 선다.

답안 목차
  1. 개요 — 정의 · 난수 표본 평균으로 기댓값 · 적분 근사 · 1949 Metropolis · Ulam
  2. 구성 요소 — 그림 3 추정 고리(확률 모형 · 난수 생성기 · 표본 · 함수 평가 · 추정 · 정지 규칙) + 요소 표
  3. 절차 사례 — 그림 4 원주율 추정(10,000점 · 7,838점 · π̂ 3.1352 · 95% 구간)
  4. 오차 특성 — 그림 5 오차 그래프(SE = s ÷ √n · 기울기 −1/2 · 4배 표본 = 절반 오차 · 차원 무관)
  5. 비교 — 라스베이거스 · 구적법 · 준몬테카를로 비교표 5행(답의 보장 · 실행 시간 · 오차 수렴)
  6. 활용 · 한계 — 밀러-라빈(1,024비트 소수 4회 · 오류 확률 2^−100 · FIPS 186-5 표 B.1) · 느린 수렴 → 분산 감소 · QMC

꼭 쓸 키워드
난수 표본기댓값큰 수의 법칙표준 오차O(n^−1/2)신뢰구간시드의사 난수라스베이거스 알고리즘분산 감소

9오해와 사실

  • 오해몬테카를로 결과는 표본을 충분히 늘리면 항상 참값에 다가간다.
    사실표본 수는 분산만 줄이므로, 분포 · 모형이 틀리거나 시드를 겹쳐 쓴 편향은 n 을 늘려도 그대로 남는다(NumPy parallel 의 시드 + 작업 번호 경고).
  • 오해고차원 문제는 몬테카를로도 차원이 늘수록 급격히 느려진다.
    사실오차 σ ÷ √n 에는 차원 d 가 들어 있지 않고, 차원이 늘수록 느려지는 쪽은 O(n^−4/d) 인 격자 구적법이다(Owen 2013 2.1절).
  • 오해몬테카를로 판정은 틀릴 수 있어 암호 표준에 쓰지 않는다.
    사실FIPS 186-5 는 RSA 소수 생성에 밀러-라빈 판정을 쓰고, 1,024비트 소수는 4회 반복으로 오류 확률을 2^−100 이하로 낮춘다(부록 B.3 · 표 B.1).

10핵심 정리

구분맡는 일식 · 값결정 요인확인 방법
난수 생성기균등 난수열메르센 트위스터 · 주기 2^19937 − 1시드 · 독립 스트림시드 고정 재실행
표본 추출분포에서 xᵢ 뽑기xᵢ 독립 · 같은 분포확률 모형답을 아는 문제로 시험
함수 평가f(xᵢ) · 모의 실험 1회f = 1(x² + y² ≤ 1) 등문제 정의표본 몇 개 손계산
추정량기댓값 근사μ̂ = Σf ÷ n표본 수 n시드별 μ̂ 비교
표준 오차흔들림 크기SE = s ÷ √n · 95% ± 1.96 SE분산 · n구간이 참값을 품는 비율
정지 규칙반복 종료n ≥ (1.96 s ÷ ε)²목표 오차 εSE ≤ ε
편향줄지 않는 오차n 과 무관모형 · 난수 품질오차 > 3 SE 반복

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ The Monte Carlo Method (N. Metropolis · S. Ulam · Journal of the American Statistical Association 44(247) 335-341) — 방법의 이름이 처음 붙은 발표를 볼 때
    American Statistical Association · 1949-09 · doi.org/10.1080/01621459.1949.10483310 · 확인 2026-11-14
  3. ★ Stan Ulam, John von Neumann, and the Monte Carlo Method (R. Eckhardt · Los Alamos Science 15 131-141) — 1946 · 1947 년 방법이 생긴 경위를 볼 때
    Los Alamos National Laboratory · 1987-01 · mcnp-green.lanl.gov/pdf_files/Article_1987_LAS_Eckhardt_131--141.pdf · 확인 2026-11-14
  4. ★ Monte Carlo theory, methods and examples (A. B. Owen) — 표준 오차 · 신뢰구간 식과 차원별 수렴 속도를 볼 때
    Stanford University · 2013-01 · artowen.su.domains/mc/ · 확인 2026-11-14
  5. ★ FIPS 186-5 Digital Signature Standard (DSS) — 밀러-라빈 판정의 반복 횟수와 오류 확률을 볼 때
    NIST · 2023-02 · nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf · 확인 2026-11-14
  6. ★ random — Generate pseudo-random numbers (Python 3 documentation) — 시드 · 메르센 트위스터 주기 · 보안 용도 제한을 볼 때
    Python Software Foundation · 2026-11 · docs.python.org/3/library/random.html · 확인 2026-11-14
  7. 본문 근거
  8. Parallel Random Number Generation (NumPy documentation) — NumPy Developers · 2026-11 · numpy.org/doc/stable/reference/random/parallel.html · 확인 2026-11-14