게임 클라 개발

개요 알고리즘이나 자료 구조의 성능을 볼 때 amortized analysis란 단어를 많이 보게 된다. 이걸 한국어로 번역하면 분할 상환 분석이라는 생소한 단어가 나와 헷갈리는데, 간단히 말하면... 성능을 분석함에 있어서 "N개의 시퀀스를 수행할 때의 평균 시간을 측정했다." 라는 의미이다. 왜 이러냐? dynamic array를 한번 생각해보자. dynamic array는 capacity가 꽉 찬 상태에서 add가 일어날 경우, 흔히 doubling 이라 불리우는 비싼 연산을 수행한다. 따라서 dynamic array의 Add 연산의 시간 복잡도는 얼마인가? 라고 묻는다면 대부분의 경우에는 O(1)이겠지만 doubling이 일어날 때는 O(n) (n은 현재 array에 있는 요소의 갯수)이라고 할 ..

개요 알아둘 만한 알고리즘 및 자료구조를 정리. 해당 알고리즘에 대해 자세히 알아보는 게 아니라 나중에 '아 이런 게 있었지. 하며 찾아볼 수 있도록 하는 용도.' 여기 나열된 게 최선의 알고리즘은 아닐 수 있으므로 어디까지나 구글링의 시작점으로 활용해야 한다. (ex. 경로의 가중치가 음수인 경로를 구하고 싶다면 벨먼 포드를 쓰는게 아니라 벨먼 포드보다 나은 알고리즘을 검색해본다.) 너무 기초적인 것(ex. KMP)은 다루지 않는다. 일반 펜윅트리, 세그먼트트리의 Lazy Propagation 구간 자체를 업데이트할때 쓸 수 있다. 백준 문제 (백준 2934 - LRH 식물)가 있다. 세그먼트트리랑 비슷함. 희소 테이블 (Sparse Table) 어 대충 정적인 Array의 1,2,4,8,16... 번..

문제 위와 같이 2차원 평면에 벡터 $\overrightarrow{AB}$가 있다. 점 C는 왼쪽방향 혹은 반시계방향(CCW)이고 점 D는 오른쪽방향 혹은 시계방향(CW)라고 할 수 있다. 이때 점C와 점D가 CW인지 CCW인지를 어떻게 판별할 수 있을까? 벡터의 외적으로 알아내기 두 3차원 벡터 $\overrightarrow{a}$와 $\overrightarrow{b}$가 있다. 이때 두 벡터의 외적은 다음과 같이 정의할 수 있다. $\overrightarrow{a}\times\overrightarrow{b} = \hat{n}\vert\overrightarrow{a}\vert \vert\overrightarrow{b}\vert\sin\theta$ $\theta$는 두 벡터의 각도이며 $\hat{n}$은..