큰 수 덧셈/더하기 알고리즘 구현 (C++) (백준 BOJ 15353 : 큰 수 A+B)

이 포스트에서는 큰 수를 문자열로 입력 받아 두 수의 덧셈을 구하여 출력하는 알고리즘을 다루고 있습니다.

C나 C++에서는 거의 가장 큰 정수 자료형인 long long의 경우에도 9 × 10^18 정도까지밖에 표현하지 못합니다.

따라서 그보다 큰 수를 더하기 위해서는 문자열로 정수를 입력받고, 두 수의 덧셈을 직접 구현해주어야 합니다.

 

 

백준 BOJ 15353 : 큰 수 A+B

 

덧셈의 경우에는 뒤에 있는 작은 자릿수부터 앞에 있는 큰 자릿수 순서대로 덧셈이 진행되므로, 문자열을 입력받은 뒤 길이를 맞춰주고 이를 뒤집어서 덧셈을 수행해주는 것이 편합니다.

이러한 원리에 따라 다음과 같이 덧셈을 구현해보았습니다.

 

 

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

string sum(string a, string b) {
    int diff = max(a.length(), b.length()) - min(a.length(), b.length());

    if(a.length() < b.length())
        for(int i=0; i<diff; i++) a = "0" + a;
    else if(a.length() > b.length())
        for(int i=0; i<diff; i++) b = "0" + b;

    vector<int> c;
    for(int i=0; i<a.length(); i++) c.push_back(a[i] - '0' + b[i] - '0');

    reverse(c.begin(), c.end());

    for(int i=0; i<c.size(); i++) {
        if(c[i] < 10) continue;

        if(i < c.size()-1) c[i+1] += c[i]/10;
        else c.push_back(c[i]/10);

        c[i] %= 10;
    }

    reverse(c.begin(), c.end());

    string ret;

    int i = 0; while(c[i] == 0) i++;
    if(i >= c.size()) ret.push_back('0');

    while(i < c.size()) {
        ret.push_back(char(c[i] + '0'));
        i++;
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    string a, b; cin >> a >> b;

    cout << sum(a, b);
}

 

 

sum 함수에 기능이 모두 구현되어 있으므로 함수 부분만 복사해서 사용하시면 됩니다.

더 짧은 문자열의 앞에 자릿수가 같아지게끔 0을 붙여준 뒤, 두 문자열을 뒤집어 덧셈을 수행합니다.

올림은 구현하지 말고 벡터에 우선 그냥 더해서 저장해주고, 일차적인 연산이 끝난 뒤 올림을 수행해주면 됩니다.

반환 역시 문자열로 반환되도록 구현하였으므로 반환값을 그대로 출력해주면 됩니다.

 

 

백준 BOJ 4150 : 피보나치 수

1000자리 이하로 답이 나오는 피보나치 수를 출력하는 문제입니다.

1000자리라는 것은 python으로 해결하거나 덧셈을 직접 구현해주어야 한다는 의미이므로, 여기서는 위에서 구현한 큰 수 덧셈을 활용하여 문제를 풀이해보도록 하겠습니다.

 

 

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

string sum(string a, string b) {
    int diff = max(a.length(), b.length()) - min(a.length(), b.length());

    if(a.length() < b.length())
        for(int i=0; i<diff; i++) a = "0" + a;
    else if(a.length() > b.length())
        for(int i=0; i<diff; i++) b = "0" + b;

    vector<int> c;
    for(int i=0; i<a.length(); i++) c.push_back(a[i] - '0' + b[i] - '0');

    reverse(c.begin(), c.end());

    for(int i=0; i<c.size(); i++) {
        if(c[i] < 10) continue;

        if(i < c.size()-1) c[i+1] += c[i]/10;
        else c.push_back(c[i]/10);

        c[i] %= 10;
    }

    reverse(c.begin(), c.end());

    string ret;

    int i = 0; while(c[i] == 0) i++;
    if(i >= c.size()) ret.push_back('0');

    while(i < c.size()) {
        ret.push_back(char(c[i] + '0'));
        i++;
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<string> fibo;
    fibo.push_back("0");
    fibo.push_back("1");

    int N; cin >> N;
    for(int i=2; i<=N; i++) fibo.push_back(sum(fibo[i-1], fibo[i-2]));

    cout << fibo[N];
}

 

위와 같이 아까 구현한 sum 함수를 적어주고, main 함수에서는 vector<string>을 선언하여 fibo[0]과 fibo[1]은 push_back 해줍니다.

그리고 2 이상 f_n에 대해서는 이전 두 문자열을 더한 값을 push_back 해주어 N번째 문자열까지 계산할 수 있도록 해주면 됩니다.

 

 

추가 질문 : 큰 수 곱셈은 어떻게 구현할 수 있을까?

곱셈 식을 써보면서 원리를 생각해보면, 각 자릿수를 교차하여 곱해야한다는 성질을 확인할 수 있습니다.

이는 단순히 자릿수를 한 두번 더하여 넘겨주는 것이 아니라 각 자릿수에 대해 최대 O(N)번 더해주어야 하므로, 시간 초과를 피하기 위해서는 단순 덧셈으로는 불가능하며 FFT(고속 푸리에 변환)을 활용하여 구해주어야 합니다.

 

이에 대해서는 ↓ 아래의 포스트(FFT)에 정리가 되어있습니다. (BOJ 22289 큰 수 곱셈 (3) 문제의 풀이를 참고해주세요.)

BOJ 1067 이동, BOJ 22289 큰 수 곱셈 (3) (고속 푸리에 변환, FFT)

---

+ 추가

참고로 "큰 수 덧셈" 문제에 대한 숏코딩 풀이를 보면 다음과 같은 알고리즘도 있으니 참고하시면 좋을 것 같습니다. (rhdqor213님의 풀이입니다.)