Multiplication of Large Integers (아주 큰 정수의 곱셈)
2020. 4. 18. 12:04
🕶 Algorithm/알고리즘
2.6 Arithmetic with Large Integer 2.6.2 Multiplication of Large Integers 굉장히 큰 정수의 곱셈은 어떻게 할까? 배열로 표현 한다. n자리 정수의 곱 시간복잡도는? n자리 정수 2개 곱셈 = O(n^2) 그럼 Divide and conquer로 시간복잡도를 낮춰보자. n자리 정수를 절반으로 나눠서 계산하자 m은 n자리 정수를 2로 나눈 값이다. u와 v 는 n자리 정수이다. >>> integer 타입이 아니라 배열이다. if ( u 나 v 가 0이면 ) : 곱이 0이니까 0이고 else if ( threshold보다 작다면 ) : u와 v를 그냥 곱한다. else : m은 n을 2로 나눈 값이고 divide는 나눈 몫을 나타낸다. 이때 divde는..
Strassen Algorithm
2020. 4. 17. 12:57
🕶 Algorithm/알고리즘
행렬의 곱셈 크기가 n x n인 두 행렬 A와B의 곱을 C로 나타내고자 한다. 의 원소를 라 하고, 는 가로 는 세로를 나타낸다. B와 C도 동일하게 표시한다. 행렬의 곱셈을 다음과 같이 표현할 수 있다. C하나의 원소를 구하는데 드는 비용은, 곱셈 번과 덧셈 번이다. 따라서, C 전체를 구할 경우 C의 크기는 n x n 이므로 곱셈을 번 그리고 덧셈을 번하게 된다. 따라서, 두행렬을 구하는 복잡도는 이 된다. 알고리즘 A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다. 만약 A와 B가 2ⁿ × 2ⁿ 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다. 이제 A, B, C를 같은 크기의 정..
Divide-and-Conquer (part4)
2020. 4. 2. 17:34
🕶 Algorithm/알고리즘
이걸 Divide-and-Conquer 해보자. 이걸 C행렬에 갖다 놓는다. C행렬의 첫번째 칼럼 ADD = 행렬의 덧셈의 관한 함수 문제 나온다 그니까 Master theroem 공식 외워라 ! Recursive Matrix Multiplication에 적용 (n/2 - n/2) 행렬 M7 까지 n/2 by n/2 행렬이다. scalart multiplicationdml 횟수 scalar addtion = 0 Scalar additon의 횟수
Divide-and-Conquer (part3)
2020. 4. 2. 16:18
🕶 Algorithm/알고리즘
Divide-and-Conquer 시간복잡도 함수의 일종의 공식 P 633 + 110 = ppt 743 자세한 설명 : https://ratsgo.github.io/data%20structure&algorithm/2017/09/11/recurrence/ 재귀함수의 계산복잡도 · ratsgo's blog 이번 글에서는 알고리즘의 계산복잡도 함수가 재귀식(Recurrence relation) 내지 점화식 형태로 표현되는 경우를 살펴보도록 하겠습니다. 재귀식 또는 점화식이란 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)처럼 수열의 항 사이에서 성립하는 관계식을 말합니다. 이로부터 데이터 수 $n$에 대해 닫힌 형태(closed-form expression)의 정확한 계산복잡도..
Divide-and-Conquer (part2)
2020. 3. 31. 23:04
🕶 Algorithm/알고리즘
퀵정렬 설명 → 더보기 더보기 · ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘 · 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다 · 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. · 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 과정 설명 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) ..
알고리즘 과제 #1
2020. 3. 28. 16:51
🕶 Algorithm/알고리즘
※ 12번 문제에 대한 답안은 교재에서 사용하는 pseudocode 형태로 알고리즘을 쓰시오. (2) 과제 제출은 pdf 파일로 만들어서 Bb에 업로드한다. Write a θ(n) algorithm that sorts n distinct integers, ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: Use a kn element array.) k는 일정한 양의 정수이고, n개의 서로 다른 정수를 1에서 kn까지 정렬하는 θ(n) 알고리즘을 작성하라. (힌트: kn 요소 배열 사용) https://ict-nroo.tistory.com/58 [Algorithm] 3-7. Counting So..
Divide-and-Conquer (part1)
2020. 3. 26. 15:08
🕶 Algorithm/알고리즘
풀어야할 인스턴스를 몇개로 나눈다. 부분으로 나누고 그 각 부분을 재귀적으로 해를 구한다. 그리고 원래 instance의 해를 구하는 것이다. Binary Search가 가장 기본적인 Divide and conquer이다. >> 합병정렬 알고리즘의 구체적인 개념 더보기 합병 정렬(merge sort) 알고리즘의 구체적인 개념 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 다음의 단계들로 이루어진다. •분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. •정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 ..
Algorithms Chapter 1 (part4)
2020. 3. 23. 14:39
🕶 Algorithm/알고리즘
둘 중에 누가 더 클지 모를 때 g(n)을 f(n)으로 나눠서 극한값을 취해주면 알 수 있다. 정 모르겠으면 로피탈써라. 분모 미분 분자 미분 근데 이 정도로는 나오지 않을 것이다. recurrsive 한 알고리즘 fib(n){ if(n
Algorithms Chapter 1 (part3)
2020. 3. 19. 16:53
🕶 Algorithm/알고리즘
Order는 한마디로 하면 시간복잡도 함수에서 상수를 무시하고 n값(input)이 클 때 어떻게 behave하느냐를 나타낸다. 우리가 다루는 알고리즘의 효율성이라는 것은 input사이즈가 클 때 문제가 된다. 왜 무시하느냐? 3n^2인 것은 다른 컴퓨터로 돌리면 0.5n^2 정도 차이밖에 안난다. 그래서 상수를 무시하고 나타낸다. 또 차수가 높은 항만 취해서 나타내고 차수가 낮은 항은 무시한다. 0.1 n^2이 n보다 언젠간 커진다. asymtotic x축은 input 사이즈, y축은 걸리는 시간과 비례 빅O의 f(n)의 정의이다. time complexity function 들의 집합이다. 양의 실수인 상수 c가 존재하고, 음이 아닌 정수 n이 존재해서 g(n)
Algorithms Chapter 1 (part2)
2020. 3. 16. 21:31
🕶 Algorithm/알고리즘
오늘은 알고리즘의 효율성 분석에 대해 알아보자 알고리즘의 효율성 분석은 시간 복잡도 함수로 나타낸다. f(n)의 BigO를 본다. 모든 알고리즘 input이 커질수록 시간이 커진다. 효율성을 나타낼 때 그 알고리즘에 실행에 걸리는 시간을 input 사이즈에 대한 함수로 나타낸다. n = input 사이즈 ,f(n) = 걸리는 시간 input size가 중요하지만 다음에 설명하겠다. 시간 복잡도의 분석을 time complexity analysis라고 한다. T(n)은 걸리는 시간이다. input 사이즈에 대해 걸리는 시간. 시간 복잡도 함수 : time complexity function input size가 같은 인스턴스라도 걸리는 시간이 다를 수 있다. 예를 들어 버블 sort를 보면 순서가 굉장히 ..
Algorithms Chapter 1 (part1)
2020. 3. 16. 18:27
🕶 Algorithm/알고리즘
단순한 연산들의 sequence에 따라서 실행을 하면 그 결과로서 주어진 문제의 solution이 얻어지는 해법이 알고리즘이다. 여기서 중요한 것은 각 스텝이 기계적으로 연산 가능한 단순한 연산이다. 단순하지 않는 연산 : 두 수의 최대 공약수를 구하라 이 과정이 언젠가는 끝나야 한다. 끝나지 않고 영원히 돌아가면 알고리즘이 아니다. 솔루션을 내놓아야 한다. 항상 정확한 솔루션이여야 알고리즘이라고 말할 수 있다. sorting 알고리즘이라고 부를 수 있으려면 그 알고리즘은 어떤 input이 들어오더라고 sorting할줄 알아야 한다. 인스턴스라는 것은 어떤 문제에 무수히 많은 경우가 있다. 최단경로 문제를 보면 최단경로 문제를 푸는 무수히 많은 그래프가 있고, 각각에서 최단경로 문제가 있는것이다. 인스턴..
백준알고리즘 11720번
2020. 1. 28. 20:57
🕶 Algorithm
백준알고리즘 11654번
2020. 1. 28. 20:56
🕶 Algorithm