끈기 있는 개발 공간

브루트 포스브루트 포스는 모든 경우의 수를 다 해보는 것이다.예를 들어, 4자리 수의 비밀번호를 잊어버렸을 때 비밀번호를 찾는 방법은0000, 0001, 0002, ... , 9999와 같이 0000부터 9999까지 다 해보는 것이다.비밀번호를 찾기 위한 가장 확실한 방법이다.비밀번호 하나를 입력하는 데 1초가 걸린다고 하자.이 방법으로 4자리 수의 비밀번호를 찾기 위해 최대 2.7시간(=10000초)이 소요된다.하지만, 4자리 수가 아니라 12자리 수의 비밀번호를 찾기 위해서는 최대 31688년(=1,000,000,000,000초)이 소요된다.이는 겨우 비밀번호 하나 찾는 데 기다리기에는 터무니없이 긴 시간이다.그러므로 브루트 포스를 이용하여 문제를 풀 때에는반드시 시간 복잡도가 해당 문제의 시간 제한..

트리의 지름트리에 존재하는 경로 중에서 가장 긴 것의 길이를 트리의 지름이라고 한다.트리의 지름은 탐색 2번으로 구할 수 있다.한 정점 $s$에서 모든 정점까지의 거리를 구한다. 이 때, 가장 먼 거리의 정점을 $u$라고 한다.$u$에서 모든 정점까지의 거리를 구한다. 이 때, 가장 먼 거리의 정점을 $v$라고 한다.$d(u,v)$를 $u$와 $v$사이의 거리라고 할 때, $d(u, v)$가 트리의 지름이다.증명$d(u,v)$를 트리의 지름이라고 하자.한 정점 $s$에서 가장 거리가 먼 정점을 $x$라고 하고 $x$에서 가장 거리가 먼 정점을 $y$라고 하자.$wlog$(일반성을 잃지 않고) $d(s,u)\geq{d(s,v)}$이다. 이 때, 반드시 $d(s,x)\geq{d(s,y)}$는 반드시 성립해야..

다이나믹 프로그래밍다이나믹 프로그래밍(Dynamic Programming)이란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.Dynamic Programming라는 용어를 1940년에 처음 사용한 Richard Bellman은 아무 의미 없이 멋있어 보여서 사용했다고 한다. 하지만, 이를 직역하여 동적 계획법이라고도 불린다.다이나믹 프로그래밍으로 문제를 해결하려면 두 가지 속성을 만족해야 한다.Overlapping SubproblemOptimal SubstructureOverlapping SubproblemOverlapping Subproblem을 직역하면 '겹치는 부분문제'이다.피보나치 수를 예로 들어 이를 알아보겠다.$F_0=0$$F_1=1$$F_n=F_{n-1}+F_{n-2}(n\geq{2})$위..

소수소수는 약수가 1과 자기 자신 밖에 없는 수이다.소수와 관련된 알고리즘은 두 가지가 있다.어떤 수 $N$이 소수인지 아닌지 판별하는 방법$N$보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법$N$이 소수가 되려면 2보다 크거나 같고, $N-1$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.$N-2$번 연산하므로 $O(N)$의 시간 복잡도를 가진다.소수 판별 구현 - $O(N)$bool prime(int n) { if(n $N$이 소수가 되려면 2보다 크거나 같고, $\frac{N}{2}$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.$N=a\times{b}$로 나타낼 수 있는데, $a$가 작을수록 $b$는 크다. 가능한 $a$ 중에서 가장 작은 값은 2이기 때문에, $b$는 $\..

최대공약수최대공약수(Greatest Common Divisor)는 줄여서 GCD라고 쓴다.두 수 $A$와 $B$의 최대공약수 $G$는 $A$와 $B$의 공통된 약수 중에서 가장 큰 정수이다.최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 것이다.기본 구현int g = 1;for(int i = 2; i 앞의 방법보다 빠른 방법은 유클리드 호제법(Euclidean algorithm)이다.유클리드 호제법은 $a$를 $b$로 나눈 나머지를 $r$이라고 했을 때 $GCD(a, b) = GCD(b, r)$이고, $r$이 0이면 그 때 $b$가 최대공약수임을 이용하는 것이다.예를 들어, $GCD(24, 16) = G..

나머지 연산컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 $M$으로 나눈 나머지를 출력하라는 문제가 등장한다.Overflow 문제와 덧셈$(A+B)\mod{B}$하지만, 위 식에서 만약 $A+B$의 연산 결과가 자료형의 범위를 넘어서게 되면 overflow가 발생한다.이 때, $A$와 $B$ 각각에 나머지 연산을 적용하여 overflow를 막을 수 있다.$(A+B)\mod{M}=((A\mod{M})+(B\mod{M}))\mod{M}$곱셈곱셈은 덧셈의 연속이기 때문에 곱셈에서는 다음의 식이 성립한다.$(A\times{B})\mod{M}=((A\mod{M})\times{(B\mod{M})})\mod{M}$나눗셈나눗셈에서는 성립하지 않고 모듈러 역수(Modular Inverse)를 구하여..

오늘날 대부분의 머신러닝 애플리케이션이 지도 학습 기반이지만, 사용할 수 있는 데이터는 대부분 레이블이 없습니다. 즉, 입력 특성 $X$는 있지만 레이블 $y$는 없습니다.8장에서는 가장 널리 사용되는 비지도 학습 방법인 차원 축소를 살펴봤습니다. 이 장에서는 몇 가지 비지도 학습과 알고리즘을 추가로 알아봅니다.군집등산하면서 이전에 본 적 없는 꽃을 발견했다고 가정해봅시다. 주위를 둘러보니 꽃이 몇 개 더 있고, 이들이 비슷해 보여 같은 종에 속한다는 걸 알았습니다. 어떤 종인지 알 수는 없지만 비슷해 보이는 꽃을 모으는 건 할 수 있습니다. 이를 군집이라고 합니다. 비슷한 샘플을 구별해 하나의 클러스터 또는 비슷한 샘플의 그룹으로 할당하는 작업입니다.위의 그림을 보시면 왼쪽 붓꽃 데이터셋은 각 샘플의 ..

머신러닝 문제에서 많은 경우 훈련 샘플 각각은 수백만 개의 특성을 가지고 있습니다. 이런 많은 특성은 훈련을 느리게 할 뿐만 아니라, 좋은 솔루션을 찾기 어렵게 만듭니다. 차원 축소를 이용하면 특성 수를 크게 줄여서 불가능한 문제를 가능한 범위로 변경할 수 있는 경우가 많습니다.3장에서 다루었던 MNIST 이미지를 생각해봅시다.이미지 경계에 있는 픽셀은 거의 항상 흰색(혹은 흰색에 가까운 색)이므로 중요한 정보가 아닙니다. 따라서, 이러한 픽셀을 제거한다고 해도 많은 정보를 잃지 않습니다. 또한 이미지 분류에서 인접한 두 픽셀은 종종 많이 연관되어 있으므로, 두 픽셀을 하나의 픽셀로 합치더라도 많은 정보를 잃지 않습니다. 여기서,이미지 경계에 있는 흰색 픽셀 제거인접한 두 픽셀 병합이 두 작업이 차원 축..