알고리듬 Get the elements of each layer in the tree를 알아보겠습니다. 트리 구조에서 각 계층마다 숫자들을 구해보겠습니다. ​ ​ ​ 아래의 트리를 예로 들어봅시다. 1 계층의 값은 1 2 계층의 값은 2, 3 3 계층의 값은 4, 5, 6 4 계층의 값은 7 깊이 우선 탐색 DFS의 전위 순회(Preorder Traversal)를 사용하면 먼저 계층부터 내려가면서 탐색하기 때문에 손쉽게 구할 수 있습니다. DFS의 설명은 아래 글에서 확인할 수 있습니다. https://shwoghk14.blogspot.com/2023/01/algorithm-dfsdepth-first-search.html 끝. 카테고리: Algorithm

알고리듬 DFS(Depth-first search)를 알아보겠습니다. DFS는 깊이 우선 탐색인데요. 2진 트리가 있을 때 깊이를 먼저 탐색하는 것을 말합니다. ​ ​ 아래와 같은 트리가 있다고 봅시다. 깊이 우선 탐색은 아래로 내려간다는 뜻입니다. 즉, 1 번 다음에 2 번으로 가고 4 번으로 내려가면서 먼저 탐색을 합니다. 이와는 다른 개념으로 옆으로 탐색하는 방법인 BFS(Breadth-first search) 너비 우선 탐색도 있습니다. 여기서는 BFS는 다루지 않겠습니다. ​ ​ 이 트리를 DFS로 모두 탐색하는 방법에는 3가지가 있습니다. Preorder Traversal, 전위 순회 (Root -> Left -> Right) Inorder Traversal, 중위 순회 (Left -> Root -> Right) Postorder Traversal, 후위 순회 (Left -> Right -> Root) ​ Pre(전), In(중), Post(후)가 뜻하는 것은 root(첫 노드)의 위치입니다. ​ 차례대로 봅시다. ​ 전위 순회(Preorder Traversal)의 경우 첫 노드(Root) -> 왼쪽(Left) -> 오른쪽(Right) 순서로 탐색합니다. 탐색 순서는 다음과 같이 됩니다. 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 중위 순회(Inorder Traversal)의 경우 왼쪽(Left) -> 첫 노드(Root) -> 오른쪽(Right) 순서로 탐색합니다. 탐색 순서는 다음과 같이 됩니다.

알고리듬 Get modular inverse value를 알아보겠습니다. ​ 나머지 연산 역원을 구하기 위한 전제 조건이 필요합니다. A mod M에서 A와 M이 서로소여야 합니다. ​ https://shwoghk14.blogspot.com/2019/03/euclidean-algorithm.html 유클리드 호제법으로 다음 식이 성립합니다. 그리고 확장 유클리드(Extended Euclidean algorithm)와 혼합하면 다음과 같이 표현됩니다. 두 식은 동일하므로 x와 x1, y와 y1과의 관계로 표현하면 다음과 같이 됩니다. 이것을 코딩으로 표현하면 됩니다. (7 mod 25)^-1 결과는 18이네요. 끝. 카테고리: Algorithm

알고리듬 Multiply exponents like binary를 알아보겠습니다. ​ 지수의 성질 중, 곱하기는 더하기가 됩니다. 예를 들어서 x^2 * x^3 = x^5처럼 말이죠. ​ 어떤 목표 지수 숫자가 있을 때, 지수의 합이 해당 숫자가 되도록 만들어 봅시다. ​ 이때, 이진법을 이용합니다. 이진법은 다음과 같이 0과 1로 구성되어 있습니다. 그리고 자릿수마다 각 숫자가 나타내지는데, 24는 0001 1000으로 표기되고, 10진법으로 변환하면 16 + 8이 됩니다. 이번 시간에서는 x^24를 x^16*x^8로 구하는 알고리듬을 알아봅시다. 7 번째 줄에서 현재 계산하는 위치에 비트가 1 위치하면 tmp를 곱합니다. 11 번째 줄에서 비트를 하나씩 오른쪽으로 옮깁니다.  ​ ​ 결과는 동일합니다. 직접 손으로 계산해 보면 다음과 같이 됩니다. 0001 1000인데, 이때 tmp는 3^2가 됩니다. 0000 1100인데, 이때 tmp는 3^4가 됩니다. 0000 0110인데, 이때 tmp는 3^8이 됩니다. 0000 0011인데, 이때 tmp는 3^16이 됩니다. x는 3^8이 됩니다. 0000 0001인데, 이때 tmp는 3^32가 됩니다. x는 3^8 * 3^16 = 3^24가 됩니다. ​ ​ ​ ​ 끝. ​ 카테고리: Algorithm

수학 나머지 연산 역원(Modular multiplicative inverse)를 알아보겠습니다. ​ 나머지 연산 글에서 나눗셈은 적용되지 않는다는 사실을 알았습니다. https://shwoghk14.blogspot.com/2023/01/modular-arithmetic.html 그래서 우리는 역원을 이용하여 곱셈을 활용해야 합니다. 역원이란 둘을 곱했을 때, 1이 되는 수를 말합니다. 5의 역원은 1/5입니다. 이것을 나머지 연산에 표현하면 이렇게 표현합니다. 나머지 연산의 역원은 다음과 같은 방법으로 구합니다. A^-1 자리에 0~(M-1)까지 숫자를 넣어가면서 1이 되는 것을 찾습니다. ​ ​ 24 mod 11의 역원을 찾아봅시다. 위의 그림에서 6을 곱했을 때 나머지가 1이 나옵니다. 따라서 24 mod 11의 역원은 6이 됩니다. ​ ​ 그럼 위의 나눗셈 식을 다시 해볼까요? 48/24 mod 11을 역원을 이용해서 곱셈 법칙으로 계산 가능합니다. 역원이 존재하기 위해서는 조건이 필요합니다. A와 M이 최대 공약수가 1 인 서로소여야 합니다.  ​ 유클리드 호제법(Euclidean algorithm)을 사용하면 최대 공약수가 1인 것을 쉽게 찾을 수 있습니다. https://shwoghk14.blogspot.com/2019/03/euclidean-algorithm.html 우리가 역원을 찾던 행위를 확장 유클리드 호제법을 사용하면 수식으로 표현할 수 있습니다. 여기서 y가 A^-1이 됩니다. ​ ​

수학 나머지 연산(Modular arithmetic)을 알아보겠습니다. ​ 나머지 연산이란 어떤 숫자를 나누고 남은 나머지를 말합니다. 보통 나눗셈은 몫을 구하는 용도인데요. 나머지 연산은 나머지에 관심을 가져주는 연산입니다. ​ ​ 표현은 아래와 같이 합니다. 24를 11로 나눴을 때 나머지는? 답은 2입니다. 11 * 2 + 2 ​ ​ 아래와 같이 같은 나머지를 가지는 두 나머지 연산이 있습니다. 이 둘은 합동(Congruence)라고 하며, 다음과 같이 표기합니다. 합동 관계는 다음과 같은 특징이 있습니다. a = b + km a - b = km 즉 두 숫자를 뺀 값이 m의 배수가 되면 됩니다. 위의 24 ≡ 35 (mod 11)의 경우 35 - 24 = 11이 되어 1 x 11이 되므로 합동 관계가 맞습니다. ​ ​ 음수에 대한 나머지 연산의 경우 다음과 같이 구합니다. -24보다 큰 11의 배수를 더합니다. 여기선 33이 크네요. 그러면 3*11 - 24 = 9 즉 9 mod 11과 같습니다. ​ 나머지 연산의 산술 특징을 알아봅시다. 두 수의 합 나머지 연산은 각 각의 나머지 연산 더하기 나머지 연산을 한 것과 같습니다. (A + B) mod M = (A mod M + B mod M) mod M ​ 예시 25 mod 11 = (11 mod 11 + 14 mod 11) mod 11 25 mod 11 = 3 (0 + 3) mod 11 = 3 ​ 증명은 다음과 같습니다.

수학 조합(Combination)을 알아보겠습니다. ​ 조합은 순서와 상관없이 나올 수 있는 경우의 수를 말합니다. 기호는 다음과 같이 사용합니다. ​ 총 n 개가 있고, 여기서 r 개를 고르는 걸 의미합니다. 이것을 수식으로 쓰면 이렇게 됩니다. 예를 들어 1, 2, 3, 4, 5가 적힌 공을 5 개가 있고, 여기서 3 개를 뽑는 것이라고 한다면 다음과 같이 표현됩니다. 이 경우, 나올 수 있는 경우의 수는 무엇일까요? 10 가지입니다. ​ ​ 조합의 다른 특징은 두 조합의 값이 같다는 것입니다. 이것을 적용해 보면 다음과 같습니다. n 개중 n 개를 뽑는 것과 n 개중 0 개를 뽑는 경우의 수는 1입니다. 순열과의 차이점을 알아볼까요? 아래는 순열의 설명입니다. https://shwoghk14.blogspot.com/2022/12/permutation.html 5 개의 공 중에서 2 개를 뽑는 경우를 생각해 봅시다. 1, 2, 3, 4, 5 ​ 순열 순서를 상관하므로. 20 가지 1, 2 1, 3 1, 4 1, 5 2, 1 2, 3 2, 4 2, 5 3, 1 3, 2 3, 4 3, 5 4, 1 4, 2 4, 3 4, 5 5, 1 5, 2 5, 3 5, 4 조합 순서를 상관하지 않으므로. 10 가지 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5 3, 4 3,