일반적으로 프로그래밍에서 정수형 타입(int, long long 등)으로 표현할 수 없는 매우 큰 수를 다룰 때 고정밀도 연산이 필요합니다.

고정밀도 연산의 핵심은 큰 수를 배열이나 문자열 등을 사용하여 각 자릿수를 개별적으로 저장하고, 이를 바탕으로 덧셈, 뺄셈, 곱셈, 나눗셈 등의 산술 연산을 직접 시뮬레이션하는 것입니다. 이는 마치 사람이 연필과 종이를 사용하여 세로셈을 하는 것과 유사합니다.

고정밀도 덧셈

고정밀도 덧셈은 각 자릿수를 배열의 한 요소에 저장하는 방식으로 구현됩니다. 일반적으로 배열의 0번 인덱스를 일의 자리로, 1번 인덱스를 십의 자리로 사용하는 것이 편리합니다. 최상위 자리를 배열의 첫 요소로 사용할 경우, 올림(carry) 처리가 복잡해지고 배열 범위를 벗어나는 문제가 발생할 수 있습니다.

두 고정밀도 수의 덧셈

이 연산은 비교적 직관적입니다. 각 자릿수를 더하고 올림을 처리하는 과정을 반복합니다.

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

int main() {
    std::vector<int> result(1000, 0); // 결과를 저장할 배열 (최대 1000자리 가정)
    std::string num_str;
    int max_len = 0;

    for (int i = 0; i < 2; ++i) {
        std::cin >> num_str;
        int current_len = num_str.length();
        max_len = std::max(max_len, current_len);
        for (int j = 0; j < current_len; ++j) {
            // 문자열의 숫자를 역순으로 배열에 저장 (일의 자리부터)
            result[current_len - 1 - j] += (num_str[j] - '0');
        }
    }

    // 올림 처리
    for (int i = 0; i < max_len; ++i) {
        if (result[i] >= 10) {
            result[i + 1] += result[i] / 10;
            result[i] %= 10;
            if (i + 1 == max_len && result[i + 1] > 0) {
                max_len++; // 최고 자리에 올림이 발생하면 자릿수 증가
            }
        }
    }

    // 결과를 역순으로 출력
    while (max_len > 0 && result[max_len] == 0) {
        max_len--; // 맨 앞의 0 제거
    }
    for (int i = max_len; i >= 0; --i) {
        std::cout << result[i];
    }
    std::cout << std::endl;

    return 0;
}

고정밀도 수와 일반 정수형 덧셈

일반 정수형을 배열로 변환하여 고정밀도 덧셈과 동일한 방식으로 처리할 수 있습니다.

고정밀도 뺄셈

고정밀도 뺄셈은 덧셈과 달리 올림(carry) 대신 빌림(borrow)을 처리해야 합니다. 즉, 뺄셈 결과가 음수가 될 경우, 다음 자릿수에서 '1'을 빌려와야 합니다. 음수 결과가 나올 수 있으므로, 두 수의 크기를 먼저 비교하여 큰 수에서 작은 수를 빼고 필요한 경우 결과에 음수 부호를 붙입니다.

두 고정밀도 수의 뺄셈

#include <cstdio>
#include <cstring>
#include <algorithm> // std::swap 사용

const int MAXN = 10100;
int result[MAXN];
int num1_digits[MAXN], num2_digits[MAXN];
char s1[MAXN], s2[MAXN];
int len1, len2;

// 두 정수를 바꾸는 함수
void swap_ints(int& a, int& b) {
    a = a ^ b;
    b = b ^ a;
    a = a ^ b;
}

int main() {
    scanf("%s %s", s1, s2);
    len1 = strlen(s1);
    len2 = strlen(s2);

    // 문자열을 역순으로 배열에 저장 (일의 자리부터)
    for (int i = 0; i < len1; ++i) num1_digits[i] = s1[len1 - 1 - i] - '0';
    for (int i = 0; i < len2; ++i) num2_digits[i] = s2[len2 - 1 - i] - '0';

    int max_len = std::max(len1, len2);
    bool is_negative = false;

    // 두 수의 크기 비교
    for (int i = max_len - 1; i >= 0; --i) {
        if (num1_digits[i] > num2_digits[i]) break;
        if (num1_digits[i] < num2_digits[i]) {
            is_negative = true;
            break;
        }
        if (i == 0) { // 두 수가 같은 경우
            printf("0");
            return 0;
        }
    }

    if (is_negative) {
        printf("-");
        // num2가 더 크므로, num1과 num2를 swap하여 큰 수 - 작은 수 연산을 수행
        for (int i = 0; i < max_len; ++i) swap_ints(num1_digits[i], num2_digits[i]);
    }

    // 뺄셈 수행
    for (int i = 0; i < max_len; ++i) {
        result[i] = num1_digits[i] - num2_digits[i];
        if (result[i] < 0) {
            num1_digits[i + 1]--; // 다음 자릿수에서 빌림
            result[i] += 10;
        }
    }

    // 결과에서 맨 앞의 0 제거
    while (max_len > 0 && result[max_len] == 0) {
        max_len--;
    }

    // 결과 출력
    if (max_len < 0) printf("0"); // 결과가 0인 경우
    else {
        for (int i = max_len; i >= 0; --i) {
            printf("%d", result[i]);
        }
    }
    printf("\n");

    return 0;
}

고정밀도 수와 일반 정수형 뺄셈

덧셈과 마찬가지로, 일반 정수형을 배열로 변환하여 고정밀도 뺄셈 방식을 적용합니다.

고정밀도 곱셈

고정밀도 곱셈의 핵심은, 한 수의 i번째 자릿수와 다른 수의 j번째 자릿수를 곱한 결과가 최종 결과의 (i+j)번째 자릿수에 더해진다는 것입니다. 이는 세로셈 곱셈 원리를 그대로 따른 결과입니다.

두 고정밀도 수의 곱셈

#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>

const int MAXN = 20010; // 곱셈 결과는 최대 두 수 길이의 합만큼 될 수 있음
int num1_digits[MAXN], num2_digits[MAXN];
int result[MAXN]; // 곱셈 결과를 저장할 배열
char temp_str[MAXN];

int main() {
    scanf("%s", temp_str);
    int len1 = strlen(temp_str);
    for (int i = 0; i < len1; ++i) num1_digits[i] = temp_str[len1 - 1 - i] - '0'; // 일의 자리부터 저장

    scanf("%s", temp_str);
    int len2 = strlen(temp_str);
    for (int i = 0; i < len2; ++i) num2_digits[i] = temp_str[len2 - 1 - i] - '0'; // 일의 자리부터 저장

    // 곱셈 수행
    for (int i = 0; i < len1; ++i) {
        for (int j = 0; j < len2; ++j) {
            result[i + j] += num1_digits[i] * num2_digits[j];
            // 올림 처리
            result[i + j + 1] += result[i + j] / 10;
            result[i + j] %= 10;
        }
    }

    int final_len = len1 + len2 - 1; // 예상되는 최대 길이
    // 결과에서 맨 앞의 0 제거
    while (final_len >= 0 && result[final_len] == 0) {
        final_len--;
    }

    if (final_len == -1) { // 결과가 0인 경우
        printf("0\n");
    } else {
        for (int i = final_len; i >= 0; --i) {
            printf("%d", result[i]);
        }
        printf("\n");
    }

    return 0;
}

고정밀도 수와 일반 정수형 곱셈

일반 정수형을 배열로 변환하여 고정밀도 곱셈과 동일한 로직으로 처리할 수 있습니다.

고정밀도 나눗셈

두 고정밀도 수의 나눗셈

이 연산은 구현이 복잡하여 일반적으로 "구현 보류" 상태입니다.

고정밀도 수와 일반 정수형 나눗셈

고정밀도 피제수를 앞에서부터 순차적으로 일반 정수형 변수로 변환하며, 일반 정수형 제수로 나눗셈을 수행합니다. 이 과정에서 몫과 나머지를 구하며, 몫은 결과로 출력하고 나머지는 다음 자릿수를 이어붙여 다시 피제수로 사용합니다.

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

int main() {
    std::string dividend_str; // 고정밀도 피제수
    long long divisor;        // 일반 정수형 제수
    std::cin >> dividend_str >> divisor;

    long long current_num = 0; // 현재 처리 중인 부분 피제수
    long long remainder = 0;   // 나머지
    bool leading_zero = true;  // 결과의 선행 0을 처리하기 위한 플래그

    // 나눗셈 수행
    for (char digit : dividend_str) {
        current_num = remainder * 10 + (digit - '0');
        long long quotient_digit = current_num / divisor;
        remainder = current_num % divisor;

        if (quotient_digit > 0 || !leading_zero) {
            std::cout << quotient_digit;
            leading_zero = false;
        }
    }

    // 피제수가 제수보다 작거나, 나눗셈 결과가 0인 경우
    if (leading_zero) {
        std::cout << "0";
    }
    std::cout << std::endl;

    return 0;
}