728x90 Algorithm (C++ based)/Math7 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 유클리드 호제법 이란 두 자연수 사이의 최대공약수(GCD) 를 구하는 알고리즘 이다. gcd(a, b) == a 와 b 의 최대공약수 라고 할 때 알고리즘에 사용되는 식은 다음과 같다. gcd(a, b) == gcd(b, a % b) ... (b 2021. 8. 4. CCW (Counter Clock Wise) CCW (Counter Clock Wise) CCW 란? 평면에 존재하는 세 점에 대해서 위치 관계를 알 수 있는 알고리즘이다. 좌표 내 임의의 점이 어떠한 선분을 기준으로 반시계방향에 있다면 양수, 시계방향에 있다면 음수, 선분의 연상선인 직선상에 있다면 0을 출력한다. 설명 공식 : CCW = (Bx - Ax) * (Cy - Ay) - (Cx - Ax) * (By - Ay) CCW 의 값이 양수라면? : 점 C는 선분 AB의 반시계방향에 위치한다. CCW 의 값이 음수라면? : 점 C는 선분 AB의 시계방향에 위치한다. CCW 의 값이 0 이라면? : 점 C는 선분 AB의 직선상에 위치한다. 위 예시 첨부 사진 상에선 점C 가 선분 AB의 반시계방향에 위치하므로 CCW 의 값은 양수가 된다. 점 A,.. 2021. 6. 27. Monge array (Monge matrix) Monge array (Monge matrix) Definition 아래와 같은 조건을 갖는 m-by-n matrix 이다. 의 조건에 대해서 를 만족하는 matrix 를 Monge array 혹은 Monge matrix 라고 한다. Example 위 사진을 보면 Monge array 의 정의를 직관적으로 볼 수 있다. 표시해둔 보라색, 연두색 점들로 예를 들어보자. 이 점들의 i, j, k, l 은 다음과 같다. i = 2 j = 3 k = 4 l = 5 A[2, 3] + A[4, 5] 2021. 2. 3. power 함수 구현 (분할 정복 이용) // Devide and Conquer algorithm 을 통한 power 함수의 구현. What is power function? Code 1 2 3 4 5 6 7 8 9 10 typedef unsigned long long ull; ull power(int num, int jisu) { if (!jisu) return 1; // num^0 = 1 이므로 if (jisu % 2) return (power(num, jisu - 1) * num) % p; ull half = power(num, jisu / 2) % p; return (half * half) % p; } Colored by Color Scripter cs Additional explanation 사실, 혹은 헤더파일에 있는 pow(a, n.. 2021. 1. 29. Pascal's triangle (파스칼의 삼각형) // Pascal's triangle What is Pascal's triangle? 좌측의 수식과 같은 이항계수의 값을 구할 때 사용할 수 있다. 하지만 아래 설명을 보면 알 수 있듯 점화식을 활용한 Dynamic Programming의 알고리즘을 사용하는 형태로, n의 값이 상당히 커진다면 사용하기 곤란한 알고리즘이다. n의 값이 상당히 커졌을 경우에는 Lucas Theorem (뤼카의 정리) 를 사용하면 된다. Explanation 위 파스칼의 삼각형을 나타낸 피라미드 모양의 그림에 연두색 값들은, 위에 있는 두 블록의 값의 합과 같다. 또한 양 변들은 nC0, nCn 이 되므로 값이 1이 된다. 이는 이항계수의 성질로서 증명이 된다. Dynamic Programming으로 C[n][k] 와 같은 .. 2021. 1. 28. Lucas's theorem (뤼카의 정리) // Lucas's theorem What is Lucas's theorem? 를 구하는 과정에서 n의 값이 상당히 클 경우 사용하면 유용한 정리이다. n의 값이 적당하다면, n!, ( n-k )!, k! 의 값을 각각 구하여 연산하면 되지만, n의 값이 10억만 되더라도 unsigned long lnog에 조차 담을 수 없게 된다. 이때 뤼카의 정리를 이용할 수 있다. Theorem 먼저, n과 k를 p진법의 전개식으로 나타내보자. 이때, 다음의 합동식이 성립한다. Example 따라서 아래와 같이 나타낼 수 있다. 따라서 답은 0이 된다. Proof // 아직 작성중인 글 입니다.. 2021. 1. 27. Fibonacci sequence (피보나치 수열) // Fibonacci sequence What is Fibonacci sequence? 란, 임의의 항의 값이 이전의 두 항의 값을 더한 값을 가지는 수열을 의미한다. 이를 점화식으로 표현하면 아래와 같다. An = 1 , ( n > n; // *********** Dynamic programming *********** Fibonacci_dynamic[0] = 0; Fibonacci_dynamic[1] = 1; for (int i = 2; i > num; cout 2020. 11. 6. 이전 1 다음 728x90
