[자료구조 및 알고리즘] (1) Integer Multiplication과 Karatsuba Multiplication

1. Computational Problem의 정의 Computational problem은 다음과 같이 세 가지의 스텝으로 나누어 볼 수 있다.

첫째, input을 정의한다. 둘째, output을 정의한다.

셋째, input을 output으로 변환하는 솔루션을 찾는다. 하지만 이 세 번째 스텝에서는 correctness와 efficiency를 반드시 고려해야 한다.

Correctness: 솔루션이 항상 input에 해당하는 올바른 output 값을 주는가? Efficiency: 솔루션의 speed는 얼마나 빠른가?

space를 얼마나 사용해야 하는가? 그러면 이 프레임워크를 사용해서 다음과 같은 정수의 곱셈 문제를 정의해 보자. 2.

Integer multiplication 문제 두 자릿 수 이상의 두 수를 곱한 값을 구하는 문제이다. 어떻게 곱셈을 계산해야 한 자리의 덧셈 및 곱셈을 최소화하면서 곱을 구할 수 있을까?

input: 자릿수가 n인 두 정수, x와 y output: ...