Theory/Algorithms (35) 썸네일형 리스트형 몬테카를로 시뮬레이션 (5) - 적분 계산하기 몬테카를로 시뮬레이션 (1) - 파이 계산하기 몬테카를로 시뮬레이션 (2) - 온라인 판매자 예제 몬테카를로 시뮬레이션 (3) - 부트스트랩 알고리즘 (bootstrap) 몬테카를로 시뮬레이션 (4) - 범용 몬테카를로 엔진 1차원 적분 몬테카를로 시뮬레이션을 이용해서 충분히 매끈한 곡선을 가지는 피적분 함수에 대해 적분을 계산할 수 있습니다. (충분히 매끈하다는 것은 수학적으로 무한차원의 미분이 가능하다는 것이지만 여기서는 1차원 미분이 가능하다고 가정하겠습니다.) 먼저 $[a,b]$ 사이에서 정의된 $f(x)$ 적분은 다음과 같이 정의됩니다. $I = \int_a^b f(x) dx$ 몬테카를로 적분의 시작은 다음 식들을 만족하는 두 개의 함수 $g(x), p(x)$를 정의하는 것입니다. $p(x) =.. 몬테카를로 시뮬레이션 (4) - 범용 몬테카를로 엔진 몬테카를로 시뮬레이션 (1) - 파이 계산하기 몬테카를로 시뮬레이션 (2) - 온라인 판매자 예제 몬테카를로 시뮬레이션 (3) - 부트스트랩 알고리즘 (bootstrap) 이제까지 다뤘던 몬테카를로 포스트들을 기반으로 일반적으로 사용할 수 있는 범용 몬테카를로 엔진을 구현해보도록 하겠습니다. MCEngine 클래스는 여러 일반적인 몬테카를로 계산 및 시뮬레이션 문제들이 상속하여 사용할 수 있는 부모 클래스로서 "simulate_once", "simulate_many" 메소드로 구성됩니다. class MCEngine: """ Monte Carlo Engine parent class. Runs a simulation many times and computes average and error in averag.. 몬테카를로 시뮬레이션 (3) - 부트스트랩 알고리즘 (bootstrap) 몬테카를로 시뮬레이션 (1) - 파이 계산하기 몬테카를로 시뮬레이션 (2) - 온라인 판매자 예제 모든 몬테카를로 시뮬레이션의 결과는 데이터 $x_i$가 가우스 분포를 따를 때 다음과 같은 평균입니다. $\mu=\frac{1}{N}\Sigma x_i$ 따라서 이 평균의 오차는 다음과 같이 추정할 수 있는데요, $\delta_{\mu}=\frac{\sigma}{\sqrt{N}}=\sqrt{\frac{1}{N}(\frac{1}{N}\Sigma x_i^2 - \mu^2)}$ 하지만 데이터가 정규 분포를 따른다는 가정이 꼭 필요할까요? 그리고 모집단으로부터 추출된 한정된 샘플들만을 가지고 정확한 모수의 분포를 추정할 수 있을까요? 이때 가장 범용적으로 사용될 수 있는 방법은 부트스트랩 알고리즘입니다. (boot.. 몬테카를로 시뮬레이션 (2) - 온라인 판매자 예제 몬테카를로 시뮬레이션 (1) - 파이 계산하기 쇼핑몰을 운영하는 온라인 판매자가 있습니다. 애널리틱스를 통해 분석해보니 하루에 접속하는 사람이 평균 976명이고 표전편차는 352인 가우스 분포를 가짐을 알았습니다. 또한, 재고가 있을 때는 5% 확률로 구매하고 재고가 없을 때는 2% 확률로 구매한다는 것 또한 알았습니다. (재고가 없으면 당연히 물건을 팔 수 없겠지만 예제이니 재고가 없어도 물건을 팔 수 있다고 가정합니다.) 판매자는 개당 100달러인 물건의 재고를 $N$개를 유지하고 한 개의 재고를 유지하는데 하루에 30달러를 지불합니다. (업무 종료 시에 한 번에 지불합니다.) 그렇다면 판매자의 평균 일일 수입을 최대화하는 최적의 재고 개수 $N$값은 얼마일까요? 이러한 문제는 수식으로 만들기도 애매.. 몬테카를로 시뮬레이션 (1) - 파이 계산하기 몬테카를로 기법은 결과를 계산하기 위해 반복적인 무작위 샘플링에 의존하는 알고리즘으로서 거의 모든 자연과학, 공학 분야에 응용됩니다. 이번 포스트에서는 간단한 몬테카를로 시뮬레이션으로 파이를 ($\pi$) 계산해보도록 하겠습니다. 테일러 급수 이용하기 $\pi$를 계산하는 표준 방법은 수학적인 정의를 적용하는 것입니다. 우리는 $\pi/4$의 탄젠트 (tangent) 값이 1임을 알고 있으므로 다음과 같이 탄젠트 함수의 역수인 arctangent로 $\pi$를 정의할 수 있습니다. $\pi=4*arctan(1)$ 공학 수학을 배우신 분들이라면 arctangent 함수는 다음과 같이 테일러 급수로 전개할 수 있음을 아실 겁니다. (테일러 급수는 미적분학에서 무한 번 미분이 가능한 함수를 도함수들의 한 점에.. Cholesky Decomposition (촐레스키 분해) - 파이썬 구현 [알고리즘 & 코딩테스트/코딩테스트] - 파이썬으로 행렬 구현하기 (4) - 마무리 지난 포스트에서 numpy 없이 구현한 행렬을 이용해 cholesky decomposition (촐레스키 분해) 를 해보도록 하겠습니다. 먼저 정방행렬 $A$가 있을 때, $x\neq 0$인 모든 $x$에 대해 $x^tAx>0$ 이면 이 행렬 $A$를 positive definite 하다고 합니다. ($x^tAx\geq 0$인 경우 semi-positive definite 하다고 합니다) 이때 행렬 $A$가 대칭이고 positive definite 하다면 $A=LL^t$를 만족하는, 대각 위의 성분이 모두 0인 하삼각행렬 (lower triangular matrix) $L$이 존재하게 되는데, $A$로부터 $L$을 구하는.. Trie 네이버나 구글에서 검색 시 찾고자 하는 검색어의 일부분만 쳐도 추천하는 검색어가 자동완성되는 기능을 많이 접해보셨을 겁니다. 이때 사용하는 알고리즘이 Trie 로서 문자열 길이만큼의 시간복잡도가 소요되어 빠르고 간단합니다. Trie 알고리즘은 Figure 1과 같이 노드를 이용한 트리 형태로 구성되고 트리의 각 노드는 해당하는 문자와 사전형태로 이루어진 자식 노드, 문자열의 끝을 알리는 플래그로 구성됩니다. Hashable한 딕셔너리가 사용되므로 ($O(1)$) 주어진 prefix 길이만큼의 시간복잡도로 prefix를 공유하는 모든 문자열을 파악할 수 있습니다. Implementation 먼저 트리를 구성할 노드를 정의합니다. 인자로 해당 노드의 문자 (char), 플래그로 사용할 전체문자열 (data).. Sparse Matrix (희소행렬) 구현하기 행렬 곱하기는 행렬 크기가 클수록 많은 연산량이 소요됩니다. 만약 행렬에 0이 대부분이고 0이 아닌 요소가 (non-zero elements) 매우 적은 경우 0은 곱연산에 의미가 없으므로 일반적인 행렬 곱연산은 비효율적이겠죠. 이럴때 효율적으로 행렬 곱을 수행할 수 있는 방법은 sparse matrix (희소행렬) 형태로 행렬을 재구성하는 것입니다. 희소행렬은 0이 아닌 요소에 대해서만 (행 인덱스, 열 인덱스, 값)을 가진 형태로 0이 아닌 요소만 저장하고 불필요한 0인 요소는 따로 저장하지 않습니다. Scipy 라이브러리의 sparse matrix 모듈에 관련 함수들이 구현되어 있고 이번 포스트에서는 raw한 파이썬으로 구현해보도록 하겠습니다. Data structure 먼저 희소행렬을 구성하기 위.. 이전 1 2 3 4 5 다음
