[#2-2]분할정복-예제: 카라츠바의 빠른 곱셈 알고리즘

러시아의 Karatsuba가 만들어서 Karatsuba(이름이 너무 어려워;;) 알고리즘이라고 한다.

Karatsuba의 빠른 곱셈 알고리즘이 대단한 이유는 간단히 설명하면 보통 곱하기를 코딩으로 작성할 때 이중 포문으로 곱해서 자릿수 올림을 사용하여 계산한다고 생각한다.

Karatsuba는 이것보다 더 빠른 알고리즘(4번 곱할걸 3번으로!)을 작성하였다.

Karatsuba의 빠른 곱셈 알고리즘은 일단 곱할려는 두 수 a, b를 둘 다 반으로 쪼갠다.

여기서 Karatsuba는 이걸 곱해서 4개의 조각으로 만들 생각을 하였다. 그렇게 나온 식이 밑에 사진이다.

그런데 이 상태에서 분할정복을 실행할 경우 시간 복잡도가 O(n^2)이 나오기 때문에 분할 정복을 사용하는 의미가 없어 Karatsuba는 고민을 하게 되고 찾은 방법이 밑에 처럼 z0부터 z3까지 지정 해준 다음 밑에 같은 규칙을 이용하여 곱셈을 4번에서 3번으로 줄이게 된다.

z2곱셈-1번, z0-곱셈 2번, z1-곱셈 3번...마이너스 2번 이걸 어캐 생각했누??

복습하면서 다시 보아도 신기하다 이걸 어떻게 생각한건지 모르겠다.

밑에는 이 수식을 코드로 작성한 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

//num[]의 자릿수를 올림을 처리한다.
void normalize(vector<int> &num)
{
    num.push_back(0); //vector 삽입순서 착각해서 삽질함 ㅋㅋㅋ 자릿수 올라가는 자리를 미리 포함시켜줘야하니까 삽입하는거임

    //자릿수 올림을 처리한다.
    int size = num.size();
    for (int i = 0; i < size - 1; i++)
    {
        if (num[i] < 0) // 계산 결과시 음수일 경우
        {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i + 1] -= borrow;
            num[i] += borrow * 10;
        }
        else
        {
            num[i + 1] += num[i] / 10;
            num[i] %= 10;
        }
    }
    //앞에 남은 0을 제거한다.
    while (num.size() > 1 && num.back() == 0)
        num.pop_back();
}

//두 긴 자연수의 곱을 반환한다.
//각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다.
//예: multiply({3,2,1},{6,5,4}) = 123* 456 = 56088 = {8,8,0,6,5};
vector<int> multiply(const vector<int> &a, const vector<int> & b)
{
    vector<int> c(a.size() + b.size() + 1, 0);

    int A_tmpSize = a.size();
    int B_tmpSize = b.size();
    for (int i = 0; i < A_tmpSize; i++)
    for (int j = 0; j < B_tmpSize; j++)
        c[i + j] += a[i] * b[j];

    normalize(c);
    return c;
}

//a+b=b*(10^k)
void addTo(vector<int>& a, const vector<int>& b, int k)
{
    if (a.size() < b.size() + k)
        a.resize(b.size() + k);

    a.push_back(0); //덧셈시 자릿수 증가를 위해 미리 공간 확보를 위한 삽입

    for (int i = a.size(); i < a.size(); i++)
        a[i] = 0;

    for (int i = 0; i < b.size(); i++)
        a[i + k] += b[i];

    normalize(a);
}

void subFrom(vector<int> &a, const vector<int> &b)
{
    for (int i = 0; i < b.size(); i++)
        a[i] -= b[i];
    normalize(a);
}
//a+=b*(10^k)를 구현한다.
vector<int> karatsuba(const vector<int>& a, const vector<int> &b)
{
    int an = a.size(), bn = b.size();
    //a가 b보다 짧을 경우 둘을 바꾼다.
    if (an < bn) return karatsuba(b, a);
    //기저 사례:a나 b가 비어 있는 경우
    if (an == 0 || bn == 0) return vector<int>();
    //기저 사례: a가 비교적 짧은 경우,O(n^2) 곱셈으로 변경한다.(성능을 위함)
    if (an <= 50)
        return multiply(a, b);
    int half = an / 2;

    vector<int> a0(a.begin(), a.begin() + half);
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
    vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

    //z2 = a1*b1
    vector<int> z2 = karatsuba(a1, b1);
    //z0 = a0 * b0
    vector<int> z0 = karatsuba(a0, b0);
    //z1 = ((a0+a1) * (b0+b1)) -z0-z2
    addTo(a0, a1, 0);
    addTo(b0, b1, 0);
    vector<int> z1 = karatsuba(a0, b0);
    subFrom(z1, z0);
    subFrom(z1, z2);

    //ret = z0 + z1*10^half + z2*10^(half*2)
    vector<int> ret(z2.size() + half*2,0);//
    addTo(ret, z0, 0);
    addTo(ret, z1, half);
    addTo(ret, z2, half + half);
    return ret;
}

int main(int argc, char*argv[])
{
    cout << "계산을 원하는 숫자 뒷자리부터 입력하세요" << endl;

    vector<int> a, b;
    for (int i = 0; i < 3; i++) //더 큰 숫자를 넣어서 확인을 해 보도록 하자 본인은
    {                            //책의 예제 321*123값을 출력하기 위해 밑에 처럼 설정하였다. 이러면 바로 기저사례가 실행되서 디버깅시 코드의 흐름을 못 찾아간다.
        int n;
        cin >> n;
        a.push_back(n);
    }
    for (int i = 0; i < 3; i++)
    {
        int n;
        cin >> n;
        b.push_back(n);
    }

    vector<int> c = karatsuba(a, b);

    cout << "계산결과" << endl;
    for (int i = 0; i < c.size(); i++)
        cout << c[i]<<" ";
    cout << endl;

    return 0;
}
Colored by Color Scripter

'Algorithm' 카테고리의 다른 글

[#2-4]분할정복-문제: 울타리 잘라내기(문제 ID: FENCE) (0)	2021.09.05
[#2-3]분할정복-문제: 쿼드 트리 뒤집기(문제 ID: QUADTREE) (0)	2021.09.05
[#2-1]분할 정복-예제: 수열의 빠른 합과 행렬의 빠른 제곱 (0)	2021.09.05
[#1]완전탐색-n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘 (0)	2021.09.05
이분탐색 구현 팁 및 반환값 줄이기(부제: 공부하며 정리하는 생각들) (0)	2021.08.09

'Algorithm' 카테고리의 다른 글

티스토리툴바