컴퓨터 공학/Software Math90 [선형대수학] 백터의 크기, 노름(norm) 구하는 법 평면이나 공간에서 벡터를 화살표로 나타낼 때 화살표의 길이가 그 벡터의 크기이다. 벡터 v의 크기를 노름(norm)이라 하고, || v ||로 나타낸다. 예제 다음 벡터의 노름을 구하라. 2023. 10. 24. [선형대수학] 내적을 이용하여 두 벡터의 사잇각 구하기 0이 아닌 두 벡터가 주어졌을 때, 두 벡터 사이의 코사인 값을 다음과 같이 구할 수 있다. 예제 다음에 주어진 두 벡터 사이의 코사인 값을 구하라. a = (-3, 4), b = (4, 3) 2023. 10. 23. [선형대수학] 수반행렬(adjoint matrix)란? 2023. 10. 20. [선형대수학] 대칭행렬 (symmetric matrix) / 반대칭행렬 (skew-symmetric matrix)이란? 대칭행렬 (symmetric matrix)은 주대각선 성분을 기준으로 대칭인 위치에 있는 성분이 서로 같음을 의미한다. 반대칭행렬(skew-symmetric matrix)은 주대각선 성분이 모두 0이고, 주대각선 성분을 기준으로 대칭이 위치에 있는 성분의 부호가 서로 반대임을 의미한다. 정사각행렬은 대칭행렬과 반대칭행렬의 합으로 나타낼 수 있다. 2023. 10. 20. [선형대수학] 전치행렬 (transpose matrix)이란? 전치행렬 (transpose matrix)은 행렬 A의 행과 열을 바꾸어 만든 행렬이다. A^{T}로 표기한다. 전치행렬의 성질 (1) (A^{T})^{T} = A (2) (A+B)^{T} = A^{T}+B^{T} (3) (AB)^{T} = B^{T}A^{T} (4) (kA)^{T} = kA^{T} 2023. 10. 20. [선형대수학] 영행렬 (zero matrix)이란? 성분이 모두 0인 행렬을 영행렬 (zero matrix)이라 하고, O로 나타낸다. 다음은 모두 영행렬이다. \begin{bmatrix}0 & 0 \\0 & 0 \\0 & 0 \end{bmatrix} \begin{bmatrix}0 & 0 & 0\\0 & 0& 0 \end{bmatrix} \begin{bmatrix}0 \\ 0 \\ 0 \\ 0 \end{bmatrix} 임의의 행렬 A에 대하여 O가 A와 크기가 같은 영행렬이면 다음이 성립한다. (1) A + O = O + A = A (2) A - A = O (3) O - A = -A (4) AO = OA = O 2023. 10. 20. [선형대수학] 역행렬 (inverse matrix) 구하는 법(공식, 기본 행 연산) 2X2행렬인 경우 아래 하늘색 박스가 역행렬 구하는 공식입니다. 대각행렬은 대각원소만 역수로 취하여 쉽게 역행렬을 구할 수 있습니다. (아래 이미지에서 행렬 B에 해당) 기본 행 연산으로 역행렬 구하기 다음 기본 행 연산 3가지 방법을 적절하게 사용하여 역행렬을 구할 수 있다. 행렬 크기에 맞는 단위 행렬과 함께 연산을 한다. 왼쪽에 단위 행렬이 될 때까지 기본 행 연산을 진행한다. 2023. 10. 20. [선형대수학] 역행렬 (inverse matrix)의 성질 n차 정사각행렬 A, B가 가역이고 k가 0이 아닌 스칼라일 때, 다음이 성립한다. 2023. 10. 20. [선형대수학] 가역행렬(invertible matrix) / 비가역행렬(noninvertible matrix) / 역행렬 (inverse matrix)란? n차 정사각행렬 A에 대해 다음을 만족하는 행렬 B가 존재하면 A는 가역행렬(invertible matrix)이라고 한다. $$ AB = I_{n} = BA $$ 이때 B를 A의 역행렬(inverse matrix)이라고 한다. 이러한 B가 존재하지 않으면 비가역행렬(noninvertible matrix)이라고 한다. A가 가역이면 B도 가역이고, B가 A의 역행렬이면 A는 B의 역행렬이다. 비가역행렬을 특이행렬(singular matrix), 가역행렬을 비특이행렬(nonsingular matrix)라고도 한다. 예제) 다음 행렬 A, B에 대해 B는 A의 역행렬임을 확인하라. $$A = \begin{bmatrix}-2 & -5 \\-1 & -3 \end{bmatrix}$$ $$B = \begin{bmat.. 2023. 10. 20. [선형대수학] 단위 행렬(identity matrix)란? 1이 실수에서 곱셈에 대한 항등원이듯 단위행렬은 행렬에서 곱셈에 대한 항등원이다. 주대각선 성분이 모두 1이고 나머지 성분이 모두 0인 n차 정사각행렬을 n차 단위행렬(identity matrix)이라고 한다. n차 단위 행렬은 아래와 같이 나타낸다. A가 m X n 행렬일 때, 다음이 성립된다. 2023. 10. 20. [선형대수학] 행렬 연산의 성질 A, B, C는 연산을 수행할 수 있는 크기의 행렬이고, a, b는 스칼라라고 할 때, 다음이 성립한다. (1) A + B = B + A (덧셈에 대한 교환법칙) (2) A + (B + C) = (A + B) + C (덧셈에 대한 결합법칙) (3) A(BC) = (AB)C (곱셈에 대한 결합법칙) (4) A(B + C) = AB + AC (분배법칙) (5) (B + C)A = BA + CA (분배법칙) (6) a(B + C) = aB + aC (7) (a + b)C = aC + bC (8) (ab)C = a(bC) (9) a(BC) = (aB)C = B(aC) 2023. 10. 20. [선형대수학] 행렬의 곱(multiplication) AB 구하는 법 행렬 A의 크기가 m X p, 행렬 B의 크기가 p X n일 때, 두 행렬의 곱 AB은 m X n 행렬이다. AB(i, j)성분은 A의 i행에 있는 각 성분에 B의 j열에 있는 각 성분을 차례로 곱하여 모두 더 한 것이다. 따라서 A와 B의 곱은 A의 열의 개수와 B의 행의 개수가 같을 때만 정의된다. 행렬의 곱에 대한 교환법칙 AB = BA는 성립하지 않는다. 2023. 10. 20. [선형대수학] 행렬의 합(sum)과 스칼라 배(scalar multiplication)이란? 행렬의 합(sum) 두 행렬의 합은 대응되는 성분끼리의 합이다. 두 행렬의 크기가 서로 다르면 두 행렬은 합할 수 없다. 스칼라 배(scalar multiplication) 행렬 A의 스칼라 배 kA는 A의 모든 성분을 k배하는 것이다. 2023. 10. 20. [선형대수학] 행렬이 상등(equality)한다는 뜻은? 두 행렬에서 같은 위치에 원소가 서로 같은 것을 ‘상등(equality)한다’고 한다. A = B로 나타낼 수 있다. 두 행렬의 크기가 같을 때에만 행렬의 상등을 논할 수 있다. 2023. 10. 20. [선형대수학] 행렬(matrix)/ 행백터 / 열백터란? 일반적으로 자연수 m, n에 대해 m X n개의 수를 다음과 같이 직사각형 모양으로 배열한 것을 행렬(matrix)이라고 한다. 그 각각의 수를 행렬의 성분(entry)이라고 한다. 행렬 A의 i번째 가로줄을 A의 i행(i-th row of A) 또는 i번째 행백터(row vector)라 한다. 행렬 A의 j번째 세로줄을 A의 j행(j-th column of A) 또는 j번째 열백터(column vector)라 한다. 행렬 A의 i행과 j열이 겹쳐지는 부분에 있는 성분을 행렬 A의 (i, j) 성분이라고 한다. 2023. 10. 20. [선형대수학] 행렬의 크기(size)란? m개의 행(row)과 n개의 열(colmn)을 갖는 행렬 A를 크기(size)가 m X n인 행렬이라 한다. 예제 다음 행렬 A의 크기는? $$A = \begin{bmatrix}1 & -3 & 4\\2 & 0 & 3 \\6 & 2 & -5\end{bmatrix}$$ 행의 수 3, 열의 수 3이므로 3 X 3이다. ‘삼바이삼’이라고 읽으면 된다. 2023. 10. 19. [선형대수학] 기본 행 연산(elementary row operation)이란? 첨가행렬(agumented matrix)을 다음과 같은 방법으로 변화시키는 것을 기본 행 연산(elementary row operation)이라고 한다. 참고: 첨가행렬(agumented matrix)이란? (클릭) ▼ 첫 번째 식에 -2를 곱하여 두 번째 식에 더한다 2023. 10. 19. [선형대수학] 첨가행렬(agumented matrix)란? n개의 미지수를 갖는 m개의 일차방정식으로 이루어진 다음 연립일차방정식(system of linear equations)에 대하여 그 계수만을 직사각형 모양으로 배열한 것을 첨가행렬(agumented matrix)이라고 한다. 첨가행렬(agumented matrix)의 가로줄을 행(row), 세로줄을 열(column)이라 한다. 2023. 10. 19. [선형대수학] 방정식(equation)에서 동치(equivalent)란? 연립일차방정식(system of linear equations)에서 n개의 미지수에 어떤 수를 각각 대입했을 대, 각 방정식이 모두 성립하면 순서쌍 (어떤 수1, 어떤 수2, ..., 어떤 수n)를 이 연립일차방정식의 해(solution)이라고 한다. 연립일차방정식의 해 전체의 집합을 연립일차방정식의 해집합(solution set)이라고 한다. 동일한 해집합을 갖는 두 연립일차방정식을 동치(equivalent)라고 한다. 예를 들어, 다음 두 연립 일차 방정식은 모두 (2, 1)을 해로 가지므로 동치이다. x + y = 3 x - y = 1 2x + 2y = 6 3x - 3y = 3 2023. 10. 19. [이산수학]최소신장 트리란?/ 최소신장 트리 구하는 알고리즘 [이산수학]최소신장 트리란?/ 최소신장 트리 구하는 알고리즘(프림,크루스칼) ■ 신장 트리(Spanning Tree)란? 그래프 G의 꼭짓점을 모두 노드로 포함하는 트리 T ■ 최소신장 트리(Minimal Spanning Tree)란? 그래프 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T 최소신장 트리를 구하기 위해서는 노드와 노드를 연결하는 변에 가중치가 부여된 그래프가 있어야 합니다. 또한 비용이 최소인 트리로 만들기 위한 알고리즘도 필요합니다. ■ 최소신장 트리 구하는 알고리즘 프림 알고리즘(Prim Algorithm) 그래프 G의 변 중 비용이 가장 낮은 변들을 가지로 연결시켜서 트리로 만드는 알고리즘 ▶프림 알고리즘 설명 더 보러가기 크루스칼 알고리즘(Kruskal Algor.. 2020. 8. 30. [이산수학]최소신장 트리 구하는 크루스칼 알고리즘(Kruskal Algorithm) 이란? [이산수학]최소신장 트리 구하는 크루스칼 알고리즘(Kruskal Algorithm) 이란? 크루스칼 알고리즘은 프림 알고리즘과 마찬가지로 그래프 G의 변들 중 비용이 가장 낮은 변들을 가지로 연결시켜 트리를 만드는 알고리즘입니다. 프림 알고리즘은 이미 연결되 노드에 근접하는 가지 중 최소 비용을 갖는 가지를 선택했지만, 크루스칼 알고리즘은 연결 여부와 상관없이 가장 비용이 낮은 가지를 연결해갑니다. ▶프림 알고리즘에 대해 더 알고 싶다면 ■ 크루스칼 알고리즘(Kruskal Algorithm) 그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘 (1) 가중치가 가장 작은 변을 차례로 선택하여 노드들을 연결 (2) 가중치가 같은 변은 임의로 선택 (4) 선택된 변에 대해 회로가 형성되는 경.. 2020. 8. 29. [이산수학]최소신장 트리 구하는 프림 알고리즘(Prim Algorithm)이란? [이산수학]최소신장 트리 구하는 프림 알고리즘(Prim Algorithm)이란?_예제포함 최소신장 트리(Minimal Spanning Tree)란 '그래프 G의 꼭짓점을 모두 노드로 포함하면서 비용을 최소로 하는 트리 T'입니다. 그래서 최소신장 트리를 구하기 위해서는 다음 두 가지 요소가 있어야 합니다. 1. 노드와 노드를 연결하는 변에 가중치에 부여된 그래프 2. 비용이 최소인 트리로 만들기 위한 알고리즘 2번의 알고리즘에는 프림 알고리즘(Prim Algorithm)과 크루스칼 알고리즘(Kruskal Algorithm)이 있습니다. 이 글에서는 프림 알고리즘에 대해 알아보겠습니다. ■ 프림 알고리즘(Prim Algorithm) 그래프 G의 변 중 비용이 가장 낮은 변들로 트리를 구성하는 알고리즘 (1.. 2020. 8. 28. [이산수학]이진 탐색 트리란?_예제포함 [이산수학]이진 탐색 트리의 정의(예제포함) 탐색(Search): 어떤 원소를 찾아가는 과정 키(key): 탐색에서 기준이 되는 값 ■ 이진탐색트리(Binary Search Tree)란 노드가 가지는 데이터의 크기에 따라 노드의 위치를 탐색할 수 있는 트리 1. 트리에서 탐색되는 모든 원소는 서로 다른 유일키를 갖는다. 2. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다. 루트 15를 기준으로 왼쪽 서브 트리는 15보다 작은 값들로 구성되고, 오른쪽 서브 트리는 15보다 큰 값들을 구성됩니다. 즉 15는 탐색되는 모든 원소들의 유일키가 됩니다. 왼쪽 서브 트리를 보면 12를 기준으로 12보다 작은 값은 왼쪽 버스 트리를 .. 2020. 8. 27. [이산수학]이진트리 순회표기법의 종류(전위표기, 중위표기, 후위표기)_예제포함 [이산수학]이진트리 순회표기법의 종류(전위표기, 중위표기, 후위표기)_예제포함 ■ 순회표기 이진 트리는 수식을 표현하는 방법에도 사용할 수 있습니다. 예를 들어 (a + b) × (c - d)를 표현하면 아래와 같은 트리가 됩니다. 이와 같이 식을 이진 트리로 표현할 수 있는 것처럼 식을 순회방식으로 표기할 수 있습니다. ■ 전위표기 위 이진트리를 전위표기로 나타내면 × + ab - cd 로 연산자가 피연사자보다 앞에 옵니다. ■ 중위표기 위 이진트리를 전위표기로 나타내면 a + b × c - d 로 연산자가 피연사자들의 중간에 옵니다. ■ 후위표기 위 이진트리를 전위표기로 나타내면 ab + cd - × 로 연산자가 피연사자들의 뒤에 옵니다. 예제 식 (x / y) + (w - z) × v를 전위표기, .. 2020. 8. 26. [이산수학]이진트리의 순회(전위순회, 중위순회, 후위순회) [이산수학]이진트리의 순회(전위순회, 중위순회, 후위순회) 모든 노드의 데이터를 처리할 수 있도록 한 번씩 방문하는 방법을 순회(Traversal)라고 합니다. 서브 트리에서 루트 노드(P)를 언제 방문하느냐에 따라 전위순회, 중위순회, 후위순회가 있습니다. 먼저 노드를 방문하는 순서를 확인하겠습니다. ■ 노드를 방문하는 순서 1 항상 루트에서 시작합니다. 즉, 트리의 레벨 0에서 시작합니다. 2 서브 트리에 대한 순회의 순서는 항상 왼쪽에서 오른쪽으로 이루어집니다. 3 데이터를 읽기 전에 왼쪽, 혹은 오른쪽 노드가 있는지 확인하는 작업을 합니다. 그럼 각 순회는 어떤 방식으로 이루어지는지 보겠습니다. ■ 전위순회(Preorder Traversal) 루트 노드 - 왼쪽 노드 - 오른쪽 노드 순으로 방문하.. 2020. 8. 26. 이전 1 2 3 4 다음
