Enlightenment in the shadow

numpy 같은 라이브러리 없이도 행렬의 회전, 전치행렬에 대해서 한 줄로 간단하게 변환시킬 수 있어서 함수로 작성해 여기에 기록해둔다. def rotate(M, dir='left'): if dir == 'left': # left 90 degree rotate out = list(reversed(list(map(list, zip(*M))))) elif dir == 'right': # right 90 degree rotate out = list(map(list, zip(*reversed(M)))) elif dir == 'transpose': # transpose matrix out = list(map(list, zip(*M))) else: print('choose dir "left"/"right"/"tra..

문제 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 $(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 $(N-1, M-1)$이다. 즉, 좌표 $(r, c)$는 북쪽에서 $(r+1)$번째에 있는 줄의 서쪽에서 $(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다. 로봇 청소기..

코테 문제를 풀다 효율적인 계층적 구조의 다중 필터링 알고리즘이 필요해서 여기에 기록해둔다. 예를 들어 8명이 각각 A, B, C, D 요소를 갖고 있다고 할 때, 첫 번째 필터로 가장 큰 A요소를 가진 사람을 찾고, 만약 여러 명이면 그 여러 명 중에서 가장 큰 B요소를 가진 사람을 찾고, 여기서도 여러 명이면 가장 작은 C요소를 가진 사람을 찾고 여기서도 여러 명이면 가장 작은 D요소를 가진 사람을 찾는 문제를 "계층적 구조의 다중 필터링" 알고리즘이라 칭했다. 각 필터가 독립적이지 않고 조건부로 얽혀있기 때문이다. 좀 많이 고민했는데, 현재 기준 가장 깔끔한 것 같은 알고리즘 구상은 아래와 같다. 상위 필터에서 단독으로 걸리는 가정은 생략했다. dic = {"A": [5, 5, 5, 5, 3, 5,..

아래는 numpy, pandas 없이 내림차순으로 랭크를 매기는 한 줄 코드이다. tmp_list = [10, -30, 50, 9, 8, 15] ranks = [sorted(tmp_list, reverse=True).index(ele) for ele in tmp_list] print(ranks) # [2, 5, 0, 3, 4, 1] 오름차순으로 랭크 매기려면 sorted의 reverse 인자를 없애면 된다.

올해 3월로 구직 시기를 잡고 스터디카페에서 오전 7시부터 저녁 11시까지 공부하는 게 요즘의 일상이다. 아침에 와이프와 같이 집을 나서 와이프는 출근하고 나는 스터디 카페를 가기 전 오늘따라 시장해서 아침을 먹고 가려고 뼈해장국 집에 들어갔는데 건설현장일을 하시는 듯한 차림의 어떤 아주머니 한 분이 옆테이블에 앉았다. 겨자소스 좀 넘겨줄 수 있냐고 말씀하셔서 드렸더니 중앙대 학생이냐 물으신다. (여기 지역이 상도역이라 중앙대가 가깝다) 출신도 아니고 학생도 아니지만 상황을 자세히 말씀드리긴 뭐해 대충 인사치레로 네 하고 대답했더니, 중앙대 병원에서 심혈관 담당의로 김상욱 교수님이란 분이 죽을뻔한 아들을 살리셨다 말씀하신다. 아 그러셨어요? 건강하게 회복돼서 다행이네요. 대답하고 침묵 속에 마저 식사를 ..

Importance Sampling은 기댓값을 계산하는 확률분포함수는 알고 있지만 표본을 생성하기 어려울 때 해당 확분포함수 대신에 표본을 생성하기가 쉬운 다른 확률 분포함수를 이용해 기댓값을 추정하는 방법이다. 즉 표본 $x$의 확률분포함수를 $p(x)$라 할 때 해당 표본에 대한 어떤 함수 $f(x)$의 기댓값은 아래와 같이 전개할 수 있게 된다는 것이다. $$ \begin{align} \Bbb{E}_{x \sim p(x)} [f(x)] &= \int_{x} p(x) f(x) dx \\ &= \int_{x} \frac{p(x)}{q(x)} q(x) f(x) dx \\ &= \Bbb{E}_{x \sim q(x)} \left [ \frac{p(x)}{q(x)} f(x) \right ] \end{align..

지난 포스팅에서는 deterministic system에서의 해밀턴 자코비 벨만 방정식(Hamilton-Jacobi-Bellman equation)에 대해 다루었다. Deterministic system에서는 시간에 대한 함수로서 상태 방정식(state equation)을 고려하지만, Stochastic system에서는 정의할 수 없는 외생변수의 영향력이 불확실성으로써 시간과 함께 모델링 된다. 여기서 이 불확실성은 랜덤 프로세스(Stochastic process)로 정의되어 시간과 함께 dynamics에 반영된다. 즉 물리적으로 정의하기 힘든 시계열 현상들에 대한 dynamical system을 정의할 때, 랜덤 프로세스가 함께 활용되어 모델링되고 이를 Stochastic system이라 정의한다. ..

1. Optimal Control problem 최적 제어(Optimal Control)는 아래의 그림에서 제어 입력(control) $\mathbf{u}(t)$을 디자인하여 cost $J$를 최소화시키면서 상태(state) $\mathbf{x}(t_0)$에서 $\mathbf{x}(t_f)$까지 도달하는 것을 목표로 한다. 여기서 위 시스템의 dynamics와 cost function을 다음과 같이 상정해보자. $$ \begin{align} \frac{d}{dt}\mathbf{x}&=f(\mathbf{x}(t), \mathbf{u}(t)) \label{eq1} \tag{1} \\ J(\mathbf{x}(t), \mathbf{u}(t), t_0)&=Q(\mathbf{x}(t_f), t_f)+\int_{t_..

1. Solution of GBM 먼저 아래의 기하 브라운 모형(Geometric Brownian Motion)을 살펴보자. $$ dS_t = \mu S_t dt + \sigma S_t dW_t \label{eq1} \tag{1} $$ 그리고 이걸 기반으로 $d \ln S_t$를 구하면 아래와 같다. 이 때 $\ln S_t$가 확률미분방정식 시스템인 S_t에 대한 함수이기 때문에 Ito's lemma로 2계 도함수까지 테일러 근사를 진행해야한다. Ito's lemma에 대한 자세한 설명은 "해밀턴 자코비 벨만 방정식 2(stochastic case)" 포스팅의 1. Ito's lemma 파트를 참고하면 된다. Ito lemma로 $d \ln S_t$에 대한 전미분을 시행하면 아래와 같다. $$ \begi..

1. Definition of Brownian motion 어떤 실수 값으로 된 랜덤 프로세스(Stochastic process)가 다음의 성질(property)을 따를 때 브라운 운동(Brownian motion)이라 칭한다. 1. $W(0)=0$ 2. $W(t)-W(s) \sim N(0, t-s)$, for t > s 3. $W(t_2)-W(t_1), W(t_3)-W(t_2), \cdots, W(t_n)-W(t_{n-1}) $들은 모두 독립이다. 위 2번째 성질에서 브라운 운동의 증분은 그 정의상 평균은 0, 분산은 time index의 거리가 된다. 즉 다음과 같이 일반화할 수 있다. $$ E[\Delta W] = 0 \\ $$ $$ \begin{align} Var[\Delta W] &= E[(\D..