파고파고

Heap이란? almost complete binary tree (완전이진트리)를 기초로 하는 자료구조이다. *complete binary tree (1) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 (자식이 모두 2개(binary)) (2) 마지막 레벨의 노드들은 가능한 한 왼쪽부터 채워져 있는 자료구조 *완전이진트리의 예시. heap에도 해당하는 것을 확인하자. 여기서 heap은 각 노드에 들어있는 값의 대소에 일정한 규칙이 있는 자료구조다. 그 규칙의 종류에 따라 heap은 2가지로 나뉜다. Max-Heap Property - 부모노드(parent node) 가 자식노드 (child node)보다 크거나 같다. - root node, 즉 트리의 가장 상단에 있는 node가 가장 큰 el..

역행렬(Inverse Matirx)과 연립일차방정식의 해의 관계 행렬 A의 역행렬이 존재한다면, 즉 다음이 성립한다면, $$AA^{-1} = A^{-1}A = I$$ $$A^{-1}Ax = A^{-1}b$$ $$x = A^{-1}b$$ 가능한 x의 집합은 하나뿐이다. 즉, 해가 하나만 존재한다.(non-singular, unique answer, invertible) 정리하면 아래와 같이 표현할 수 있다. Square System의 해를 구할 때, A의 역행렬이 존재한다면 그 해는 유일(unique)하다. 이때, A는 Invertible하다고 표현한다. 가우스 조던 소거법 (Gauss-Jordan Method) 가우스 조던 소거법은 A의 역행렬을 구할 수 있는 방법이다. 원리는 A를 단위행렬(I)로 만드..

가우스 소거법 - Gaussian Elimination 가우스소거법은 연립방정식의 해를 구하는 방법 중 하나다. 각 행의 pivot을 사용해 Upper Triangular Matirx를 만드는 과정이라고 생각하면 된다. 예시를 따라가며 가우스소거법의 연산방법을 익혀보자. 아래 연립일차방정식의 해 u, v, w를 구하는 것이 목적이다. $$\begin{cases} 2u+v+w = 5\\ 4u-6v = -2 \\ -2u+7v+2w = 9 \end{cases}$$ 이를 행렬로 표현하면 다음과 같다. $$\left[ \begin{matrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \\ \end{matrix} \right] \left[ \begin{matrix} u \\ v \\ w \\ \end{mat..

선형결합 - Linear Combination 선형결합이란 다음과 같은 벡터들의 결합을 의미한다. $$a_{1}x_{1}\;+\;a_{2}x_{2}\;+\;a_{3}x_{3}\;+.... = y$$ 여기서 x는 벡터를, a는 각각의 벡터에 곱해진 계수(coefficient)를 의미한다. 예를 들어보면 좀 더 이해가 잘 된다. 예 1) $$x\left[\begin{matrix}1\\0\\0\\ \end{matrix} \right] + y\left[\begin{matrix}0\\1\\0\\ \end{matrix} \right] + z\left[\begin{matrix}0\\0\\1\\ \end{matrix} \right] = \left[\begin{matrix}x\\y\\z\\ \end{matrix} \ri..

Power Series power series란 다음과 같은 형태다. $$\sum_{n=0}^{\infty}c_{n}x^{n} = c_{0}+c_{1}x+c_{2}x^{2}+c_{3}x^{3}+....$$ 이를 좀 더 보편적인 형식으로 표기하면, power series란 아래와 같은 급수를 의미한다. $$\sum_{n=0}^{\infty}c_{n}(x-a)^{n} = c_{0}+c_{1}(x-a)+c_{2}(x-a)^{2}+c_{3}(x-a)^{3}+....$$ 이러한 형태의 급수를 power series in (x - a) power series centered at a power series about a 라고 부른다. Convergence of Power Series 멱급수는 x의 범위에 따라 수렴..

무한급수 급수(series)는 수열의 합이다. 무한급수는 수열을 n=1부터 무한대까지 더한 값이다. $$\sum_{n=1}^{\infty}a_{n}$$ 급수의 수렴판정법들 급수의 수렴과 발산을 test 하기위한 method들에는 여러가지가 있다. Test for Divergence 다음 조건을 만족시키지 못하면 수열 an의 급수는 발산(divergent)한다. $$\lim_{n\to\infty}a_{n} = 0$$ 단, 조건을 만족시킨다고 해서 무조건 급수가 수렴하는 것은 아니다. Integral Test 함수 f가 [1,∞)에서 continuous(1), positive(2), decreasing(3) function일 때 $$\sum_{n=1}^{\infty}a_{n}$$ 위 급수가 수렴(conver..

수열(sequence) 수열의 극한의 엄밀한 정의 - Precise Definition of a Limit of a Sequence 임의의 ε>0 (아주 작은 양수)에 대해서 적당한 자연수 N에 대해, Nn0에서 다음의 조건을 만족할 때, $$a_{n}≤b_{n}≤c_{n}\;\;and\;\; \lim_{n\to\infty}a_{n} = \lim_{n\to\infty}c_{n} = L$$ 다음이 성립한다. $$\lim_{n\to\infty}b_{n} = L$$ 수열의 극한과 관련한 공통적인 이론들 이론1 $$\lim_{n\to\infty}|a_{n}| = 0 \; 이면 \; \lim_{n\to\infty}a_{n} = 0$$ 이론2 함수 f가 L에서 연속이고, 다음 조건을 만족할 때, $$\lim_{n\..

알고리즘에서 자기 자신을 재귀적으로 호출할 때, 그 시간복잡도를 재귀로 표현할 수 있다. 재귀식이란, 함수에 더 작은 입력값을 대입했을 때의 등식이나 부등식을 표현한 것을 말한다. (이렇게 말하면 이해가 안되니까 가령,) $$\begin{cases} \theta(1) \; if\, n=1\\ 2T(n/2)+\theta(n) \; if\, n>1\\ \end{cases}$$ 재귀를 이용해 알고리즘에 대한 알맞은 점근표기법을 찾아낼 수 있다. 점근표기법을 찾는 과정에서 재귀를 푸는 방법으로는 3가지가 있다. 1) Substitution method 2) Recursion-tree method 3) Master method (다루지 않을 것) 1. Substitution Method 지난 포스팅에서 점근표기법..

알고리즘의 시간복잡도는 여러 표기법으로 표현될 수 있다. 대표적인 표기법은 3가지이다. 1. $$\theta( )$$ 보통 함수의 최고차항에서 계수를 뗀 차수를 괄호 안에 넣어 표기한다. 예를 들면 다음과 같다. $$3n^2+2n-1 = \theta(n^2)$$ $$3n-1 = \theta(n)$$ $$3n-1 ≠ \theta(n^2)$$ 2. $$O( )$$ 함수의 최고차항(계수를 뗀)과 같거나 높은 차수를 괄호 안에 넣어 표기한다. 다음과 같은 예로 이해할 수 있다. $$3n^2+2n-1 = O(n^2)$$ $$3n-1 = O(n)$$ $$3n^2-1 ≠ O(n)$$ 3. $$\Omega( )$$ 함수의 최고차항(계수를 땐)과 같거나 낮은 차수를 괄호 안에 넣어 표기한다. 다음과 같은 예로 이해할 수..

병합정렬(Merge Sort)이란? 병합(merge)을 이용한 정렬 알고리즘이다. 그렇다면 병합은 무엇을 의미하는가? 두 개의 sorted list에서 각각의 키(list A의 key, list B의 key)의 대소를 비교하면서 새로운 병합된(merged) sorted list를 생성하는 것을 의미한다. 예를들어, 를 병합한다고 치자. 위처럼 작은 key를 우선으로 하여 새로운 list 맨 뒤에 추가해주는 과정을 병합이라고 한다. 병합(Merge)과정을 pseudo code로 나타내면 다음과 같다. Merge(A, p, q, r) n1 = q - p + 1 //n1은 array L의 크기 n2 = r - q //n2는 array R의 크기 L[1... n1 + 1]과 R[1... n2+1]을 새로운 배열..