카라츠바의 빠른 곱셈 알고리즘(1) - O(N^2)

( 여기서 설명하는 알고리즘은 카라츠바를 쓰기 이전의 알고리즘을 설명합니다. )

( 그러므로, 분할 정복을 사용하는 카라츠바 알고리즘은 아래의 사이트로 이동하길 바랍니다. )

                   카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3) (tistory.com)

카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3)

 

 

1. 문제 설명

(1) 카라츠바의 알고리즘은 두 개의 정수를 곱하는 일을 합니다.

 

(2) 32비트 정수 둘을 곱할 때 쓰는 것이 아닌 수백 자리 또는 수만 자리가 되는 큰 숫자들을 다룰 때 사용합니다.

 

(3) 곱셈을 하는 과정은 아래와 같으며, 오른쪽 연산 과정을 쓰시오.

( 오른쪽 그림처럼 입력을 반대로 받는다면, 불편하지만 A[i]에 주어진 자릿수의 크기를 10^i로 쉽게 구할 수 있다. )

( 따라서 A[i] * B[j]의 결과를 c[i+j]에 저장하는 등 직관적으로 코드를 작성할 수 있다. )

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

X

 

출력 조건

X

 

 

입력 예제

1234
5678

 

출력 예제

7 0 0 6 6 5 2 

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

public class Multiply_Two_Integer {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException{
        String str1 = sc.readLine();
        String str2 = sc.readLine();

        ArrayList<Integer> a = toArrayList(str1);
        ArrayList<Integer> b = toArrayList(str2);

        ArrayList<Integer> c = multiply(a, b);
        for(int i=c.size()-1; i>=0; i--) {
            System.out.print(c.get(i) +" ");
        }
    }

    // ArrayList<Integer>로 변환하며
    // 123이 넘어 온다면, 321로 변환해줌.
    private static ArrayList<Integer> toArrayList(String str) throws IOException{
        ArrayList<Integer> c = new ArrayList<>();

        for(int i=str.length()-1; i>=0; i--) {
            c.add(str.charAt(i)-'0');
        }
        return c;
    }

    // 자릿수 올림을 처리하는 메서드
    private static ArrayList<Integer> normalize(ArrayList<Integer> num) {

        // 마지막 자리 수가 올림을 할 경우를 대비하여 0 삽입
        // ex) 9 14 -> 1 0 4 (여기서 마지막 자리수는 9 왼쪽을 의미함)
        num.add(0);

        for(int i=0; i<num.size()-1; i++) {

            // 음수일 경우
            if(num.get(i)<0) {
                int borrow = (Math.abs(num.get(i))+9)/10;
                num.set(i+1, num.get(i+1) - borrow);
                num.set(i, num.get(i) + borrow*10);
            }else { // 양수일 경우
                num.set(i+1, num.get(i+1) + num.get(i)/10);
                num.set(i, num.get(i)%10);
            }
        }

        // 마지막 자리수가 0 그대로라면 0을 삭제
        while(num.size()>1 && num.get(num.size()-1)==0) num.remove(num.size()-1);

        return num;
    }

    // 두 큰 정수를 삭제하는 메서드
    // 시간 복잡도: O(N^2)
    private static ArrayList<Integer> multiply(ArrayList<Integer> a, ArrayList<Integer> b) {
        ArrayList<Integer> c = new ArrayList<>();

        // 각 size를 알기 위해 0을 a,b 사이즈만큼 삽입
        for(int i=0; i<a.size()+b.size(); i++) {
            c.add(0);
        }

        // 계산 수행
        for(int i=0; i<a.size(); i++) {
            for(int j=0; j<b.size(); j++) {
                c.set(i+j, c.get(i+j) + a.get(i)*b.get(j));
            }
        }

        // 자릿수 올림하고 결과값 리턴
        c = normalize(c);
        return c;
    }
}