[Algorithm][Big Integer]큰수 표현하기

추상적 자료형(Abstract data type)과 자료구조(Data structure)는 엄밀히 말하면 다르다.

가령 스택의 경우는 추상적 자료형이다. 그 이유는 리스트(List)는 정의만 존재하고 구현은 사용자 마음이다.

그러나 만약 누군가가 연결리스트(Linked List), 혹은 배열리스트(Array List, Vector)를 말한다면 그건 자료구조인 셈이다.

그러나 이런 구분이 애매한 녀석들도 존재하기는 한다.

스택(Stack)같은 녀석이 그 정체인데 스택은 추상적 자료형으로 분류되는게 맞으나 사실상 자료구조라고도 볼 수 있다.

왜냐하면 스택을 구현하는 방식이 배열과 연결리스트 두가지가 존재하긴 하지만 사실상 무조건 배열을 쓰는게 이득이기 때문이다.

그래서 필자의 포스팅에서는 추상적 자료형과 자료구조를 엄밀히 구분하지 않고 모두 자료구조라 논하겠다.

참고:

이 사이트의 예제 문제는 백준 사이트(https://www.acmicpc.net/)를 참조합니다.

예제:

백준 큰 수 A+B(10757)

백준 조합(2407)

언어들의 경우 전부 큰 수를 표현하는데 지장이 있다.

그 이유는 당연하게도 수는 무한대지만 메모리 양은 무한하지 않기 때문이다.

보통의 경우 short는 2바이트, int는 4바이트이며 long형은 8바이트이다.

타입이 존재하는 메이저 언어별로 양을 보자면 아래와 같다.

64비트 intel아키텍쳐 기준

C - int,long:4바이트 long long:8바이트

C++ - int,long:4바이트 long long:8바이트

java - int:4바이트 long:8바이트

C# - int:4바이트 long:8바이트

보통 우리는 계산을 할때 int로 하다가 수틀리면 long형(C나 C++은 long long형)을 사용한다.

특히 C나 C++은 아래와같이 정의를 해서 사용한다.

#define ll long long

솔직히 long long을 다 적기 너무 귀찮기 때문이다. 그리고 long은 4바이트이다.. 짜증난다.

문제는 이 long long범위마저 넘어갈 경우이다.

long long의 표현범위가 넓기 떄문에 방심하기 쉽지만 사실 작정하고 넘기려면 얼마든지 넘길 수 있다.

간단한 예로 팩토리얼, 피보나치, 조합의 갯수 등등의 계산할 때는 매우 쉽게 넘길 수 있다.

이 때 우리는 큰 수를 임의로 만들어서 사용해야한다.

사실 이 방법은 매우 귀찮고 짜증나는 일이지만 어쩔수 없다.

사실 이부분은 그렇게 까지 핫하지 않다. 특히 최근들어 더 그렇다.

왜냐하면 Python은 Big Integer를 내부적으로 제공하기 때문이다.

따라서 요즘 알고리즘에서는 Big Integer를 다루는 내용을 잘 내지는 않는다.

파이썬만 반사이익을 보기 때문이다.

그렇지만 다루는 방법을 알고는 있어야한다. 혹시 모르기 때문이며 사실 만들기는 그리 어렵지 않다.

생각하는 루틴은 딱 한가지이다.

우리가 몇자리의 큰 수를 표현할까이다.

자동화 해서 무한대로 증가하게도 할 수 있지만 사실 그렇게 까지는 필요하지 않다.

특히 알고리즘 문제를 푼다면 더더욱 이런일은 불필요하다. 시간만 낭비하기 때문이다.

그러면 먼저 int형이 몇자릴 표시할수 있는지 부터 알아야한다.

int는 21억까지 표시가 가능하다. 그러므로 10자리지만 10자리를 전부 표시하는건 아니므로 사실상 9자리라고 생각하면된다.

long은 922경까지 표시가 가능하다. 이는 19자리 이지만 당연히 19자리를 모두 표시하진 못하므로 사실상 18자리라고 생각하면된다.

즉 여러분이 새로만든 Big Integer의 경우 18자리 이상이 되야하는 것이다.

보통의 목표는 36자리를 목표로한다.

여러분이 생각해야할걸 정리해보자면

1. 8바이트 정수형을 사용한다.

2. 단위는 18자리라고 생각하고 쓴다.

3. 모든 경우를 만족하는 BigInteger를 만드려면 비용과 시간이 걸린다. 원하는 목표까지만 만든다.

여기서 3번이 중요하다. BigInteger는 생각보다 짜증나는 경우가 있는데 바로 여러 경우를 만들어야한다는 것이다.

Big Integer의 4칙연산도 다 따로 만들어야하며 특히 곱셈의 경우 Big Integer의 범위도 넘어가는게 일도 아니다.

보통 Big Integer의 덧셈만 다루긴하지만 생각해볼일이긴하다.

또한 Big Integer와 8바이트 정수형(long혹은 long long)의 계산도 지원할지 생각해 봐야한다.

그러니 필요한것 까지만 재빠르게 만들자. 보통 Big Integer끼리의 덧셈만 만들면되긴하다.

만드는 예제는 C언어로 보여주도록 하겠다.

쉽게 만들려면 객체로 만드는 것이 좋다.

객체를 만드는 방법은 C의 경우 struct, C++이상의 언어는 class, js의 경우 prototype등이 있지만

여기서는 C를 쓸것이기에 struct기준으로 언급하겠다.

#include <stdio.h>
#include <math.h>

#define ll long long
#define CIPHER_CNT 18
static const ll CIPHER = pow(10, CIPHER_CNT);

일단 중요한건 자를 자릿수를 정하는 것이다.

보통의 경우 18자리를 자른다.

typedef struct _tagBigInteger {
    ll high;
    ll low;
} BI;

그 다음 struct를 정의하는데 하위 18자리와 상위 18자리를 정의한다.

계산시 하위는 하위끼리 계산하고 상위는 상위끼리 계산한다.

BI ll_to_bi(ll li) {
    return {0, li};
}

BI bi_add_bi(BI a, BI b) {
    ll tlow = a.low % CIPHER + b.low % CIPHER;
    ll thigh = 0;
    if (tlow % CIPHER != a.low + b.low) {
        thigh = a.low / CIPHER + b.low / CIPHER;
    }
    thigh += a.high + b.high;
    return {thigh, tlow};
}

그 다음 long long을 Big Integer로 바꿔주는 루틴을 만든다.

경우에 따라서는 str_to_bi를 만들어야 하는 경우도 있는데 받는 숫자 자체가 long long을 초과하는 일이 있다.

이런 경우가 바로 백준 10757번 문제이다.

이런 경우에는 문자열로 바로 받아서 그걸 분해해서 Big Integer로 만들어야한다.

그리고 Big Integer끼리의 더하는 함수인 bi_add_bi를 만든다.

이제 큰수를 더할수 있다.

main의 예시를 보자.

int main() {
    ll ta;
    ll tb;
    BI A;
    BI B;
    BI result;
    scanf("%lld %lld", &ta, &tb);
    A = ll_to_bi(ta);
    B = ll_to_bi(tb);
    result = bi_add_bi(A, B);
    printf("%lld%018lld\n", result.high, result.low);
    return 0;
}

값은 무조건 longlong형만 받는다고 가정한다. 즉 long long형 범위 내의 숫자라고 가정한다.

위의 예제는 A+B를 출력하는 예제이다.

먼저 long long형으로 A와 B를 받는다. 그 다음 이를 Big Integer로 변환해서 더해준다.

근데 출력할때 굉장히 중요한게 0의 자릿수이다.

왜냐하면 BigInteger의 low값이 18자리가 아닐수도 있다는 것이다.

가령 000000000000000001일수도 있다.

이 경우 그냥 출력하면 1만 나오게된다.

따라서 0의 갯수를 포메팅해줘야한다.

이걸 자동화 하고 싶다면 함수로 만들면된다.

보통 알고리즘을 풀때는 시간이 없으므로 위와 같은 형태로 출력하게된다.

이러한 큰 수를 다루는 문제로 유명한 문제는 백준의 큰 수 A+B(10757)이다.

이미 받아 들이는 수부터 long long형을 초월하는 이 미친 문제는 받는 숫자를 문자로 받고 Big Integer로 바꿔줘야한다.

또 다른 문제로는 조합(2407)이다.

파스칼의 삼각형을 이용해서 조합을 구하는 이 문제 역시 무지막지하게 커져서 8바이트 정수를 초과하게된다.