programming

1 백트래킹 백트래킹이란 조건을 가진 문제를 풀기 위한 전략이다. DFS와 재귀로 구현되며, 정답이 될 수 있는 후보의 탐색을 하면서 조건에 맞는다면 계속 탐색하고 맞지 않다면 그 후보를 배제하고 다음 후보의 탐색을 한다. 이러한 과정을 가지치기라고 하고 가지치기를 얼마나 잘 짜냐에 따라 백트래킹의 성능이 좌우된다. 2 예시 문제 링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제를 예시로 들겠다. 1부터 N까지의 자연수 중에서 ..

1 정규화(Normalization) 정규화란 위키피디아에서 무언가를 더 정상적이거나 규칙적으로 만드는 프로세스를 의미합니다라고 한다. 여러가지 방법들이 있는데 min-max scaling이나 표준화같은 것이 있다. 또 머신러닝쪽으로 가면 L2 정규화 같은 것도 있다. 2 표준화(Stadardization) 표준화는 표준정규분포를 따르도록 분포를 바꾸는 것이다. 표준정규 분포는 평균이 0이고, 표준편차가 0이므로 본래 분포의 각 값에서 평균을 빼고 표준편차로 나누면 표준화가 된다. $$\frac{x-\mu}{\sigma}$$ $\mu$는 평균, $\sigma$는 표준편차 3 min-max scaling min-max 스케일링은 값을 분포의 최솟값으로 빼고, 분포의 최댓값과 최솟값의 차로 나눈다. 이러하여..

1 공분산 공분산은 두 변수가 선형적인 관계를 가지는가에 대한 지표이다. $$COV(X, Y) = E[(X-E[X])(Y-E[Y])]$$ E는 평균을 뜻하고 COV는 공분산을 뜻한다. 식을 보면 알겠지만 분산이랑 비슷한 식인 것을 알 수 있다. 공분산은 COV의 절댓값이 크면 클수록 선형적인 관계를 가지고, 0에 가까울수록 어떤 선형적인 관계도 가지지 않는다. 또한 공분산이 0보다 크다면 우상향하는 그래프이고 0보다 작다면 우하향하는 그래프가 나온다. 2 상관계수 상관계수는 공분산을 정규화한 것이다. 그래서 공분산과 똑같은 특징을 가지는데 상관계수의 절댓값이 1보다 커지지 않으므로 1에 가까울수록 선형적인 관계를 가지고, 0에 가까울수록 선형적인 관계를 가지지 않는다라고 말할 수 있겠다. 그리고 보통 0..

유사도를 먼저 보고 오면 좋다. 1 TF TF는 특정 문서(d)에서의 단어(t)의 빈도이다. 한 문서에서 단어의 중요도를 나타낸다고 보면 된다. $$TF(d, t) = d에서의 t의 갯수$$ 2 IDF IDF는 총 문서의 수를 특정 단어(t)가 등장한 문서의 수(n)로 나눈 값이다. 실제로 사용할 때는 총 문서의 수가 많기 때문에 분모에 1을 더하고 식 전체에 log를 사용하여 값의 크기를 줄인다. 분모에 1을 더하는 이유는 분모가 0이 되는 경우를 방지하기 위해서이다. 그리고 보통 log의 밑으로는 e를 사용한다. IDF는 너무 많이 등장하는 단어의 중요도를 낮추기 위해서 사용된다. $$IDF(n, t) = \frac{n}{t가 등장한 문서의 수}$$ $$IDF(n, t) = \log\frac{n}{1..

1 연쇄 법칙 연쇄 법칙은 합성 함수의 도함수에 관한 것이다. 미분가능한 함수 $f$와 $g$가 있을 때 $f(g(x))$의 도함수는 아래와 같다. $$f^{\prime}(g(x))g^{\prime}(x)$$ 이 것을 $u=g(x)$라고 하고 라이프니츠 표기법으로 쓸 수도 있다. $$\frac{dy}{dx} = \frac{dy}{du} \cdot \frac{du}{dx}$$ n개의 함수가 합성이 되어져 있는 경우에도 함성함수가 구해지는데 라이프니츠 표기법으로 나타내면 아래와 같이 나온다. 왜 연쇄법칙인지 알 수 있는 결과이다. $$\frac{df_1}{dx} = \frac{df_1}{df_2} \frac{df_2}{df_3} ... \frac{df_{n-1}}{df_n} $$ 2 예제 연쇄 법칙이 쓰이는..

1 퀵정렬 퀵정렬은 피벗(pivot)을 지정해두고, 피벗의 왼쪽에는 피벗보다 작은 값, 피벗의 오른쪽에는 피벗보다 큰 값을 두도록 각 값들을 비교하고 바꾸어준다. 바꾼 후에는 피벗보다 작은 왼쪽 배열과 피벗보다 큰 오른쪽 배열로 나누어서 그 둘을 각각 다시 앞의 과정을 반복해준다. 이 과정은 재귀함수로 구현되어있다. 퀵정렬은 피벗을 어떻게 지정하냐에 따라 성능이 달라진다. 보통은 그냥 배열의 중앙에 있는 값을 정하기도 한다. 2 시간복잡도 시간복잡도는 평균적으로 $O(n \log n)$이다. 다만 최악의 경우에는 $O(n^2)$이 나오기도 한다. 두 경우를 살펴보면서 알아보겠다. 먼저 평균적인 경우인데 피벗으로 중앙값에 가까운 값이 뽑힌다고 생각하면 배열이 본래 크기의 2분의 1로 잘릴 것이다. 그러면 ..

1 코사인 유사도 코사인 유사도는 두 벡터가 얼마나 비슷하냐를 알기 위해 사용된다. 벡터 a, b가 있을 때 a와 b의 내적을 a의 놈과 b의 놈을 곱한 값으로 나누어 계산한다. 기존의 내적을 구할 때 쓰는 공식에서 a의 놈과 b의 놈을 우측으로 옮긴 것이다. $$a \cdot b = \parallel a \parallel \parallel b \parallel \cos(\theta)$$ $$ \cos(\theta) = \frac{a \cdot b}{ \parallel a \parallel \parallel b \parallel}$$ 내적과 놈(Norm) $$a \cdot b = \sum_{k=1}^N a_k \cdot b_k $$ $$\parallel a \parallel = \sqrt{\sum_{k=..

오늘은 정렬 알고리즘에 대해 알아볼 것이다. 대표적인 알고리즘으로는 가장 쉬운 버블정렬, 많이 쓰는 병합정렬, 퀵정렬, 그 외에 삽입정렬, 힙정렬, 기수정렬 등 더 많이 있다. 오늘은 퀵정렬에 대해 알아보겠다. 1 병합정렬 병합정렬의 아이디어는 먼저 기존 배열을 크기가 1인 배열로 분해시킨 다음에 각각의 배열들을 정렬시킨다. 그 다음에 정렬된 배열들을 2개씩 합쳐서 합쳐진 배열들을 정렬시킨다. 이 것을 반복하여서 크기가 원래 배열 크기로 돌아올 때까지 반복한다. 2 시간복잡도 시간복잡도는 $O(n \cdot \log n)$이다. 왜 그렇나면 배열을 나눌 때 $log n$만큼 걸리고 합칠 때 또한 $log n$만큼 걸리고 각각의 배열을 정렬할 때 $n$번 걸린다. 이렇게 하여서 $\log n + n \cd..

다른 알고리즘들을 설명하기 전에 시간복잡도에 대해 한 번 설명을 하겠다. 전에 설명해 놓은 자료구조에 대한 시간복잡도도 생각해 보면 좋겠다. 1 빅-오 표기법 시간복잡도를 말할 때 보통 점근 표기법을 사용하는데 그 중에서도 빅-오 표기법을 가장 많이 사용한다. 빅-오 표기법이란 최악의 경우에 시간이 얼마나 걸리는가에 대해 알기 위해 사용한다. 보통 O(n) 이런 식으로 표기를 한다. 2 표기 방법 빅-오 표기법은 계수와 낮은 차수의 항들을 모두 제외하고 표기하는 방법이다. 예를 들어 $n^3+3n^2+1$이 있다고 하자. 이럴 때 가장 큰 항만 남기고 큰 항의 계수도 없애면 시간복잡도가 $O(n^3)$이 나온다. 또 하나 예를 들자면 $2^n+n$이 있으면 그때의 시간복잡도는 $O(2^n)$이 된다. 그..

비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 어느 한 상자에는 2개 이상의 물건이 들어있다는 원리를 말한다. 디리클레의 서랍 원리라고도 한다. 뭐 하다가 이런 것을 증명했는지 참 궁금해진다. 증명 증명은 귀류법으로 간단히 가능한데, n개의 상자에 n+1마리의 비둘기를 넣을건데 비둘기가 한 마리 이하로 들어가 있다고 가정하자. 그러면 n개의 상자에는 최대 n 마리의 비둘기가 들어갈 수 있으므로 모순이다. 그러니 이 원리는 참이다. 예시 이 원리가 통하는 상황을 생각해보면 저번에 다룬 해시테이블이 있다. 이 원리 때문에 연결리스트나 아예 배열의 크기를 확장할 필요가 생겼다. 또 생각해 보자면 아무 자리 자연수 11개 이상이 있다면 무조건 1의 자리 숫자가 한 개는 겹칠 것이다. 뭐 또 유명한 예..