몬테카를로 알고리즘

컴퓨터 공학 스터디 W1.자료구조와 알고리즘, 언어론👻

몬테카를로 알고리즘

몬테카를로 알고리즘이란 무작위로 난수 즉 랜덤수를 생성한 후, 무작위 난수를 기반으로 생성해서 구하고자 하는 정보의 확률을 계산하는 알고리즘이다. 난수 생성이 무한에 가까워질 경우 우리가 원하는 정보의 실제값으로 근사하다.
현실에서 우리가 만나는 문제들을 풀어내기 위해 얻을 수 있는 데이터들은 매우 적고 한정되어 있다. 이런 경우 문제를 풀기 위해서는 여러 변수들을 제외하여 실제보다는 단순하게 모델을 구상한 뒤에 수많은 케이스를 가지고 모델을 실험하는 방법이 있습니다. 이렇게 실험할 경우 실험 횟수가 점점 많아질 수록 얻는 값은 실제값에 근사하게 된다는 것이 몬테카를로 알고리즘의 기본 구조이다.

⚙️ 계산

몬테카를로 알고리즘은 반복적이고 큰 수를 계산해야하기 때문에 실제로 계산하는 것보다는 컴퓨터로 계산하는 것이 빠르고 효율적이다.

이 알고리즘은 수학적인 결과를 얻기 위해 반복적으로 무작위 샘플링의 방법을 이용하는 넓은 범위의 컴퓨터 알고리즘이다. 몬테카를로 알고리즘은 문제를 해결하기 위해 무작위성을 이용한다.

😆 패턴

몬테카를로 방법은 다양하지만 특정한 패턴을 따르는 경향이 있다.
1. 가능한 입력의 도메인을 정의한다.
2. 도메인에 대한 확률 분포에서 임의로 입력을 생성한다.
3. 입력에 대한 결정론적인 계산을 수행한다.
4. 결과를 집계한다.
위의 4가지 단계가 몬테카를로 알고리즘의 특정한 패턴이다.

🔥 예시

몬테카를로 알고리즘의 예시로는 원주율 구하기가 있다. 다음과 같은 사진처럼 몬테카를로 방법을 이용하여 원주율을 계산할 수 있다.이미지 출처: 위키백과

원주율을 구하는 방법의 순서는
1. 정사각형을 그린 후 그 안에 사분면을 삽입한다.
2. 정사각형 위에 일정한 개수의 점을 균일하게 분포한다.
3. 사분면 내부의 점, 즉 원점으로부터 1만의 개수를 센다.
4. 내부의 개수와 전체 개수의 비율은 두 영역의 비율을 나타내므로 그 값에 4를 곱하여 파이를 만든다.
이렇게 총 4단계가 된다.

여기서 중요한 사항이 있다. 점이 균일하게 분포되지 않으면 근사치가 떨어진다는 것과 평균적으로 더 많은 점을 배치하도록 근사치가 개선된다는 점이다.

🧸 예제코드

예제코드는 C언어로 구현하였다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, const char * argv[]) {
    int i = 0;
    double x = 0;
    double y = 0;
    double circle = 0;
    double count = 0;
    
    srand((double)time(NULL));
    
    while(1) {
        for(i = 0; i <1000000; i++) {
            x = (double)rand()/(double)RAND_MAX;
            y = (double)rand()/(double)RAND_MAX;
            count++;
            if((x*x) + (y*y) <= 1){
                circle++;
            }
        }
        printf("n = %0.0f, pi = %0.15f\n",count,(circle/count) *4);
    }
}

난수를 생성하여 while문으로 x와 y의 값을 프린트하는 코드이다. 이 코드의 실행결과는

다음과 같이 계속 나오게 된다.

❗️ 사용

몬테카를로 알고리즘은 수학, 물리학에서 사용하며 다양한 방법으로 접근이 불가능할 경우에도 사용된다. 또한 계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우 근사적으로 계산할때 사용된다. 닫힌 형식이란 미분 기하학에서 사용하는 단어이며 근사적은 어떤 최적화 문제에 대한 해의 근사 값을 구하는 알고리즘인 근사 알고리즘을 의미한다.