기록기록 우는 갈매기

Monte Carlo 알고리즘은 backtracking 알고리즘의 성능을 추정할 때 사용하는 알고리즘이다. Monte Carlo 알고리즘은 어떤 입력이 주어졌을 때 그에 따라 생성되는 상태공간트리의 전형적인 경로를 무작위로 생성하고 그 경로상에 있는 노드의 수를 센다. 이 과정을 여러 번 반복하여 나오는 결과의 평균치가 곧 추정치가 된다. 이처럼 Monte Carlo 알고리즘은 무작위 표본의 추정치를 사용하여 무작위 변수의 기대치를 측정하는 확률적 알고리즘이다. 이 알고리즘을 사용하기 위해 만족해야할 조건 2가지는 아래와 같다. ① 상태공간트리에서 같은 수준(level)에 있는 모든 노드에서는 같은 유망함수를 사용해야 한다. ② 상태공간트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가지..

이진탐색 알고리즘이란? 크기가 n인 정렬된 배열 s에 x가 있는지 결정하는 재귀 알고리즘 알고리즘 설계 전략 배열의 중간에 위치하고 있는 값이 x와 같은 경우 성공을 리턴, 그렇지 않으면 분할(Divide) 분할(Divide) : 배열을 반으로 나누고, x가 배열의 중간에 있는 값보다 작으면 왼쪽 배열을 선택(오른쪽 배열은 버림), 크면 오른쪽 배열을 선택(왼쪽 배열은 버림). 정복(Conquer) : 선택한 배열을 갖고 다시 x를 찾는다. 알고리즘 수도 코드 index location (index low, index high) { index mid; if(low > high) return 0; else { mid = ⌊(low+high) / 2⌋; //배열 가운데 값을 구함 if (x == s[mid]..