[JAVA] BigInteger 사용법: 하노이탑 문제

안녕하세요! 오늘은  BigInteger 를 사용하는 방법에 대해 이야기해보기위해 하노이탑의 문제를 예시로 들려고 합니다. 특히, BigInteger 를 사용할 때 주의해야 할 점들과, 입력값이 매우 큰 경우(예: 100)에 대한 처리 방법에 대해 살펴보겠습니다.

 

https://www.acmicpc.net/problem/1914

1914번: 하노이 탑

 

BigInteger 사용의 핵심 이유

input : 100
output : 1267650600228229401496703205375

자바에서 int나 long과 같은 기본 숫자 형식으로는 이러한 큰 숫자를 표현할 수 없습니다. 이 경우 BigInteger 클래스를 사용하여 큰 숫자를 처리할 수 있습니다. BigInteger는 아주 큰 정수를 저장하고 연산할 수 있는 클래스로, 기본 숫자 형식의 범위를 초과하는 큰 수를 다룰 때 유용합니다.

 

코드 비교

기존 코드:

public static int countHanoi(int n) {
    if (n==1) {
        return 1;
    } else {
        return 2*countHanoi(n-1)+1;
    }
}

int 나 long으로 출력하더라도 Input 70도 출력하지 못하고 뻗어버립니다.

 

수정된 코드:

public static BigInteger countHanoi(BigInteger n) {
    if (n.equals(BigInteger.ONE)) {
        return BigInteger.ONE;
    } else {
        return countHanoi(n.subtract(BigInteger.ONE)).multiply(BigInteger.valueOf(2)).add(BigInteger.ONE);
    }
}

수정된 코드에서는 모든 연산을 BigInteger 클래스의 메서드를 사용하여 수행합니다. 이는 BigInteger의 값에 대한 정확한 연산을 보장합니다.

이 코드는 BigInteger와 본 숫자 연산( \-, \==) 을 혼용하여 사용하고 있습니다. 하지만 BigInteger는 기본 숫자 형식과 다르게 작동하므로, 빨간줄이 뜨며 에러를 출력합니다.

 

BigInteger사용의 중요성

BigInteger는 .equals() , .subtract() , .multiply() , .add() 등의 메서드를 사용하여 값을 비교하고 연산합니다. 이 메서드들은 BigInteger 객체에 대한 연산을 정확하고 안전하게 수행하기 위해 필요합니다.

BigInteger의 메서드 설명

1. .equals()

• 용도: 두 BigInteger 객체의 값이 같은지 비교합니다.
• 특징: == 연산자와 달리, .equals() 메서드는 두 객체의 참조가 아니라 값을 비교합니다. 따라서, 값이 같은 두 BigInteger 객체가 메모리상 다른 위치에 있더라도 true를 반환합니다.
• 예시: n.equals(BigInteger.ONE)은 n이 1과 같은 값인지 확인합니다.

2. .subtract()

• 용도: 한 BigInteger 객체에서 다른 하나를 빼는 데 사용합니다.
• 특징: 기본 자료형에서 사용하는 - 연산자 대신 subtract() 메서드를 사용합니다. 이는 BigInteger의 크기가 기본 자료형의 범위를 넘어설 수 있기 때문입니다.
• 예시: n.subtract(BigInteger.ONE)은 n에서 1을 뺀 결과를 반환합니다.

3. .multiply()

• 용도: 두 BigInteger 객체를 곱하는 데 사용합니다.
• 특징: 기본 자료형에서 사용하는 * 연산자 대신 multiply() 메서드를 사용합니다. BigInteger 객체 간의 곱셈을 정확히 수행하기 위해 필요합니다.
• 예시: countHanoi(n.subtract(BigInteger.ONE)).multiply(BigInteger.valueOf(2))는 n-1에 대한 하노이 탑의 이동 횟수를 계산한 후, 그 결과에 2를 곱합니다.

4. .add()

• 용도: 두 BigInteger 객체를 더하는 데 사용합니다.
• 특징: 기본 자료형에서 사용하는 + 연산자 대신 add() 메서드를 사용합니다. 이 메서드는 BigInteger 객체 간의 정확한 덧셈을 보장합니다.
• 예시: .add(BigInteger.ONE)은 BigInteger 객체에 1을 더합니다.

5. .divide()

• 용도: 두 BigInteger 객체의 나눗셈을 수행합니다.
• 특징: BigInteger는 기본 자료형과 달리, 나눗셈을 위해 .divide() 메서드를 사용합니다. 이 메서드는 정수 나눗셈을 수행하며, 결과는 나눗셈의 몫만을 포함합니다. BigInteger의 크기에 제한이 없으며, 정확한 나눗셈 연산을 보장합니다.
• 예시: a.divide(b)는 BigInteger 객체 a를 b로 나누고, 그 결과를 반환합니다. 50 / 3 = 16

 

결론

BigInteger 클래스는 매우 큰 정수를 정확하게 처리하기 위한 메서드들을 제공합니다. 기본 자료형의 연산자(==, -, *, +)를 사용할 수 없기 때문에, BigInteger의 메서드들은 이러한 연산을 대신합니다. 이 메서드들은 BigInteger 객체의 크기에 제한이 없으며, 정확하고 안전한 연산을 보장합니다. 따라서, 큰 숫자를 다루는 알고리즘에서 BigInteger 사용은 매우 중요합니다. 감사합니다!