반드시 알아야하는 알고리즘 top 8 - 8. 몬테 카를로 알고리즘

반드시 알아야 하는 알고리즘 top 8 

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

몬테 카를로 알고리즘 

• 프랑스의 공국중 하나인 모나코엔 도박으로 라스베가스보다 유명한 도시가 있는데 그곳이 바로 몬테 카를로(Monte Carlo)입니다. 몬테 카를로 알고리즘은 난수생성과 그에 따른 확률계산을 기반으로 하는 알고리즘인데 알고리즘의 개발자인 스타니스와프 울람이 난수와 확률계산을 도박에서 연상시켜 알고리즘 이름을 몬테 카를로 알고리즘으로 명명했습니다. 처음엔 난수생성과 그에 따른 확률 계산으로 수치 계산에 사용되었고 이것을 응용하여 모르는 함수나 자료에 대한 시뮬레이션 기법으로 사용되다가 2000년대 들어서서 여러 트리탐색 기법들과 결합되어 몬테카를로 트리탐색법으로 발전하였습니다.

• 대표적인 예제로는 원주율 구하기, 뷔퐁의 바늘 등이 있으나 최근에는 강화학습등에서 기본알고리즘으로 사용되며 그 사용처가 무궁무진하게 증가하는 추세입니다.

몬테 카를로 알고리즘의 기본 개념 

무작위로 난수(랜덤 수)를 생성 한다.

무작위로 난수(랜덤 수)를 기반으로 사용해서 구하고자 하는 정보의 확률을 계산 한다.

난수 생성이 무한에 가까워 질 경우 우리가 원하는 정보의 실제 값으로 근사 한다.

• 현실에서 우리가 만나는 문제들을 풀어내기 위해 얻을 수 있는 데이터들은 매우 적고 한정되있는 편이다. 이런 경우 문제를 풀기 위해서는 여러 변수들을 제외하여 실제보다는 단순하게 모델을 구성한 뒤에 수많은 케이스를 가지고 모델을 실험하는 방법이 있다. 이렇게 실험할 경우 실험횟수가 점점 많아질 수록 얻는 값은 실제 값에 근사하게 된다는 것이 몬테 카를로 알고리즘의 기본 구조 이다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^