7.1 분할 정복_도입(2)_카라츠바의 빠른 곱셈 알고리즘(Python)

• 참고자료 : [알고리즘2] 07.01. 분할 정복과 카라츠바 알고리즘 in 알고리즘 문제해결전략 (종만북) - YouTube

---

1. 카라츠바의 빠른 곱셈 알고리즘 개요

• 구 소련의 아나톨리 알렉세예비치 카라츠바가 1960년대에 발견한 알고리즘
• 수백자리, 수만 자리가 되는 큰 정수를 곱할때 주로 사용하는 분할 정복의 한 예
• 큰 정수들을 배열을 이용해 저장하고 각 배열의 자리는 십진수의 자릿수를 의미한다.
• 두 큰 정수 A와 B가 있을 때, 배열을 이용하여 10^i번째 자리수를 각각 A[i], B[i]에 저장한다.
• A[i]와 B[j]의 곱셈 값을 C[i+j]에 저장하여 직관적인 코드를 작성할 수 있다.

---

2. 두 큰 수를 곱하는 O(n^2)시간 알고리즘

  카라츠바의 빠른 곱셈 알고리즘을 구현하기 전에 먼저 마찬가지로 큰 정수를 배열에 저장하여 곱하는 알고리즘에 대해 구현한다. 이 코드를 응용하여 아래의 카라츠바의 빠른 곱셈 알고리즘을 작성할 수 있다.

 

(1) 자릿수 올림을 처리하는 함수

# 자리수 올림을 처리하는 함수
def normalize(num):
    num.append(0)

    for i in range(len(num) - 1):
        if num[i] < 0:
            borrow = (abs(num[i]) + 9) // 10 # 괄호 실수
            num[i+1] -= borrow
            num[i] += borrow * 10 # 복합 대입 연산자 빼먹음

        else:
            num[i+1] += num[i] // 10
            num[i] %= 10

    while len(num) > 1 and num[len(num)-1] == 0:
        num.pop(len(num)-1)

• 매개변수로 들어오는 num은 앞서 설명한 것 처럼 엄청 큰 수를 배열로 표기한 것이다.
• 자릿수 올림을 처리하면서 배열의 길이가 달라 질 수 있기 때문에(예를 들어 5 * 2의 경우 5와 2인 각 숫자는 1자리지만 계산하면서 필요한 자릿수는 총 2자리) 먼저 여유 공간으로 배열에 자리를 하나 추가할 필요가 있다.
• if 문의 경우 자릿수가 음수가 되는 경우를 처리하는데 이는 카라츠바의 빠른 곱셈에서 사용한다.
• else 문의 경우 일반적인 곱셈에서 발생하는 양수 자릿수 올림을 처리한다.
• 그리고 함수가 종료될 때 필요없는 자리가 존재할 경우(배열의 끝단의 0이 존재) 이를 삭제한다.

 

(2) 두 자연수의 곱을 반환하는 함수

# 두 자연수의 곱을 반환
# 각 배열에는 각 수의 자리수가 1의 자리에서부터 시작되 저장되어있음
# multiply([3, 2, 1], [6, 5, 4]) = 123*456을 의미
def multiply(a, b):
    # 책의 오타?
    # c = [0] * (len(a) + len(b) + 1)
    c = [0] * (len(a) + len(b) - 1)

    for i in range(len(a)):
        for j in range(len(b)):
            c[i+j] += a[i] * b[j]

    normalize(c)
    return c

• 두 큰 정수 a와 b를 각 자릿수마다 값을 저장하는 배열로 함수에 매개변수로 전달한다.
• 코드의 주석에 나와있는 것 처럼 1234의 경우 10^0자리인 4부터 차례로 [4, 3, 2, 1]꼴로 변환해야 한다. 
• 책에서는 두 정수의 곱을 저장할 c의 초기화를 '[ 0 ] * ( len(a) + len(b) + 1'로 설명하고 있는데 위 참고 영상에서는 +1을 -1로 바꾸는 것으로 사용한다.
• 일단 -1로 해서 시험했을 때나 +1로 시험했을 때 둘 다 예시 문제에 대해서는 정상 작동하는 것으로 보인다.
• 이중 for 문을 통해 두 정수의 자릿수에 대해 곱셈을 진행한다.
• c[i+j]에 그 값을 저장하는 이유는 a * 10^i와 b * 10^j를 곱할 때 그 값은 a*b*10^(i+j)임을 생각하면 이해하기 편하다.
• 곱셈이 끝났다면 위 함수를 통해 각 자리에 존재하는 10이상의 수들에 대한 올림수 처리를 진행하고 반환한다.
• 이 곰셈의 시간 복잡도는 이중 for 문이므로 O(n^2)임을 알 수 있다.

 

(3) 출력 방법

answer = multiply([3, 2, 1], [6, 5, 4])
result = 0
for i in range(len(answer)):
    result += answer[i] * (10 ** i)

print(result)

• 123 * 456의 경우 배열에 [3, 2, 1]과 [6, 5, 4]형식으로 변환하여 계산을 진행한다.
• 개인적으로 귀찮아서 그냥 넣었는데 융통성 있게 하려면 어떤 큰 정수를 입력받아 문자열(str() 혹은 repr() 함수)로 바꾸고 이를 배열에 한 글자씩 집어넣고(list() 함수) 다시 정수로 바꾼 뒤 순서를 뒤집으면(a[::-1]) 될거 같다.
• 그리고 계산된 결과는 배열의 인덱스에 해당 하는 만큼 10의 거듭제곱을 한 뒤에 이를 합하여 출력하면 끝!

---

3. 카라츠바의 빠른 곱셈 알고리즘 코드 구현

(1) 분할 정복을 통한 문제 분할

• 카라츠바의 빠른 곱셈 알고리즘은 위의 O(n^2)시간 알고리즘보다 더 빠르다.
• 분할 정복의 방법을 이용하여 큰 정수를 절반으로 쪼개서 계산한다.
• 만일 a와 b가 256자리 수인 경우 각각 128자리씩 나누어 사용한다.

• 처음에 이 부분이 직관적으로 이해되지 않았는데 만일 1234인 경우를 예시로 들면 1234 = 12 * 10^2 + 34로 표현하면 이해가 쉬웠다.
• a와 b를 위 처럼 절반으로 쪼개면 a * b는 다음과 같이 표현할 수 있다.

• 여기서 10^256과 10^128을 곱하는 건 나중에 자릿수 연산을 통해 구현할 수 있으므로 곱셈으로 치지 않으면 다음과 같이 3개의 곱셈만으로 값을 계산할 수 있음을 알 수 있다.

• 이를 응용하여 코드를 작성하면 카라츠바의 빠른 곱셈 알고리즘을 구현할 수 있다.

 

(2) 코드로 구현한 카라츠바의 빠른 곱셈 알고리즘

from code7_3 import normalize, multiply

# a, b : 정수의 리스트
# k : 정수

# a += b * (10 ** k)
def addTo(a, b, k):
    # 자리수 맞추기
    newsize = max(len(a), len(b) + k)

    # 동일한 자리수가 되도록 0추가
    while (len(a) != newsize):
        a.append(0)

    while (len(b) != newsize):
        b.append(0)

    # b의 최소 자리수부터 부터 더함
    for i in range(k, newsize):
        a[i] = a[i] + b[i - k]

    # 반올림 처리
    normalize(a)

# a -= b (a >= b를 가정함)
def subFrom(a, b):
    for i in range(len(b)):
        a[i] -= b[i]

    normalize(a)

def karatsuba(a, b):
    an = len(a)
    bn = len(b)

    # a가 b보다 짧은 경우 교체
    if an < bn:
        return karatsuba(b, a)

    # 기저 사례 1 : a나 b가 빈 리스트인 경우
    if an == 0 or bn == 0:
        return []

    # 기저 사례 2 : a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경
    if an <= 2:
        return multiply(a, b)

    half = an // 2

    a0 = a[:half]
    a1 = a[half:]
    b0 = b[:min(bn, half)]
    b1 = b[min(bn, half):]

    z0 = karatsuba(a0, b0)
    z2 = karatsuba(a1, b1)

    addTo(a0, a1, 0)
    addTo(b0, b1, 0)

    z1 = karatsuba(a0, b0)

    subFrom(z1, z0)
    subFrom(z1, z2)

    result = []
    addTo(result, z0, 0)
    addTo(result, z1, half)
    addTo(result, z2, 2*half)

    return result

• 먼저, 위에서 구현한 normalize() 함수와 multiply() 함수를 사용할 필요가 있다.
• 위의 normalize() 함수에서 자릿수가 음수인 경우도 처리했었는데 그 이유를 subFrom() 함수에서 찾을 수 있다.
• 기본적으로 앞서 말한 것 처럼 a와 b를 분할하여 z0과 z2를 재귀 호출을 통해 계산한다.
• 그리고 z0과 z1의 결과값을 이용하여 z1을 구한다.
• 마지막에 result 리스트에 계산된 값들의 자릿수를 맞추어 최종 결과값을 반환한다.

 

(3) 시간 복잡도 분석

• 사실 책의 설명에 나와있는 시간 복잡도 분석을 제대로 이해하지는 못했기 때문에 대략적으로나마 이해한 것을 바탕으로 분석을 해보면 다음과 같다.
• 정수의 자리수가 n이고 n은 2의 거듭제곱인 2^k이라고 했을 때 정수를 반으로 나누기 때문에 재귀 호출의 깊이는 k가 된다.(1234의 자리수는 4=2^2이고 재귀 호출은 1234를 12와 34로 나눈 깊이 1의 재귀 호출 그리고 12를 1과 2로 그리고 34를 3과 4로 나누는 총 깊이 2의 재귀 호출)
• 그리고 한 번 분할할 때 마다 3번의 곱셈을 하기 때문에 마지막 단계에서 총 3^k의 부분 문제가 발생한다.
• 그러나 두 수는 한 자리 수까지 분할 되므로 곱셈의 수는 O(3^k)가 된다.
• n = 2^k이므로 k는 밑이 2인 logN이다.(k = logN)
• 이를 곱셈의 수 n에 대해 표현하면 O(3^k) = O(3^logN) = O(N^log3)이 된다.
• (사실, O(3^logN) = O(N^log3)이 정확하게 왜 성립하는지 잘 모르겠다. 아마 임의의 두 함수 y = 3^logN과 y = N^log3의 양변에 log를 취하면 둘이 똑같이 나타나기 때문으로 생각하는게 대략적으로 이해가 된다....)
• 병합 단계의 수행 시간은 addTo() 함수와 subFrom()함수에 의해 지배된다.
• 깊이가 깊어질 때마다 숫자의 길이는 반으로 줄고 부분 문제의 개수는 3배씩 늘기 때문에 필요한 연산의 수는 다음 식에 비례한다.

• 책의 설명에 따르면 이는 n^log3과 같은 속도로 증가한다고 한다.
• 시간 복잡도는 곱셈이 지배하기 때문에 결과적으로 O(n^log3)로 나타난다.(밑이 2인 log3은 대략 1.585)
• 단, 구현이 복잡하기 때문에 입력의 크기가 작은 경우 O(n^2) 알고리즘보다 느린 경우가 많음을 유의해야 한다.

---

4. 후기

  먼저 이 카라츠바의 빠른 곱셈 알고리즘 자체의 이해는 크게 어려운 부분은 없었다. 하지만 시간 복잡도를 계산하는 과정에서 고등과정 수학이 잘 생각이 나지 않아 크게 고생했다. 대략적으로 이해하고 넘어가기 보다는 깊고 정확하게 이해하고 넘어가는 편이 아무래도 좋다는 생각이 드는데 그래도 처음 책보고 코드 짜고 읽고 이해하는 과정 한 번, 그리고 블로그에 글을 정리하면서 이해하는 두 번의 과정을 통해 읽으면 읽을수록 좀 더 깊게 이해하게 되는 경험을 할 수 있음에 나름 수확이 있다고 생각한다.

  분할 정복이 어렵게 느껴지는 부분은 문제를 어떻게 분할하냐에 대한 사고인데 일단은 역시 많은 문제들을 접하고 뒷장에 나와있는 방법들을 익히게 되면 조금 낫지 않을까 하는 기대를 해본다.

---

github 1 : Algorithmic_Problem_Soving_Strategies/code7_3.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies

github 2 : Algorithmic_Problem_Soving_Strategies/code7_4.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies