Adore__

Source : [BoostCourse '인공지능을 위한 선형대수' - 주재걸 교수님] 방정식의 개수(열벡터)가 변수보다 클 때, 보통 '해가 없다'라고 말한다. 방정식의 개수가 많아지면 하나의 열벡터는 엄청 광활한 dimension 안에 있다는 것이다. 여기서 해가 존재한다는 것은 이보다 적은 벡터의 span 공간 안에 b벡터가 들어가야한다는 것인데, 광활한 (예를 들어 100 dimension) 전체 공간에서 아주 작은 3개 벡터의 span 공간 안에 b 벡터가 딱 들어갈 확률은 그으윽히 작다. 이러한 경우 해는 어떻게 구해야할까? 단순히 해가 없네~라고 끝낼 수 없다. 근사적으로라도 해를 구해보자! 라는 게 Least Squares가 등장한 배경이다. 먼저 기본적인 내용을 살펴보자 Basis ▪️I..

Source: Steve Brunton (Youtube) https://www.youtube.com/watch?v=gXbThCXjZFM&list=RDCMUCm5mt-A4w61lknZ9lCsZtBw&index=5 Singular Value Decomposition = 특이값 분해 - Data Reduction : 고차원 input data를 저차원으로 줄여주는 차원 축소 기법이다 - Data-driven generalization of Fourier transform : 푸리에 변환의 일반화 기법 * 푸리에 변환이란? -> https://www.youtube.com/watch?v=Mc9PHZ3H36M - Facial Recognition, recommendation, 등에 사용됨 - 상업적 이용에 아주 중..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' ▪️트리의 특징 트리는 그래프의 형태 중 하나로, 다음과 같은 특징이 있다. 순환구조(cycle) 이 없고, 1개의 root node 가 존재한다 root node를 제외한 노드는 단 1개의 부모 노드를 갖는다. subtree 또한 트리의 모든 특징을 따른다. 연결된 트리에서 임의의 두 노드를 이어주는 경로는 유일하다 그래프 트리 방향성 방향, 무방향 방향만 존재 사이클 순환, 비순환, 자기순환 비순환만 허용 루트 노드 루트 개념이 없다. 한개의 루트만 존재 부모-자식 관계 이런 개념이 없다 1개의 부모노드에여러개의 자식 노드 가능 단, 각 자식 노드는 하나의 부모노드만 가짐 모델 네트워크 모델 계층모델 간선 수 제한..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 최소 신장 트리란, 그래프의 모든 노드를 한번씩 방문할 때, 거쳐가는 edge들의 가중치의 합이 최소가 되도록 하는 트리이다. ▪️특징 - 트리이므로 사이클을 포함하지 않는다. (만약 모든 노드를 연결해서 순환되는 구조가 만들어지면, 최소의 가중치가 될 수 없다. 하나의 엣지를 제거하더라도 모든 노드를 거치는 경로를 만들 수 있기때문이다.) - N개의 node가 있으면, MST를 구성하는 edge의 수는 N-1개이다. - 구현하는 방법은 크루스칼 / 프림 알고리즘이 있다. * 크루스칼 알고리즘 * 프림 알고리즘 크루스칼은 처음부터 모든 간선의 가중치를 오름차순으로 정렬한 후에 작은 가중치의 간선부터 연결하지만, 프림 ..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' Union-Find는 말 그대로 두개의 연산으로 구성되어 있는 알고리즘이다. ▪️수학적 연산 기법 ▷ Union 연산: 각 node가 속한 집합을 1개로 합치는 연산. node a, b가 각각 집합 A,B에 속할 때, union(a,b)는 A U B를 말한다. 우리가 집합연산에서 배웠던 합집합과 같다. ▷ Find 연산: 특정 노드 a가 속한 집합의 대표 node를 반환해준다. 노드 a가 A집합에 속할 때, find(a) 는 A집합의 대표 노드(루트 노드)를 반환한다. ▪️그림으로 과정 이해하기 union-find는 집합을 표현하는 배열, 리스트, 트리로 표현할 수 있지만, 우선 빠른 이해를 위해 1차원 배열로 살펴보..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 최단 거리를 구하는 알고리즘으로, 특정 노드에서 다른 노드까지 최단 거리는 몇인가?라는 문제에서 사용한다. 딴, edge의 가중치가 양수여야 한다. 기능 특징 시간 복잡도(node:V, edge:E) 출발 노드에서 모든 노드간의 최단 거리 탐색 Egde의 가중치는 모두 양수여야 한다. O(E*logV) ▪️과정 1. 인접 리스트로 그래프 구현 인접 행렬도 가능하지만, 시간복잡도를 고려할 때 N의 크기가 커지는 것을 방지하기 위해 인접 리스트를 선택하자. 2. 최단 거리 배열 초기화 최단거리를 저장해주는 배열을 노드 개수만큼 만든다. 에서 출발하므로 노드1까지의 최단거리는 0, 그리고 나머지 노드들의 최단거리는 무한대(..