분류 전체보기
[Algorithm Strategies] 06. Divide & Conquer - Karatsuba Multipy
1. Divide & Conquer 1.1 Karatsuba Multipy - Example Program 1.1.1 Problem - 빠른 곱셈 알고리즘으로, 두 개의 정수를 곱하는 알고리즘 - 32비트 정수 둘을 곱할 때 쓰는 것이 아닌 수백자리, 나아가 수만 자리는 되는 큰 숫자들을 다룰 때 주로 사용 - 이 곱셈 알고리즘을 적용하기 전 기존의 곱셈 알고리즘을 설명 1.1.1.1 O(n2) Mutiply vector DivideConquer::multiply(const vector& a, const vector& b); - 곱셈을 진행할 때 일반적인 정수형 변수가 아닌 정수형 배열을 입력받는 점을 확인 - 이 배열들은 곱할 수의 각 자릿수를 맨 아래 자리부터 저장, 이렇게 순서를 뒤집으면 입출력할 ..