가장 단순한 몬테카를로 프로그램 중 하나부터 시작해 보겠습니다. 몬테카를로 프로그램에 익숙하지 않다면 잠시 멈추어 기본 개념을 익히는 것이 좋습니다. 무작위 알고리즘에는 몬테카를로와 라스베이거스 두 가지 유형이 있습니다. 무작위 알고리즘은 컴퓨터 그래픽스 전반에서 널리 사용되므로 탄탄한 기초를 다져두는 것이 좋습니다. 무작위 알고리즘은 계산 과정에서 어느 정도의 무작위성을 활용합니다. 라스베이거스 무작위 알고리즘은 항상 올바른 결과를 생성하는 반면, 몬테카를로 알고리즘은 올바른 결과를 낼 수도 있지만 종종 틀린 결과를 내놓기도 합니다! 하지만 레이 트레이싱처럼 특히 복잡한 문제의 경우 완벽한 정확성보다는 합리적인 시간 내에 답을 얻는 데 더 큰 우선순위를 둘 수 있습니다. 라스베이거스 알고리즘은 결국 올바른 결과에 도달하지만,そこに 도달하기까지 걸리는 시간에 대해서는 많은 보장을 할 수 없습니다. 라스베이거스 알고리즘의 대표적인 예는 퀵정렬 (quicksort) 정렬 알고리즘입니다. 퀵정렬 알고리즘은 항상 완전히 정렬된 목록으로 완료되지만, 완료되는 시간은 무작위입니다.라스베이거스 알고리즘의 또 다른 좋은 예시는 단위 원판 내에서 무작위 점을 선택하는 데 사용하는 코드입니다.
inline vec3 random_in_unit_disk()
{
while (true)
{
auto p = vec3(random_double(-1,1), random_double(-1,1), 0);
if (p.length_squared() < 1)
return p;
}
}
C++
복사
이 코드는 결국 단위 원 내부의 무작위 점에 도달하지만, 얼마나 오래 걸릴지는 미리 알 수 없습니다. 1 회 만에 끝날 수도 있고, 2 회, 3 회, 4 회, 혹은 그 이상 걸릴 수도 있습니다. 반면 몬테카를로 프로그램은 답에 대한 통계적 추정을 제공하며, 이 추정값은 실행 시간이 길어질수록 점점 더 정확해집니다. 즉, 특정 시점에서 답이 충분히 정확하다고 판단하고 작업을 중단할 수 있다는 뜻입니다. 노이즈가 있지만 계속 개선되는 답을 생성하는 이러한 단순한 프로그램의 기본 특성이 바로 몬테카를로의 핵심이며, 높은 정확도가 필요하지 않은 그래픽스와 같은 애플리케이션에 특히 적합합니다.
파이 추정하기
몬테카를로 알고리즘의 대표적인 예시는 π 을 추정하는 것이므로, 이를 수행해 보겠습니다. π 을 추정하는 방법은 여러 가지가 있으며, 그중 뷔퐁의 바늘 문제가 고전적인 사례 연구입니다. 뷔퐁의 바늘 문제에서는 폭이 모두 동일한 평행한 마루판으로 이루어진 바닥이 주어집니다. 바늘을 바닥에 무작위로 떨어뜨렸을 때, 바늘이 두 개의 마루판에 걸쳐 있을 확률은 얼마일까요? (이 문제에 대한 자세한 정보는 간단한 인터넷 검색으로 찾을 수 있습니다.)
이 방법에서 영감을 받은 변형 기법을 사용해 보겠습니다. 정사각형 안에 내접한 원이 있다고 가정해 봅시다:
그림 1: 정사각형 내부의 원을 사용하여 π 추정하기
이제 정사각형 내부에서 무작위 점들을 선택한다고 가정해 봅시다. 이 무작위 점들 중 원 내부에 위치하는 점들의 비율은 원의 면적에 비례해야 합니다. 실제로 정확한 비율은 원의 면적과 정사각형 면적의 비율이어야 합니다:
r 이 상쇄되므로, 계산상 편리한 값을 선택할 수 있습니다. 원점을 중심으로 하는 r=1 을 사용하겠습니다:
#include "rtweekend.h"
#include <iostream>
#include <iomanip>
int main()
{
std::cout << std::fixed << std::setprecision(12);
int inside_circle = 0;
int N = 100000;
for (int i = 0; i < N; i++)
{
auto x = random_double(-1,1);
auto y = random_double(-1,1);
if (x*x + y*y < 1)
inside_circle++;
}
std::cout << "Estimate of Pi = " << (4.0 * inside_circle) / N << '\n';
}
C++
복사
프로그램을 무한히 실행하면서 추정치를 계속 출력하도록 변경해 보겠습니다:
#include "rtweekend.h"
#include <iostream>
#include <iomanip>
int main()
{
std::cout << std::fixed << std::setprecision(12);
int inside_circle = 0; int runs = 0;
while (true)
{
runs++;
auto x = random_double(-1,1);
auto y = random_double(-1,1);
if (x*x + y*y < 1)
inside_circle++;
if (runs % 100000 == 0)
std::cout << "\rEstimate of Pi = " << (4.0 * inside_circle) / runs;
}
std::cout << "Estimate of Pi = " << (4.0 * inside_circle) / N << '\n';
}
C++
복사