간단한 예제와 함께 몬테카를로 방법을 알아보겠습니다.
몬테카를로 방법(Monte Carlo Method) 은 무작위 시행을 통한 확률적인 방법으로 함숫값을 구하는 방법입니다. 수학적 계산으로 함숫값을 구하는 것이 아니라, 무수한 수의 시행을 반복해서 임계선으로 정한 확률을 넘은 시행의 비율을 구하면 구하고자 했던 값에 매우 근사하게 된다는 원리입니다. 이 떄 이 ‘확률’은 엄밀한 의미의 확률이라기보다는, 원하는 결과를 도출하기 위해 시행 결과를 나누는 경계선으로 볼 수 있습니다.
몬테카를로 방법은 기본적으로 큰 수의 법칙을 기반으로 합니다. 임의의 모집단에서 샘플을 무수히 많이 뽑아내어 그 비율로 모집단에서의 비율을 추정하는 모습이기 때문입니다.
간단한 예를 들어, 몬테카를로 방법이 어떻게 구현되는지 보겠습니다. 사각형 내에서 특정 범위의 넓이를 구하는 문제를 풀고 있다고 가정하겠습니다. 초록색 사각형의 넓이를 알 때, 그 사각형 안에서 보라색 사각형의 넓이를 알고 싶습니다. 전체 사각형은 \((0, 0)\) 좌표의 점과 \((10, 10)\) 좌표의 점 사이로 만들어지는 사각형입니다. 보라색 사각형은 \((0, 0)\) 좌표와 \((2, 10)\) 좌표 사이로 만들어지는 사각형입니다. 따라서 전체 사각형의 넓이는 100이고, 보라색 사각형의 넓이는 20입니다. 아래의 그림들은 실제 그 비율을 맞춰서 그렸습니다.
이제 전체 사각형 내의 임의의 위치에 점을 찍는 시행을 반복합니다.
시행을 계속 반복하면, 점을 초록색 범위 내에 찍힌 것들과 보라색 범위 내에 찍힌 것들로 구분할 수 있습니다.
이 때, 전체 점 개수에 대한 보라색 범위 내 점들의 개수 비율을 구하면, 보라색 사각형의 대략적인 넓이를 알 수 있습니다. 전체 사각형의 넓이를 알고 있기 때문입니다. 시행을 많이 반복할수록 큰 수의 법칙에 따라 그 비율은 확실해질 것입니다. 이런 방법으로 무수히 많은 시행을 거쳐 보라색 사각형의 넓이를 알 수 있게 되는 것이고, 이것이 몬테카를로 방법입니다.
위의 예시를 간단히 C언어로 구현해보았습니다.
출력은 순서대로 보라색 범위 내 점의 개수, 전체 점의 개수, 보라색 범위 내 점의 비율, 그를 통해 구한 넓이입니다. 프로그램 실행 초기에 시행 횟수가 아직 적을 때에는 넓이 예측이 비교적 불안정했으나, 시행이 반복될수록 정확한 넓이인 20을 찾아가고 있는 것을 볼 수 있습니다.
시행의 횟수가 많아질수록 넓이는 정확해지고, 예측한 넓이 값의 변동도 작아집니다.
아래는 이를 구현한 C언어 코드입니다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct _coord {
float x;
float y;
}coord;
int main()
{
srand(time(NULL));
const coord max = { 10, 10 }; // 전체 사각형 네 점의 좌표 : 좌하단 점은 (0, 0)이므로, 우상단만 잡아줌
const coord squareLB = { 0, 0 }; // 보라색 사각형의 좌하단 점 좌표
const coord squareRT = { 2, 10 }; // 보라색 사각형의 좌상단 점 좌표
coord next = { 0, 0 }; // 임의로 찍는 점의 좌표
int totalPoints = 0, inPurple = 0; // 전체 점의 개수와, 보라색 사각형 내 점의 개수
float ratio; // 보라색 사각형 내 점 개수의 비율
while (1) {
// 랜덤한 점 좌표 생성
next.x = ((float)rand() / (float)RAND_MAX)*10;
next.y = ((float)rand() / (float)RAND_MAX)*10;
// 보라색 사각형 범위에 생성한 점의 좌표가 포함되어있는지 확인
if ((next.x > squareLB.x && next.y < squareRT.x) && (next.y > squareLB.y && next.y < squareRT.y)) {
inPurple++;
}
totalPoints++;
// 10만번의 시행마다 한번씩 결과 출력
if (totalPoints % 100000 == 0) {
ratio = (float)inPurple / (float)totalPoints;
printf("%d / %d, RATIO : %f, AREA : %f\n", inPurple, totalPoints, ratio, 100 * ratio);
}
}
return 0;
}