c++에서 long long보다 큰 정수를 다루는 방법

오성민
March 23, 2024
홈으로 돌아가기

백준에서 하노이 탑 문제를 풀다가 분명히 알고리즘은 맞는데 정답이 틀리게 나와서 반례를 확인해보았다. 

        입력1: 30
        출력1: 1073741823

        입력2: 31
        출력2: 2147483647

        입력3: 32
        출력3: -1

변수의 자료형이 int여서 너무 큰 출력값을 저장하지 못하고 오버플로우가 발생한 모습이다.

int형의 범위 : -231 ~ (231 - 1) (-2,147,483,648 ~ 2,147,483,647)

이를 해결하기 위해 long long 자료형으로 바꾸어 실행해본다.

        입력1: 32
        출력1: 4294967295

        입력2: 62
        출력2: 4611686018427387903

        입력3: 63
        출력3: 9223372036854775807

        입력4: 64
        출력4: -1

역시나 오버플로우가 발생한다.

long long형의 범위 : -263 ~ (263 - 1) (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)

문제의 정답이 오직 양수이기 때문에, 더 큰 수를 담기 위해 unsigned long long을 사용했다. 

        입력1: 64
        출력1: 18446744073709551615

        입력2: 65
        출력2: 18446744073709551615

        입력3: 66
        출력3: 18446744073709551615

        입력4: 67
        출력4: 18446744073709551615
unsigned long long형의 범위 : 0 ~ 264 (0 ~ 18,446,744,073,709,551,615)

비상!!! 가장 큰 정수 자료형을 사용했음에도 오버플로우가 발생했다. 이 정도 큰 수는 정수 자료형으로 다룰 수 없다는 것을 깨닫고 다른 방법을 생각해 본다.

내가 생각한 방법은 수를 벡터에 담는 것이다. 예를 들어 정수 147,573,952,589,676,412,927를 표현하고 싶다면 다음과 같이 저장하는 것이다. 

vector<int> count =
  { 1, 4, 7, 5, 7, 3, 9, 5, 2, 5, 8, 9, 6, 7, 6, 4, 1, 2, 9, 2, 7 };

위의 방법을 사용하면, 벡터의 원소 개수는 메모리가 허용하는 한 무제한 늘어날 수 있기 때문에 아무리 큰 정수라도 모두 표현할 수 있다. 그러나 내가 풀던 문제에서는 입력이 1 늘어날 때마다 2를 곱하고 1을 더해야 하기 때문에 이 연산을 위한 별도의 코드를 작성하여야 한다. 

  //변경 전
  int count = 0;
  for(int i = 0; i < N; i++) {
    count = (count * 2) + 1;
  }
  cout<<count<<"\n";

  //변경 후
  vector<int> count = {0};
  for(int i = 0; i < N; i++) {
    mul2(count);
    plus1(count);
  }
  printCount(count);

mul2 함수의 동작은 다음과 같다.

void mul2(vector<int> &count) {
  int carry = 0;
  for(int digit = count.size() - 1; digit >= 0; digit--) {
    count[digit] = (count[digit] * 2) + carry;
    carry = 0;
    
    if(digit == 0 && count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      count.insert(count.begin(), 1);
    } else if(count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      carry = 1;
    }
  }
}

1. 맨 마지막 자리에서부터 2를 곱한다.

1-1. 만약 뒷자리에서 올림값(carry)이 존재했다면 이를 더해준다.

1-2. 올림값을 더한 뒤에는 올림값을 0으로 초기화해 준다.

2. 만약 2를 곱한 값이 10을 넘지 않는다면 다음 자릿수로 넘어가 반복한다.

3. 만약 2를 곱한 값이 10을 넘는다면 일의 자릿수만 취하고, 나머지 값은 다음 자릿수에 올림값으로 넘긴다.

4. 만약 맨 앞자리 수가 10이 넘어 더 이상 넘길 다음 자릿수가 없다면, 일의 자릿수만 취하고 올림값을 앞에 새 원소로 삽입한다.

예시를 통해 mul2 함수의 동작을 더 자세히 알아보자.

1. mul2( { 9, 8, 7, 2 } )
9872에 2를 곱하는 예시이다.

2. { 9, 8, 7, 4 }
맨 마지막 자리에 2를 곱한다. 값이 10을 넘지 않았으므로 다음 자리로 넘어간다.

3. { 9, 8, 14, 4 }
세 번째 자리에 2를 곱한다. 값이 10을 넘었다.

4. { 9, 8 (+ 1), 4, 4 }
일의 자릿수만 취하고, 나머지 값은 두 번째 자리에 올림값으로 넘겼다.

5. { 9, 16 (+ 1), 4, 4 }
두 번째 자리에 2를 곱한다.

6. { 9, 17, 4, 4 }
뒷자리에서 올라온 올림값을 더해준다. 값이 10을 넘었다.

7. { 9 (+ 1), 7, 4, 4 }
일의 자릿수만 취하고, 나머지 값은 첫 번째 자리에 올림값으로 넘겨준다.

8. { 19, 7, 4, 4 }
첫 번째 자리에 2를 곱하고 올림수를 더한다. 값이 10을 넘었고, 넘길 다음 자리가 없다.

9. { 1, 9, 7, 4, 4 }
일의 자릿수만 취하고, 올림값을 앞에 새 원소로 삽입한다.

답이 맞는지 확인해 보자. (9872 x 2 = 19744) 완벽하다! 이렇게 벡터로 표현된 정수에 2를 곱하는 함수를 구현했다. 다음은 비슷한 방법으로 구현한 plus1 함수이다. 직접 함수의 동작을 분석해 보자. 

void plus1(vector<int> &count) {
  int carry = 0;
  for(int digit = count.size() - 1; digit >= 0; digit--) {
    count[digit] = count[digit] + 1 + carry;
    carry = 0;
    
    if(digit == 0 && count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      count.insert(count.begin(), 1);
    } else if(count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      carry = 1;
    } else {
      break;
    }
  }
}

※ 힌트 : 곱하기는 모든 자리에 다 곱하여야 하지만, 더하기를 할 때는 마지막 자리에만 더하면 된다. 즉, 올림수가 발생하지 않으면 그대로 함수를 종료하면 된다.

plus1 함수의 동작을 직접 분석해 보았는가? 그렇다면 마지막으로 작동하는 전체 정답 코드를 보이겠다. 

#include <iostream>
#include <vector>
using namespace std;

void Hanoi(int n, int from, int drop, int to) {
  if(n == 1) {
    cout<<from<<" "<<to<<"\n";
    return;
  }
  
  Hanoi(n - 1, from, to, drop);
  cout<<from<<" "<<to<<"\n";
  Hanoi(n - 1, drop, from, to);
}

void mul2(vector<int> &count) {
  int carry = 0;
  for(int digit = count.size() - 1; digit >= 0; digit--) {
    count[digit] = (count[digit] * 2) + carry;
    carry = 0;
    
    if(digit == 0 && count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      count.insert(count.begin(), 1);
    } else if(count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      carry = 1;
    }
  }
}

void plus1(vector<int> &count) {
  int carry = 0;
  for(int digit = count.size() - 1; digit >= 0; digit--) {
    count[digit] = count[digit] + 1 + carry;
    carry = 0;
    
    if(digit == 0 && count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      count.insert(count.begin(), 1);
    } else if(count[digit] >= 10) {
      count[digit] = count[digit] % 10;
      carry = 1;
    } else {
      break;
    }
  }
}

void printCount(vector<int> &count) {
  for(auto num : count) {
    cout<<num;
  }
  cout<<"\n";
}

int main(void) {
  int N; cin>>N;
  
  vector<int> count = {0};
  for(int i = 0; i < N; i++) {
    mul2(count);
    plus1(count);
  }
  printCount(count);
  
  if(N <= 20) {
    Hanoi(N, 1, 2, 3);
  }
  return 0;
}

위와 같이 문제를 풀 수 있었다.

배울 수 있었던 점

더 생각해 볼 점