에라토스테네스의 체는 $O(nlog(logn))$의 시간 복잡도를 가지는 알고리즘으로, 효율적으로 소수(Prime Number)를 구할 수 있다. 소수: 1과 자기 자신 만을 약수로 가지는 수 아이디어는 간단하다. 자연수 N이 있을 때, N의 배수는 소수가 아니다. 소수는 1과 자기 자신만을 약수로 가지는데, N의 배수는 N을 약수로 가지기 때문이다. 소수의 정의를 생각해 보면 당연한 이야기이다. 1 ~ 100까지의 수가 있는 표를 만들자. 그리고 만약 소수가 아니라면 표에서 값을 지운다. 0과 1은 소수가 아니다. 0 1 2 3 4 5 6 7 8 ... 2는 소수이다. 하지만 2의 배수는 소수가 아니다. 따라서 4, 6, 8 ... 등은 지운다. 0 1 2 3 4 5 6 7 8 ... 3은 소수이다. ..
Quick Sort는 분할 정복을 이용한 정렬 알고리즘으로 평균적으로 좋은 성능을 보인다. 평균 시간 복잡도: $O(nlog_2n)$ 정렬된 리스트에 대해: $O(n^2)$ 정렬 원리 1 퀵 정렬의 아이디어는 생각보다 간단하다. 기준을 정한다. 기준보다 작으면 기준점의 왼쪽으로, 기준보다 크면 기준점의 오른쪽으로 모은다. 기준의 왼쪽과 오른쪽의 배열을 쪼갤 수 없을 때까지 재귀적으로 정렬한다. 이때 기준점을 pivot이라고 한다. 배열의 첫번째 값을 pivot으로 설정한 예시: 1. [5 4 3 1 6 2 7] 2. pivot: 5 [4 3 1 2] + [5] + [6 7] 3. pivot: 4, 6 [3 1 2] + [4] + [5] + [6] + [7] 4. pivot: 3, (우측은 정렬 완료) [..
Optimizer는 모델의 Training Loss를 최소화하는 방향으로 파라미터를 업데이트하는 중요한 역할을 한다. 쉽게 말해 모델을 어떤 방향으로 얼마만큼 업데이트할 것인지를 결정하는 역할을 한다. Optimizer는 Gradient Descent(경사하강법)를 기반으로 한다. 기울기(Gradient)는 학습 방향을 결정하고, 학습률은 학습할 정도를 결정한다. 여기까지 내용을 모른다면 "경사하강법과 학습률" 글을 먼저 이해해야 한다. 아래 내용은 Gradient Descent를 기반으로 한 여러 optimizer의 개념들을 설명한다. SGD momentum Adagrad RMSProp Adam [기호 정리] $w$: 가중치, $t$: 시점(step), $\mu$: 학습률, $L$: Loss 값. SG..
딥러닝으로 모델을 학습시키기 위해 미분 값을 구하는 과정이 필요하다. 만약 왜 미분이 필요한지 모른다면 '경사하강법과 학습률'을 참고하면 된다. 해당 내용을 몰라도 이번 글을 이해하는 데는 문제가 없다. 문제점 Chain-rule 연산자와 미분 결과 계산 과정 시각화 역방향으로 계산 문제점 일반적으로 미분값을 구할 때, 도함수를 구한 후 값을 대입해 계산한다. $f(x)=ax^3+bx^2+c \\ \cfrac{d}{dx}f(x)=3ax^2+2bx$ 하지만 문제는 모델의 연산 과정이 너무 복잡하다. $f(x)=Linear(Droupout( ... (maxpool(relu(conv(...))))))$ 위 예시는 아주 기본적인 CNN 모델의 구조이다. 그리고 가장 많이 사용되는 손실 함수인 Cross Entr..
1번에서 전체 개념을 가볍게 설명하고, 2번부터 자세하고 차근차근 설명해 두었습니다. 그러니 첫 부분이 이해되지 않아도 일단은 넘어가서 뒷부분을 읽고 돌아오시면 이해하기 더 편할 겁니다. 전체 개념 딥러닝에서 모델을 학습한다는 것은 실제 값과 예측 값의 오차를 최소화하는 가중치를 찾는 과정이다. 여기서 '오차'를 정의하는 함수를 비용 함수(Cost function)라고 한다. 즉, 비용 함수가 최솟값을 갖는 방향으로 가중치를 업데이트하는 작업이 필요하다. 경사 하강법이라고 불리는 Gradient Descent는 최솟값을 찾을 때 사용할 수 있는 최적화 알고리즘이다. 먼저, 최솟값을 찾을 함수를 설정한 후, 임의의 값으로 초기화하고 해당 값의 기울기를 빼면서 최솟값에 가까워질 때까지 반복하는 방법이다. $..