karatsuba multiplication1 Karatsuba Multiplication 1. 문제 정의 입력 : 두개의 n자리 양수 x, y 출력 : x y 의 곱 2. Grade-School Algorithm 5678 * 1234 계산 시 다음과 같이 계산 5678 * 4 + (5678 * 3) * 10 + (5678 * 2) * 100 + (5678 * 1) * 1000 복잡도는 O(n²) -> 너무 느리다 3. Improving 3.1. Divide and conquer Divide and conquer란? 큰 문제를 더 작고 쉬운 문제들의 모음으로 쪼개어 풀어내는 것 3.2. Integer Multiplication에 적용 1234 = 12 * 100 + 34 1234 * 5678 = (12 * 100 + 34) (56 * 100 + 78) = (12 * 56)10000 + (34 .. 2021. 9. 8. 이전 1 다음 반응형