반응형 데이터 및 Programing/Part1. Basic Knowledge13 유클리드 호제법 (Euclidean algorithm), 유클리드 알고리즘과 최대공약수 & 최소공배수 구하기. 1. 유클리드 호제법과 최대 공약수 구하기. 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나임. 호제법이란 말자체에서 알 수 있듯이 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다 일반적으로 최대공약수를 구하기 위해선 먼저 소인수분해를 해야한다. 두 수를 소인수분해한 후, 공통된 소수를 찾으면 된다. 하지만!! 이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있으며, 이때, 유클리드 호제법을 사용하면 조금 더 효율적으로 최대공약수를 구할 수 있다!!!!!! 방법은 아래와 같다 두개의 자연수 A, B (A>B) 가 있을때 큰수(A)를 작은 수(B) 로 나누면 몫(C)와 나머지(D)를 구할 수 있다. A / B = C, A%B =D 이때 중요한 것은 나머지이다. .. 2023. 5. 23. [기본개념] 고윳값과 고유벡터 (EigenValue, EigenVector, 예제 포함) 1. 정의 임의의 n×n 행렬 A 에 대하여, x ≠ 0 인 해를 갖게 하는 λ 를 행렬 A의 고유값 (Eigenvalue)이라 부른다. 그리고 이에 대응하는 벡터 x를 고유 벡터 (eigen vector) 라고 부한다. 2. 예제를 통한 고유값과 고유 벡터를 찾는 방법 행렬 A를 이용하여 고유값과 고유벡터를 찾는 과정을 설명하겠다. 우선 고유값과 고유 벡터의 정의를 이용하여 아래와 같이 정리 할 수 있다. 이를 다시 풀어 쓰면 2개의 수식으로 정리가 가능하다. 여기서 우변의 항들을 좌변으로 옮겨서 다시 정리하면 안래와 같이 정리가 가능하다. 위의 두 수식을 행렬로 표기하면 형태로 정리가 가능하다. 이 형태는 괄호안에 있는 식으로 부터 얻는 행렬은 역행렬을 가지지 않아야만 아무런 λ와 x=0이라는 ‘tr.. 2023. 3. 5. [기본개념] 고유값 분해 (EigenValue Decomposition, Eigen Decomposition, EVD) 1. 고유값 분해 - 고유값 분해는 고유값과 고유벡터로부터 유도되는 고유값 행렬과 고유벡터 행렬에 의해 행렬을 분해 하는 것을 말함. - Eigen decomposition 혹은 Eigen-Value Decomposition 으로 불리우고 있다. - 고유값 분해는 PCA (Principal component analysis, 주성분 분석), SVD (Singular Value Decomposition, 특이값 분해) 들과 아주 밀접한 관계를 가지고 있다. (공부 해 놓으면 쓸모가 많다는 의미로 보면 된다!) 2. 고유값 분해 표현 선형 독립을 만족하는 정방 행렬 A는 고유값 분해에 의해 다음과 같이 표현이 가능하다. 위의 수식에서 P는 고유 벡터를 열로 가지는 행렬, Δ는 고유값을 대각행렬로 가지는 대각.. 2023. 3. 5. [기본개념] 기댓값과 분산 그리고 공분산 1. 기댓값 (Expectation Value) - 어떤 확률 과정을 무한히 반복했을 때, 얻을 수 있는 값의 평균으로서 기대할 수 있는 값을 의미함. - 사건이 발생해서 얻는 값과 그 사건이 일어날 확률의 곱을 모든 사건에 대해 합한 값. - 엄밀히 보면 가중 평균이라고 볼수 있음. - 기대값은 성형성을 가지며, 이 성됩된다. (X,Y는 확률 변수이며, a는 상수) 2. 분산 (variance) - 확률변수가 기댓값으로부터 얼마나 떨어진 곳에 분포하는지를 가늠하는 수 - 기댓값은 확률 변수의 위치를 나타내고 분산은 그것이 얼마나 퍼져 있는지를 나타냄. - 관측 값에서 평균을 뺀 값을 제곱하고, 그것을 모두 더한 후 전체 개수로 나누어줌. (즉 편차 제곱의 평균값임, 관측값에 평균을 뺀값을 그냥 더해주면.. 2023. 3. 1. 이전 1 2 3 4 다음 반응형
