파고파고

정렬문제란 input: n개로 이루어진 일련의 숫자 output: a1 ≤ a2 ≤ a3 ≤ ... ≤ an으로 정렬(reordered)된 순열(permutation) 이때, a1, a2 등을 item 또는 key라고 한다. Insertion Sort (삽입정렬) 삽입정렬이란? insertion을 사용한 정렬 알고리즘을 말한다. 그렇다면 삽입(Insertion)이란 무엇을 의미하는가? A[1...n]이라는 배열(array)가 있다고 치자. 삽입은 key A[2]를 array A[1]에 넣는것 key A[3]를 array A[1..2]에 넣는것 key A[4]를 array A[1..3]에 넣는것 ... key A[n]를 array A[1...n-1]에 넣는것 을 의미한다. 삽입정렬은 이러한 삽입과정의 반복..

알고리즘이란 문제(problem)를 해결하는 일련의 과정(procedure)이다. 어떤 알고리즘이 더 나은가를 판단하는 기준들 알고리즘의 성능(Performance) 1. Running Time Division, Addition, Multiplication 등이 해당된다. 2. Space Consumption 변수의 개수 (Number of variables), 배열의 크기(Size of an array) 등이 해당된다. 문제(Problem)와 그 Instance Problem 1부터 n까지 정수의 합인 S를 구하는 것 Problem Instance 1에서 100까지 정수의 합을 구하는 것 즉, Problem Instance is a set of Problem. 이다.

여기서는 행렬 중에서 2X2 역행렬을 구하는 방법과 관련해 조금 더 자세히 써볼 것이다. *역행렬 행렬에 곱했을 때 단위행렬이 나오는 행렬을 그 행렬의 역행렬이라고 한다. $$A·A_{-1} = A_{-1}·A = I$$ 역행렬은 존재할 수도, 아닐 수도 있다. 행렬과 그 역행렬은 정사각행렬(square matrix)이어야 한다. 2X2 행렬의 역행렬 구하기 행과 열의 개수가 2개인 행렬의 역행렬을 구하는 방법은 다음과 같다. $$ \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} x & y \\ z & w \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} $$ a, b,..

행렬의 표기 $$M = \begin{bmatrix} x_{1} & x_{2} & x_{3} \\ x_{4} & x_{5} & x_{6} \\ x_{7} & x_{8} & x_{9} \\ \end{bmatrix} $$ 행렬은 Upper Bold Case 로 표기한다. 콤마 (,) 없이, 각 요소를 [ ] 안에 표기한다. m X n 행렬은, 행의 개수가 m개 이고, 열의 개수가 n개 인 행렬이다. 행렬의 종류, 용어 행렬의 요소 $$c_{ij}$$ C 행렬의 i 번째 행의 j 번째 열에 위치한 요소를 의미한다. 정사각행렬 (square matrix) 열과 행의 수가 같은 행렬을 정사각행렬이라고 한다. (m = n) $$A = \begin{bmatrix} -1 & 2 \\ 4 & 1/2 \\ \end{bmat..

벡터의 의미 일반적인 의미 벡터는 크기와 방향을 갖는다. 크기(magnitude) + 방향(orientation, direction) *scalar(상수)는 magnitude만 있다. 선형대수에서의 의미 여러 개의 스칼라를 나열해 놓은 것으로 받아들일 수 있다. $$vector x = [x1, x2, x3,,,, xn]$$ $$(x ∈ R^n)$$ x1, x2, x3 등을 벡터의 element 또는 component라 하며, n개의 element로 이루어진 위와 같은 벡터를 통상적으로 실수집합으로 이루어진 n - dimensional(차원) vector 라고 부른다. 벡터의 표기 일반적으로 벡터는 아래와 같이 Column Vector Notation으로 표기한다. *Row Vector Notation은 ..

Linearity (선형성) 선형성의 조건 f(x), x1, x2 등이 다음의 조건을 만족할 때, 선형성을 지닌다고 말한다. 1. Superposition (중첩) $$f(x1 + x2) = f(x1) + f(x2)$$ 2. Homogeniety $$f(ax) = af(x)$$ Superposition과 Homogeniety를 모두 만족할 때, 선형성(Linearity)을 지닌다고 말한다. $$f(ax1+bx2) = af(x1)+bf(x2)$$ 선형성의 예시 선형성(Linearity)은 함수 뿐 아니라 연산방법, 나아가 시스템에도 적용하여 말할 수 있다. 1. 원점을 지나는 직선 $$f(x) = mx$$ f(x) = mx+n와 같은 함수는 선형성을 지닌다고 하지 않는다. 2. 미분과 적분 (Differe..