[C++] 큰 수 더하기 (adding big numbers)

반응형

안녕하세요 한주현입니다.

오늘은 C++ 에서 큰 수를 더하는 방법에 대해 알아보겠습니다.

들어가며

100경 더하기 200경은 몇 일까요? (1경 = 10의 16제곱)

→ 네 맞습니다 300경 입니다.

 

이를 C++ 로 코딩해 볼까요?

#include <iostream>

int main() {
    int a, b;
    a = 1000000000000000000;
    b = 2000000000000000000;
    std::cout << a + b << std::endl; // -1651507200
    return 0;
}

코딩 결과 -1651507200 라는 잘못된 값이 나왔습니다.

 

다들 아시겠지만.. int 는 -2^31 에서 2^31-1 까지의 수인 –2,147,483,648 ~ 2,147,483,647 의 값의 범위를 가지고 있기에 이보다 더 큰 숫자가 들어오게 되면 overflow 가 일어나서 제대로 된 연산을 할 수 없게 됩니다.

 

그러므로 100경과 200경을 더하려면 int 대신 long long 이라는 타입으로 변수를 선언해주면 답을 얻을 수 있습니다.

 

long long 은 -2^63 에서 2^63-1 까지의 수인 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 커버할 수 있습니다.

 

#include <iostream>

int main() {
    long long a, b;
    a = 1000000000000000000;
    b = 2000000000000000000;
    std::cout << a + b << std::endl; // 3000000000000000000
    return 0;
}

 

만약 그렇다면 long long 의 범위를 벗어나는 숫자인 110^19 + 210^19 를 연산하면 어떻게 될까요?

 

#include <iostream>

int main() {
    long long a, b;
    a = 10000000000000000000;
    b = 20000000000000000000;
    std::cout << a + b << std::endl;
    return 0;
}

// error: integer literal is too large to be represented in any integer type

→ 제 컴퓨터에서는 컴파일 조차 되지 않으며 오류가 발생하네요.

그렇다면..! 오늘의 주제인 엄청나게 큰 수를 더하려면 어떻게 해야 할까요?

 

큰 수의 더하기 - 더하기의 원리

우선 더하기의 원리를 알아봅시다.

아래 그림처럼, 더하기 연산은 더하려는 각 자리수를 더한 뒤 그 값을 적고 그 다음 자리수를 더해주면 됩니다. 이 때 자리수에서 더하기 연산을 한 값이 10을 넘게 되면 carry (올림수) 가 발생하게 됩니다.

이를 그림으로 표현해보면 아래와 같습니다.

첫 번째 자리의 B와 D를 더한 뒤 이것이 10보다 크거나 같게 되면 올림수가 발생하게 됩니다.

이를 10으로 나눈 나머지 연산 (%)을 하게 되어 자리에 남게 되는 값 (B+D)%10 을 계산합니다.

그리고 올림수인 CARRY1에 1을 넣습니다.

이후 두 번째 자리수인 A+C 를 계산할 때 CARRY1 도 같이 더해줍니다.

 

두 번째 자리도 마찬가지로 A+C+CARRY1이 10보다 크게 되면 올림수가 발생합니다.

이를 고려하여 1을 다음 자리수로 넘겨주도록 CARRY에 1을 넣습니다.

 

큰 수의 더하기 - 코딩

위의 설명을 C++로 코딩해보면 아래와 같습니다.

 

위의 코딩에서 처럼 입력을 숫자로 받게 되면 연산을 할 수 없으므로 문자열 변수 A, B 로 받도록 하겠습니다.

그 다음 이를 각 끝자리 부터 더해가며 carry 를 생성하여 자리수를 더해가는 알고리즘을 짜봅시다.

 

한 가지 주의할 점은 계산해야 하는 전체 자리수를 체크하고 긴 자리수에 맞게 0을 채워 넣어 긴 자리수도 0이랑 더할 수 있게 해줍니다.

 

나머지 설명은 코드에 주석을 달아 놓았습니다.

 

#include <iostream>
#include <vector>

int main()
{
    // 변수 선언
    std::string A, B; // 두 수 A, B 를 선언함
    std::cin >> A >> B; // 두 수를 입력 받음
    std::string zeros = ""; // 짧은 문자열에 0을 채우기 위한 변수
    std::vector<int> res; // 결과를 담을 벡터를 생성
    int carry = 0; // 올림수를 선언

    // 긴 문자열을 찾고 0을 채워넣는 부분
    int lenA = A.size();
    int lenB = B.size();
    int size_diff = lenA - lenB;
    if (size_diff < 0)
        size_diff *= -1;
    for (int i = 0; i < size_diff; i++)
        zeros += "0";
    if (lenA < lenB)
        A = zeros + A;
    else if (lenA > lenB)
        B = zeros + B;
    // else의 경우는 길이가 같은 경우이며 이때는 0을 채울 필요가 없습니다

    // 가장 낮은 자리부터 하여 두 숫자의 자릿수를 더해갑니다
    int n1, n2;
    for (int i = A.size() - 1; i >= 0; i--)
    {
        n1 = A[i] - '0'; // char에 '0' 을 빼면 숫자가 됩니다
        n2 = B[i] - '0';

        // 두 자릿수의 숫자와 carry를 더한 값이 10 이상이면 carry를 만듭니다
        if ((n1 + n2) % 10 + carry == 10)
        {
            carry = 1;
            res.push_back(0);
        }
        else
        {
            res.push_back((n1 + n2) % 10 + carry);
            carry = (n1 + n2) / 10;
        }
    }
    if (carry != 0)
        res.push_back(carry);
    for (int i = res.size() - 1; i >= 0; i--)
    {
        std::cout << res[i];
    }
    std::cout << "\\n";

    return 0;
}

 

완성되었네요!

 

위에서 오류가 났었던 110^19 + 210^19 를 연산을 해 볼까요?

 

$ ./add_large_umber
10000000000000000000 20000000000000000000
30000000000000000000

 

잘 되는군요!

 

마치며

오늘은 큰 자리수의 덧셈에 대해 진행해보았습니다.

 

여러분들께 도움이 되셨으면 좋겠습니다!

 

그럼 다음에 만나요!