Life is a mystery

오늘은 알고리즘 중에서 중요한 DP에 대해서 알아보도록 하자. 정의 DP란 memory table를 활용한 재귀 연산이라고 할 수 있다. 그렇다면 재귀 연산이란 무엇일까? Recursive Operation이라고도 하는데, 이 알고리즘은 반복하여 계산하는 것과 같다. 이전 포스팅의 Divide and Conquer를 생각해보면, 거기서도 재귀를 사용했었다. 그렇다면 재귀 연산의 간단한 예시를 보도록 하자. 피보나치 수열은 다음과 같이 정의된다. $A_{n+2} = A_{n+1} + A_{n}$ where $A_1 = 1, A_2 = 1$ 그렇다면 $A(n)$을 구하는데 어떻게 알고리즘을 설계할까? 바로 재귀를 이용해 다음과 같이 설계한다. Fib(n) if n == 1 or n == 2 : return ..

오늘은 알고리즘에서 말하는 divide and conquer 개념에 대해서 알아보자. Dynamic Programming을 들어가기 앞서서 알아두어야 할 문제해결 방법론이다. Divide and Conquer란 무엇인가? 바로, 주어진 문제를 여러 개의 단위로 쪼개서 해결한 뒤 해결된 것들을 합쳐서 최종적인 output을 낸다는 아이디어다. 그렇다면 여기서 해야 할 것은 무언인가? 바로, 독립적으로 해결 가능한 subproblem을 정의하고 optimal substructure를 정의하는 것이다. 독립적으로 해결 가능한 subproblem이라 함은 주어진 문제를 쪼갰을 때, 그 쪼갠 두 문제가 서로 독립적이어야 한다는 것이다. 그래야 서로 영향을 주지 않고, 두 문제 모두 해결하여 그 output을 합쳤..

오늘은 간단히 컴퓨터 과학 분야에서 흔히 사용되는 Big O notation의 의미를 얘기해보고자 한다. Big O notation이 사용되는 대상은 알고리즘에 대한 것이다. 어떤 알고리즘의 복잡도(complexity)가 얼마나 되느냐고 묻는 것과 같다. 조금 더 세분화해서 들어가면 복잡도는 1) 계산 복잡도, 2) 저장 복잡도로 얘기가 되기도 한다. 하지만 여기서는 그냥 계산 복잡도를 얘기하도록 하겠다. 어차피 계산 방식은 같기 때문에 Big O가 어떻게 계산되는지 알면 세분화된 내용들은 자동적으로 이해된다. Big O notation은 알고리즘의 복잡도를 설명할 때 사용되는 방식인데, 일단 2가지 방식으로 설명해보련다. 첫번째는 쉬운 방법으로 이해하면, Big O notation은 일종의 어림잡은 복..

머신러닝, 딥러닝에서 기본적으로 중요한 것은 수학이다. 물론 CS(컴퓨터 공학) 지식, domain knowledge도 필요한 건 맞지만 가장 필요한 것은 이것이다. 그래서 앞으로 이런 내용에 대해서 더 쓰고자 한다. 다룰 내용들은 다음과 같다. Linear Algebra Geometry Vector Calculus Probability Theory 이 책의 장점은 기본기가 되는 수학들을 심도있게 다룬다는 점이다. 동시에 후반부에는 수학을 활용한 응용들을 다룬다는 것이다. 머신러닝에서 알아야 하는 PCA(차원축소), EM(기대값 최대화) 등을 잘 다룬다.