몬테카를로 알고리즘

무작위 난수를 기반으로 특정 공간에 해당 난수가 존재할 가능성을 확인하는 알고리즘

몬테카를로 알고리즘은 큰 수와 반복적인 작업을 해야 하므로 직접적인 계산 보다는 시스템 및 함수 처리에서 무작위성을 사용하여 알고리즘을 해결한다.

---

특정한 패턴을 따르는 경향이 있다.

1. 가능한 입력의 도메인을 정의한다.
2. 도메인에 대한 확률 분포에서 임의로 입력을 생성한다.
3. 입력에 대한 결정론적인 계산을 수행한다.
4. 결과를 집계한다.

몬테카를로 알고리즘을 통한 문제 해결 예시는 대표적으로 원주율을 구하는 방식이다.

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

원주율을 구하는 실제 코드는 아래와 같다.

작성: java

import java.util.*;

public static double pie(){
	int roofNum = 100000;
    int count = 0;
    
    
    while( i != 100000){
    	double x = Math.random() * 2 - 1;
    	double y = Math.random() * 2 - 1;
        
        if((x*x) + (y*y) <= 1) {
        	count++;
        }
        
    	i++
    }
    
    double result = 4.0 * count / roofNum;
    return result;
}

---

참고

https://velog.io/@awt0311/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://walking-and-walking.com/entry/Java%EC%97%90%EC%84%9C-%ED%99%95%EB%A5%A0%EC%A0%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EA%B5%AC%ED%98%84-%EC%9D%B4%EB%A1%A0%EA%B3%BC-%EC%8B%A4%EC%A0%9C-%EC%82%AC%EB%A1%80