💻

O(n*logn)의 성능을 나타내는 병합정렬(합병정렬)을 파이썬으로 구현할 것이다. 병합정렬 힙정렬, 퀵정렬만큼 빠른 정렬 알고리즘이다. 병합정렬은 크게 분할과 병합과정으로 나누어진다. 과정 요약 배열의 모든 원소들을 하나씩 분할한 후, 각 원소들끼리 비교하며 다시 병합하는 과정을 거친다. 과정 1. 배열을 하나씩 분해할때 까지 분해한다. 2. 분해한 후 서로 비교하며 오름차순이 되도록 합친다. 3. 비교하고자 하는 배열의 크기가 2 이상일경우에는 두 배열을 합친 크기만큼의 새로운 배열을 만들어준다. 4. 두배열중 가장 작은 수를 새로운 배열의 앞에 넣어준다. 여기서 중요한것은 두 배열은 오름차순으로 정렬이 된 상태 이므로 두배열의 앞만 비교하면 된다. 5-1. 새로운 배열에 넣은 수는 제외하고 다시 비..

Diagonalization :: 대각화 n*n mattix A가 eigenvalues λ₁, λ₂, …, λₙ 을 가지고 있고, 서로 독립된 eigenvector x₁, x₂, …, xₙ 을 가지고 있다고 가정하자. ((λᵢ, xᵢ)는 eigenpair) S = [x₁ x₂ … xₙ], Λ = diag(λ₁, λ₂, …, λₙ)라 하면 S⁻¹AS = Λ 증명. AS = A[x₁ x₂ … xₙ] = [A*x₁ A*x₂ … A*xₙ] = [λ₁*x₁ λ₂*x₂ … λₙ*xₙ] = SΛ Diagonalizale :: 대각가능성 n*n mattix에 대해 n개의 독립적인 eigenvector를 가지고 있어야 함 ↔ diagonalizable n개의 다른 eigenvalue를 갖는다면 n개의 독립된 eigenv..

Eigenvalue & Eigenvectors :: 교유값 & 고유벡터 square matrix A에 대해 Ax = λx에 nonzero vector x가 존재할 때 (invertible 할 때) scalar λ가 eigenvalue, x는 eigenvector라고 불림 (λ, x) eigen pair eigenvalue : 고유값, eigenvector : 고유벡터 계산 eigenvalue λ, eigenvector x를 알고 싶을 때 Ax = λx ↔ (A - λI)x = 0 ↔ (A - λI) singular (x는 nonzerovector이기 때문) ↔ |A - λI| = 0 마지막 방정식을 characteristic polynomial equation(특정다항식)이라고 함→ n*n matrix ..

O(n*logn)의 성능을 나타내는 힙정렬을 파이썬으로 구현할 것이다. 필요한 지식 완전 이진트리 트리 힙 (트리) 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내기 위해 만든 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 힙을 이용하여 우선순위 큐를 구현하면 데이터를 삽입, 삭제하는데 log(n)의 시간이 걸린다. 종류 max heap :: 최대 힙 부모노드가 자식 노드보다 항상 큰 힙 EX. min heap :: 최소 힙 부모노드가 자식 노드보다 항상 작은 힙 EX. 힙정렬 힙 트리 구조를 이용하는 정렬방법으로 병합정렬, 퀵정렬만큼 빠른 정렬 알고리즘이다. 최대 힙을 이용한 방법(상향식, 하향식) 1. 입력해오는 순서대로 혹은 배열의 순서대로 완전이진트리를 만들어준다 2..

Cramer's rule :: 크라머르 법칙 Ax = b의 해를 구하는 방법 Elimination을 통해 구하는 방법 : numerical sol (수치적으로) Cramer’s rule을 통해 구하는 방법 : closed form sol (바로 정답을 구할 수 있음) A의 Determinant를 구할 수 있다면 해를 바로 구할 수 있음 계산 방법 위와 같은 방식으로 나머지 x의 원소에 대해서 반복 x2 = |B2|/|A| x3 = |B3|/|A| Cramer’ Rule을 통한 역함수 구하기 기본적으로 G-J(Gauss-Jorden) Elimination의 발상을 이용 A에 곱해 I가 되도록 하는 matrix의 column을 x, y, z로 쪼갬 Ax = [1 0 0]’ Ay = [0 1 0]‘ Az = ..

sys.stdin.readline() 백준을 풀다 보면 이유 없이 시간초과를 당할 때가 있다. 그럴 때는 input()을 sys.stdin.readline()으로 바꾸면 시간 초과 없이 문제를 해결할 수 있다. input()보다 sys.stdin.readline()이 빠른이유 sys.stdin.readline()에는 input("프롬프트")와 같이 프롬프트를 출력하는 기능이 없다. 버퍼에 입력되는 방식에 차이가 있다. input()은 입력하는 값 하나하나마다 버퍼에 저장한다. \n과 같은 개행 문자를 입력이 종료되는 기준으로 삼으므로 개행 문자를 생략하여 입력받을 수 있다. sys.stdin.readline()은 readline이라는 이름과 같이 개행 문자를 포함한 하나의 줄을 버퍼로 입력받는다. inp..