Weekly Java: Java에서 100자리 이상의 수를 계산하는 방법

백준 10757 큰 수 A+B를 풀어보면서 익혀보자

Sigrid Jin

25 min readJun 11, 2022

상기 문제의 경우, long 데이터 타입을 사용할 수 없다.
int 형의 경우 -2^31에서 2^31−1 범위의 정수만을 표현할 수 있다. 이보다 조금 더 큰 정수를 담을 수 있는long 형은 (2^64)-1 의 범위까지 표현할 수 있는데, 이 문제의 경우 입력 범위가 최대 10^10000 이므로 범위를 초과한다.

접근법 1. 클래스를 활용하지 않고, 직접 덧셈을 활용하여 계산 알고리즘을 구현해보자.

먼저, 직접 덧셈의 기본 방식을 활용하여 직접 100자리 이상의 수를 계산하는 과정을 구현해보자. 덧셈은 각 자릿값을 뒤에서부터 채워야 한다. 이는 우리가 덧셈을 배울 때 직관적으로 알 수 있는 대목이다.
우리는 가장 낮은 자리의 수부터 덧셈을 해야 하고, 자릿수의 값이 10이 넘어가면 다음 자릿값에 +1을 해서 올림해야 한다. 배열의 측면에서는, 앞 인덱스에서부터 1의 자릿수를 채워나가야 한다.
배열의 인덱스에서 배열 A와 배열 B의 현재 인덱스 값을 더했을 때 결과값이 10이 넘어가는 경우라면 어떻게 해야 할까? A를 기준으로, 배열의 현재 인덱스 값에, 배열 A의 현재 인덱스와 배열 B의 현재 인덱스 값을 더한 결과값을, 10으로 나눈 나머지 값을 구한 후 이를 저장해야 한다. 10이 넘었을 때는 올림이 발생했다는 의미이므로 다음 자리수에 +1을 해주어야 한다.
A가 3783이고, B가 495일 때 덧셈을 직접 구현하는 방식을 이용하여 문제를 풀이하면 다음과 같다.

소스 코드

String strA = input();
String strB = input();

int max_length = max(strA.length(), strB.length());
int[] A = new int[max_length + 1]; // 마지막 자릿수를 고려하여 +1
int[] B = new int[max_length + 1];

// A를 초기화한다
for (int i = A.length - 1; int idx = 0; i >= 0; i--, idx++) {
  A[idx] = strA.charAt(i); // i는 뒤에서부터, idx는 앞으로부터 저장. 따라서 맨 뒤 문자를 역순으로 저장
}

// B를 초기화한다
for (int i = B.length - 1; int idx = 0; i >= 0; i--, idx++) {
  B[idx] = strB.charAt(i);
}

// 덧셈
for (int i = 0; i < max_length; i++) {
  int value = A[i] + B[i];
  A[i] = value % 10; // 더한 값의 10으로 나눈 나머지가 자릿값이 됨
  A[i + 1] = A[i + 1] + (value / 10); // 더한 값의 10으로 나눈 몫이 올림값이 됨
}

// A배열 역순 출력
// 가장 높은 자리수가 0이 될 수도 있기 때문에 0이 아닐 경우에만 출력
if (A[max_length] != 0) {
  print(A[max_length]);
}

for (int i = max_length - 1; i >= 0; i--) {
  print(A[i]);
}

최종 풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
  public static void main(String[] args) throws IOException {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    
    String str_A = st.nextToken();
    String str_B = st.nextToken();
    
    int max_length = Math.max(str_A.length(), str_B.length());
    
    
    int[] A = new int[max_length + 1];
    int[] B = new int[max_length + 1];
     
    for (int i = str_A.length() - 1, idx = 0; i >= 0; i--, idx++) {
      A[idx] = str_A.charAt(i) - '0';
    }
    
    
    for (int i = str_B.length() - 1, idx = 0; i >= 0; i--, idx++) {
      B[idx] = str_B.charAt(i) - '0';
    }
    
    
    for(int i = 0; i < max_length; i++) {
      int value = A[i] + B[i];
      A[i] = value % 10;
      A[i + 1] += (value / 10);
    }
    
    StringBuilder sb = new StringBuilder();
    if(A[max_length] != 0) {
      sb.append(A[max_length]);
    }
    
    for(int i = max_length - 1; i >= 0; i--) {
      sb.append(A[i]);
    }
    System.out.println(sb);
  }
}

접근법 2. BigInteger 클래스를 이용해보자.

같은 문제를 BigInteger 클래스를 활용하면 하기와 같이 풀이할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.math.BigInteger;
 
public class Main {
  public static void main(String[] args) throws IOException {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    
    BigInteger A = new BigInteger(st.nextToken());
    BigInteger B = new BigInteger(st.nextToken());
    
    A = A.add(B);
    
    System.out.println(A.toString());
  }
}

BigInteger란 무엇인가?

그러면 BigInteger 가 무엇인지 알아보도록 하자. 먼저, BigInteger 는 java.math 패키지 내부에 구현되어 있는 클래스이다.
Javadoc 커멘트에 따르면, 해당 클래스는 불변하는 정밀한 임의의 정수이다. BigInteger 는 byte[] 나 string 그리고 numBits 를 통해 생성할 수 있다. 예를 들어, 다음과 같이 생성할 수 있다.

// 16진법
BigInteger bigIntWithRadix = new BigInteger("64", 16);

// 정수
BigInteger bigIntWithValue = BigInteger.valueOf(100);

// 문자열
BigInteger bigIntWithString = new BigInteger("100");

사칙연산도 당연히 지원하는데, add / subtract / mutiply / divide 함수를 통해 덧셈과 뺄셈, 곱셈과 나눗셈 연산을 수행할 수 있다. 예를 들면 다음과 같이 두 정수를 입력없이 더하고 출력하는 프로그램의 예시를 살펴보자.

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String args[]) {
        BigInteger a = new BigInteger("9223372036854775807");
        BigInteger b = new BigInteger("9223372036854775808");
        BigInteger sum = a.add(b);
        System.out.println(sum.toString());
    }
}

기본적으로 Scanner는 nextBigInteger 를 지원하므로 Scanner를 이용하면 두 수를 입력받아 새로운 값을 계산하는 프로그램을 작성할 수 있다. 또한, 0, 1, 10 과 같은 값도 static 필드를 이용하여 표현할 수 있다. 아래는 피보나치 수를 구해 배열에 저장하고 출력하는 예제이다.

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        BigInteger[] f = new BigInteger[100];
        f[0] = BigInteger.ZERO;
        f[1] = BigInteger.ONE;
        for (int i=2; i < f.length; i++) {
            f[i] = f[i-1].add(f[i-2]);
        }
        for (int i=0; i < f.length; i++) {
            System.out.println(String.format("f[%d] = %s", i, f[i].toString()));
        }
    }
}

add의 내부 구현 살펴보기

앞서 언급했듯이 BigInteger 는 불변하는 정밀한 임의의 정수이다. 따라서 사칙연산 함수를 수행할 경우, 원래의 인스턴스를 수정하지 않고 새로운 인스턴스를 생성한다. 불변한 객체에 사칙연산 함수를 수행한다는 것은 기존 인스턴스의 상태를 바꾸는 것이 아니고, 새로운 인스턴스를 생성하여 해당 인스턴스와 변수를 링크하는 것을 의미한다.

Integer i = new Integer(10);//State 1
i = new Integer(20);//State 2 but does not update state 1

아래 코드는 BigInteger 에서 add 메소드를 수행하는 소스 코드이다. 아래 코드를 읽어보면 BigInteger 는 부호를 따로 저장하고 배열에는 값 자체만을 저장한다. 따라서 부호의 변수인 signum 의 값이 음수인 경우 2의 보수법에 맞게 값인 mag 의 실제 값을 변환한다. 서로 값이 같고 부호만 다른 두 BigInteger 의 경우 mag 는 같고 signum 이 다르다.

final int signum; // 부호. 1(양수), 0, -1 (음수) 세 가지 경우의 수 중 하나이다.
final int[] mag; // 값 (magnitude)

public BigInteger(int signum, byte[] magnitude) {
        this.mag = stripLeadingZeroBytes(magnitude);

        if (signum < -1 || signum > 1)
            throw(new NumberFormatException("Invalid signum value"));

        if (this.mag.length==0) {
            this.signum = 0;
        } else {
            if (signum == 0)
                throw(new NumberFormatException("signum-magnitude mismatch"));
            this.signum = signum;
        }
}

public BigInteger add(BigInteger val) {
    if (val.signum == 0)
        return this;
    if (signum == 0)
        return val;
    if (val.signum == signum)
        return new BigInteger(add(mag, val.mag), signum);

    int cmp = compareMagnitude(val);
    if (cmp == 0)
        return ZERO;
    int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
                       : subtract(val.mag, mag));
    resultMag = trustedStripLeadingZeroInts(resultMag);
    // 새로운 Object를 생성한다
    return new BigInteger(resultMag, cmp == signum ? 1 : -1);//<====
}

final int compareMagnitude(BigInteger val) {
        int[] m1 = mag;
        int len1 = m1.length;
        int[] m2 = val.mag;
        int len2 = m2.length;
        if (len1 < len2)
            return -1;
        if (len1 > len2)
            return 1;
        for (int i = 0; i < len1; i++) {
            int a = m1[i];
            int b = m2[i];
            if (a != b)
                return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
        }
        return 0;
 }

add의 내부 구현 살펴보기

앞서 언급했듯이 BigInteger 는 불변하는 정밀한 임의의 정수이다. 따라서 사칙연산 함수를 수행할 경우, 원래의 인스턴스를 수정하지 않고 새로운 인스턴스를 생성한다. 불변한 객체에 사칙연산 함수를 수행한다는 것은 기존 인스턴스의 상태를 바꾸는 것이 아니고, 새로운 인스턴스를 생성하여 해당 인스턴스와 변수를 링크하는 것을 의미한다.

Integer i = new Integer(10);//State 1
i = new Integer(20);//State 2 but does not update state 1

아래 코드는 BigInteger 에서 add 메소드를 수행하는 소스 코드이다. 아래 코드를 읽어보면 BigInteger 는 부호를 따로 저장하고 배열에는 값 자체만을 저장한다. 따라서 부호의 변수인 signum 의 값이 음수인 경우 2의 보수법에 맞게 값인 mag 의 실제 값을 변환한다. 서로 값이 같고 부호만 다른 두 BigInteger 의 경우 mag 는 같고 signum 이 다르다.

final int signum; // 부호. 1(양수), 0, -1 (음수) 세 가지 경우의 수 중 하나이다.
final int[] mag; // 값 (magnitude)

public BigInteger(int signum, byte[] magnitude) {
        this.mag = stripLeadingZeroBytes(magnitude);

        if (signum < -1 || signum > 1)
            throw(new NumberFormatException("Invalid signum value"));

        if (this.mag.length==0) {
            this.signum = 0;
        } else {
            if (signum == 0)
                throw(new NumberFormatException("signum-magnitude mismatch"));
            this.signum = signum;
        }
}

public BigInteger add(BigInteger val) {
    if (val.signum == 0)
        return this;
    if (signum == 0)
        return val;
    if (val.signum == signum)
        return new BigInteger(add(mag, val.mag), signum);

    int cmp = compareMagnitude(val);
    if (cmp == 0)
        return ZERO;
    int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
                       : subtract(val.mag, mag));
    resultMag = trustedStripLeadingZeroInts(resultMag);
    // 새로운 Object를 생성한다
    return new BigInteger(resultMag, cmp == signum ? 1 : -1);//<====
}

final int compareMagnitude(BigInteger val) {
        int[] m1 = mag;
        int len1 = m1.length;
        int[] m2 = val.mag;
        int len2 = m2.length;
        if (len1 < len2)
            return -1;
        if (len1 > len2)
            return 1;
        for (int i = 0; i < len1; i++) {
            int a = m1[i];
            int b = m2[i];
            if (a != b)
                return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
        }
        return 0;
 }

대체로 연산하려는 큰 수를 String 형태로 저장한 이후, 9자리 (10진수)로 문자열을 잘라 Integer 데이터 타입으로 parse하여 배열에 저장한다.

int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1; // BASE_DECIMAL_DIGITS = 9
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;

// 만들고, loop한다
int[] digits = new int[bigLen];
for(int i = 0; i < bigLen; i++) {

String block =
        decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
                          firstSome +   i  *BASE_DECIMAL_DIGITS);
  // ...
  digits[i] = Integer.parseInt(block);
}

자릿수가 같은 경우를 살펴보자. 값을 더하기 위해서는 같은 자리 수의 digits를 더하고 값이 10보다 크면 다음 digits로 +1 값에 대한 올림을 수행한다. 이는 앞서 보았던 덧셈의 논리와 같다. overflow 되는 +1의 올림은 왼쪽 digit로 넘어간다. 참고로, 하기 예제에서는 다음 digits로 이동하기 위해서는 오른쪽에서 왼쪽으로 이동해야 한다. (We go from right to left, so we can carry any overflows to the next digit.)

int[] result = new int[this.digits.length];
int carry = 0;
for(int i = this.digits.length-1; i > 0; i--) {
    int digSum = carry + this.digits[i] + that.digits[i];
    result[i] = digSum % BASE;
    carry = digSum / BASE;
}
if(carry > 0) {
    int[] temp = new int[result.length + 1];
    System.arraycopy(result, 0, temp, 1, result.length);
    temp[0] = carry;
    result = temp;
}
return new DecimalBigInt(result);

자릿수가 다른 경우를 살펴보자. 이러한 경우 overflow가 있을 때 재귀 호출을 통하여 다음 digits에 올림을 수행한다.

/**
 * calculates the sum of this and that.
 */
public DecimalBigInt plus(DecimalBigInt that) {
    int[] result = new int[Math.max(this.digits.length,
                                    that.digits.length)+ 1];

    addDigits(result, result.length-1, this.digits);
    addDigits(result, result.length-1, that.digits);

    // cut of leading zero, if any
    if(result[0] == 0) {
        result = Arrays.copyOfRange(result, 1, result.length);
    }
    return new DecimalBigInt(result);
}

/**
 * adds all the digits from the addend array to the result array.
 */
private void addDigits(int[] result, int resultIndex,
                       int... addend)
{
    int addendIndex = addend.length - 1;
    while(addendIndex >= 0) {
        addDigit(result, resultIndex,
                 addend[addendIndex]);
        addendIndex--;
        resultIndex--;
    }
}

/**
 * adds one digit from the addend to the corresponding digit
 * of the result.
 * If there is carry, it is recursively added to the next digit
 * of the result.
 */
private void addDigit(int[] result, int resultIndex,
                      int addendDigit)
{
    int sum = result[resultIndex] + addendDigit;
    result[resultIndex] = sum % BASE;
    int carry = sum / BASE;
    if(carry > 0) {
        addDigit(result, resultIndex - 1, carry);
    }
}

비트 연산과 BigInteger

우리가 앞서 언급했듯이 BigInteger 클래스는 불변 객체이다. 불변 객체는 인스턴스의 내부 값을 수정할 수 없는 클래스를 의미한다. 값이 다르다면 반드시 독립적인 객체로 만들어야 한다. 백만 비트 짜리의 BigInteger에서 비트 하나를 수정하기 위해서는 새로운 인스턴스를 생성해야 한다. 객체를 새로 생성하는 단계를 고민하면, long 형에 비해 성능이 좋을 수 없다. 따라서 비트 단위로 연산하는 것이 성능 상 유리하다고 생각한다.
비트 연산에는 비트 길이를 확인하는 bitLength , 비트의 값이 0인지 1인지 확인하는 testBit , 그리고 쉬프트 연산인 shiftLeft 와 shiftRight 이 있다.

BigInteger value = BigInteger.TEN;

value.bitCount() // 4

// 2진수 변환
value.toString(2); // 1010

value.shiftLeft(1).toString(2) // 10100
  
value.shiftRight(1).toString(2) // 101

기타 메소드

나머지 구하기, 값 비교하기, 그리고 최대-최소 비교하기도 별도의 메소드로 구현되어 있다.

BigInteger value = new BigInteger("3");

// 1
value.remainder(BigInteger.TWO);BigInteger value = BigInteger.TEN;

// 1
value.compareTo(BigInteger.TWO);

// 0
value.compareTo(BigInteger.TEN);

// -1
BigInteger.TWO.compareTo(value);

// 10
value.max(BigInteger.TWO);

// 2 
value.min(BigInteger.TWO);

BigInteger vs int & long

직접 덧셈의 원칙으로 구현한 것 (제출번호: 44420131) 과, BigInteger 를 활용한 것 (제출번호: 44420192) 중에 어느 것이 속도가 더 빠른지 비교해보자.
직접 덧셈의 원칙으로 구현한 것이 BigInteger 클래스보다 더 빠르다는 사실을 알 수 있다. 왜 그런가? Computation 시간 보다는 BigInteger가 String을 parse 하는 과정이 시간 더 걸린다고 한다.
또한, BigInteger 를 사용할 경우 불변한 새로운 copy를 만들기 때문에 메모리 사용이 비효율적일 수밖에 없다.
따라서 다음의 스택오버플로우 답변에 따르면 Bitwise 를 통해 직접 구현하거나 long 을 사용하고 대신 index가 넘어가는 경우를 확인하라고 조언한다. 특히 사칙연산이 잦을 경우 Bitwise 를 사용하여 직접 구현하는 것이 현명해 보인다.

You could define your own Java interface for this, initially using a Java BitSet to implement that interface.
If you run into performance issues, or if you require the use of long later on, you may always provide a different implementation (e.g. one that uses caching or similar improvements) without changing the rest of the code. Think well about the interface you require, and choose a long index just to be sure, you can always check if it is out of bounds in the implementation later on (or simply return "no access" initially) for anything index > Integer.MAX_VALUE.
Using BigInteger is not such a good idea, as the class was not written for that particular purpose, and the only way of changing it is to create a fully new copy. It is efficient regarding memory use; it uses an array consisting 64 bit longs internally (at the moment, this could of course change). 출처

추후 학습할 거리

직접 BigInteger 클래스를 나만의 것으로 구현하는 것도 의미가 있어 보인다. 추후 글에는 다음 링크와 이 링크를 참고하여 구현하는 시간을 가져보도록 하겠다.

Weekly Java: Java에서 100자리 이상의 수를 계산하는 방법

백준 10757 큰 수 A+B를 풀어보면서 익혀보자

접근법 1. 클래스를 활용하지 않고, 직접 덧셈을 활용하여 계산 알고리즘을 구현해보자.

소스 코드

최종 풀이 코드

접근법 2. BigInteger 클래스를 이용해보자.

BigInteger란 무엇인가?

add의 내부 구현 살펴보기

add의 내부 구현 살펴보기

비트 연산과 BigInteger

기타 메소드

BigInteger vs int & long

추후 학습할 거리

Reference

Written by Sigrid Jin

No responses yet