C++에서 두 개의 큰 수의 합 구하기

C++의 기본 정수 타입(long long 등)으로는 담을 수 없는 매우 큰 숫자 두 개가 문자열 형태로 주어집니다. 이 문제의 목표는 이 두 큰 수의 합을 정확하게 계산하는 프로그램을 작성하는 것입니다.

문제 이해를 돕는 예시

입력: number1 = "341299123919"
number2 = "52413424"
출력: 341351537343

이 문제를 해결하는 핵심 아이디어는 손으로 직접 덧셈을 할 때와 같습니다. 두 문자열을 일의 자리부터 순회하면서 각 자릿수끼리 더하고, 합이 10을 넘으면 올림수(carry)를 다음 자릿수로 전파하는 방식입니다. 계산된 결과는 한 자릿수씩 결과 문자열에 저장됩니다.

알고리즘

sum = 0, carry = 0으로 초기화한다.
1단계: n부터 0까지 반복한다.
  1.1단계: intSum = number1[i] + number2[i] (+ carry)
  1.2단계: carry = intSum / 10, sum에는 intSum % 10을 추가한다.
2단계: 남아 있는 carry를 sum에 더한다.
3단계: sum을 반환한다.

예제 코드

아래 프로그램은 위에서 설명한 해결 방법이 실제로 어떻게 동작하는지 보여줍니다.

#include<bits/stdc++.h>
using namespace std;

string addBigNumbers(string number1, string number2) {
    if (number1.length() > number2.length())
        swap(number1, number2); // number1이 항상 더 짧도록 정렬
    string sum = "";
    int len1 = number1.length();
    int len2 = number2.length();
    int digitDiff = len2 - len1; // 두 숫자의 길이 차이
    int carry = 0;
    int intSum;
    // 공통 자릿수 부분을 일의 자리부터 더함
    for (int i = len1 - 1; i >= 0; i--) {
        intSum = ((number1[i] - '0') + (number2[i + digitDiff] - '0') + carry);
        sum.push_back(intSum % 10 + '0');
        carry = intSum / 10;
    }
    // 더 긴 숫자의 남은 자릿수 처리
    for (int i = digitDiff - 1; i >= 0; i--) {
        intSum = ((number2[i] - '0') + carry);
        sum.push_back(intSum % 10 + '0');
        carry = intSum / 10;
    }
    // 마지막 올림수가 남아 있다면 추가
    if (carry)
        sum.push_back(carry + '0');
    reverse(sum.begin(), sum.end()); // 역순으로 저장된 결과를 뒤집어 복원
    return sum;
}

int main() {
    string number1 = "235235823852";
    string number2 = "45230820348";
    cout << "두 큰 수의 합은 " << addBigNumbers(number1, number2);
    return 0;
}

출력 결과

두 큰 수의 합은 280466644200

동작 원리와 복잡도

이 알고리즘은 먼저 두 숫자 중 더 짧은 쪽을 기준으로 일의 자리부터 자릿수를 맞춰 더한 뒤, 더 긴 숫자의 나머지 자릿수에는 올림수만 전파하며 처리합니다. 마지막에 올림수가 남아 있으면 결과 앞에 붙여주고, 역순으로 저장된 문자열을 뒤집어 최종 결과를 완성합니다.

시간 복잡도는 두 숫자 중 길이가 긴 값에 비례하여 O(max(N, M))이며, 공간 복잡도 역시 결과 문자열 크기만큼인 O(max(N, M))입니다. 이처럼 문자열 기반 덧셈을 활용하면 자료형의 표현 범위 제한 없이, 메모리가 허용하는 한 임의의 크기를 가진 숫자의 덧셈을 정확하게 처리할 수 있습니다.