몬테카를로 알고리즘

Warning

Over a year old. May be outdated

몬테카를로 알고리즘은 무작위 샘플링으로 복잡한 문제의 대략적인 답을 구하는 확률적 방법이다. 이름처럼 몬테카를로 카지노의 무작위성에서 따온 방법인데, 무작위 시뮬레이션을 잔뜩 돌려서 원하는 값을 추정한다. 예를 들어 π를 구한다고 해 보자. 원이 그려진 정사각형에 다트를 아무렇게나 던지고, 던진 다트 중에 원 안에 들어간 비율을 보면 π를 추정할 수 있다. 금융, 물리학, 게임 이론, 그래픽 같은 데서 두루 쓰이고, 기존 방법으로는 버거운 복잡한 시스템이나 고차원 공간도 다룰 수 있다. 근데 보통 정확도가 느리게 올라가서, 더 정밀한 답을 원하면 샘플이 훨씬 많이 필요하다.

재밌는 건, 몬테카를로 알고리즘은 추산치를 엄청 빨리 내놓지만 아주 낮은 확률로 값이 크게 틀린다는 점이다. 빠른 시간을 보장받는 대신 정확도에 리스크를 거는 셈이다. 계산 이론에서 꽤 재밌는 부분이다.

Backlinks3

이화여대 GDG 세미나 몬테카를로와 라스베가스 알고리즘 라스베가스 알고리즘