P-coding

이번 글에서는 백준 110번 문제를 통해 이항계수를 활용하고
최대 값을 넘어서는 순간을 다루는 방법을 알아보자.

문제 핵심

• 서쪽 ( N )
• 동쪽 ( M )
• N <= M
• 최대 한 개의 다리만 연결

풀이 과정

이 문제는 조합론으로 mCn이라고 할 수 있다.

다만 M의 최대값이 30일 때 factorial의 값은 다음과 같다.

• 1! = 1
• 2! = 2
• 3! = 6
• 4! = 24
• 5! = 120
• 6! = 720
• 7! = 5040
• 8! = 40,320
• 9! = 362,880
• 10! = 3,628,800
• 11! = 39,916,800
• 12! = 479,001,600
• 13! = 6,227,020,800
• 14! = 87,178,291,200
• 15! = 1,307,674,368,000
• 16! = 20,922,789,888,000
• 17! = 355,687,428,096,000
• 18! = 6,402,373,705,728,000
• 19! = 121,645,100,408,832,000
• 20! = 2,432,902,008,176,640,000
• 21! = 51,090,942,171,709,440,000
• 22! = 1,124,000,727,777,607,680,000
• 23! = 25,852,016,738,884,976,640,000
• 24! = 620,448,401,733,239,439,360,000
• 25! = 15,511,210,043,330,985,984,000,000
• 26! = 403,291,461,126,605,635,584,000,000
• 27! = 10,888,869,450,418,352,160,768,000,000
• 28! = 304,888,344,611,713,860,501,504,000,000
• 29! = 8,841,761,993,739,701,954,543,616,000,000
• 30! = 265,252,859,812,191,058,636,308,480,000,000

한계는 이미 초과했다.

이 때 우리는 각 프로그래밍언어에서 제공하는 클래스를 사용하면 된다.

Java에서는 BigInteger가 있다.

핵심 코드

이항 계수1 문제 처럼 나왔지만 이번에는 동쪽이 숫자가 항상 크다.

( 값을 받을 때 반대로 받았다. 헷갈리지 않게 N M으로 선언하는게 좋다. )

int T = Integer.parseInt(bufferedReader.readLine());
int N, K;
BigInteger result;

for (int i = 0; i < T; i++) {
    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    K = Integer.parseInt(stringTokenizer.nextToken());
    N = Integer.parseInt(stringTokenizer.nextToken());


    result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
    stringBuilder.append(result).append("\n");
}

이번 문제는 자료형의 최대값을 한참 넘어서기 때문에,
그 부분만 해결할 수 있다면 이전 이항계수 문제를 활용해 아주 쉽게 풀 수 있는 문제이다.

꼭 BigInteger같은 클래스를 사용하지 않더라도 비슷한 방식으로
직접 문자로 만들어서 처리하는 방법도 존재한다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

    public static BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();

        int T = Integer.parseInt(bufferedReader.readLine());
        int N, K;
        BigInteger result;

        for (int i = 0; i < T; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            K = Integer.parseInt(stringTokenizer.nextToken());
            N = Integer.parseInt(stringTokenizer.nextToken());


            result = factorial(N).divide(factorial(K).multiply(factorial(N - K)));
            stringBuilder.append(result).append("\n");
        }

        System.out.println(stringBuilder);
    }
}

자료형 변환시 주로 ParseInt가 권장된다.
하지만 valueOf 함수도 있는데 왜 저걸 권장할까?

ParseInt()

Java 라이브러리에서 ParseInt()는 다음과 같이 정의하고 있다.

public static int parseInt(String s) throws NumberFormatException {
    return parseInt(s,10);
}

기본 자료형( int )로 반환하며, 오버로딩(Overloading) 되어서 다시 재정의가 이루어진다.

다음은 오버로딩 ( Overloading ) 전체 코드이다. 문자열( s )를 진법( radix )을 통해 변환이 이루어진다.

public static int parseInt(String s, int radix)
            throws NumberFormatException
{
    /*
     * WARNING: This method may be invoked early during VM initialization
     * before IntegerCache is initialized. Care must be taken to not use
     * the valueOf method.
     */

    if (s == null) {
        throw new NumberFormatException("Cannot parse null string");
    }

    if (radix < Character.MIN_RADIX) {
        throw new NumberFormatException("radix " + radix +
                                        " less than Character.MIN_RADIX");
    }

    if (radix > Character.MAX_RADIX) {
        throw new NumberFormatException("radix " + radix +
                                        " greater than Character.MAX_RADIX");
    }

    boolean negative = false;
    int i = 0, len = s.length();
    int limit = -Integer.MAX_VALUE;

    if (len > 0) {
        char firstChar = s.charAt(0);
        if (firstChar < '0') { // Possible leading "+" or "-"
            if (firstChar == '-') {
                negative = true;
                limit = Integer.MIN_VALUE;
            } else if (firstChar != '+') {
                throw NumberFormatException.forInputString(s, radix);
            }

            if (len == 1) { // Cannot have lone "+" or "-"
                throw NumberFormatException.forInputString(s, radix);
            }
            i++;
        }
        int multmin = limit / radix;
        int result = 0;
        while (i < len) {
            // Accumulating negatively avoids surprises near MAX_VALUE
            int digit = Character.digit(s.charAt(i++), radix);
            if (digit < 0 || result < multmin) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result *= radix;
            if (result < limit + digit) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result -= digit;
        }
        return negative ? result : -result;
    } else {
        throw NumberFormatException.forInputString(s, radix);
    }
}

1. 초기 예외 검사

문자열(s)가 null이면 변환이 불가 함으로 NumberFormatException 예외 발생

if (s == null) {
    throw new NumberFormatException("Cannot parse null string");
}

radix(진법)이 2~36 진법 범위 내에서만 변환 가능함으로 Min, Max 값 범위 예외 처리

if (radix < Character.MIN_RADIX) {
    throw new NumberFormatException("radix " + radix +
                                    " less than Character.MIN_RADIX");
}
if (radix > Character.MAX_RADIX) {
    throw new NumberFormatException("radix " + radix +
                                    " greater than Character.MAX_RADIX");
}

2. 부호 판별 및 기본 설정

부호 +(43), -(45)은 0(48)보다 아래이기 때문에 부호를 찾고 '+'은 무시 나머지 경우에만 처리한다.

'-'인 경우 음수로 설정하고, limit를 int 자료형의 변환이기 때문에 Integer.MIN_VALUE 로 설정한다.

        if (firstChar < '0') { // Possible leading "+" or "-"
            if (firstChar == '-') {
                negative = true;
                limit = Integer.MIN_VALUE;
            } else if (firstChar != '+') {
                throw NumberFormatException.forInputString(s, radix);
            }

길이가 1이라면 앞 부호 하나만 있기 때문에 예외 처리

        if (len == 1) { // Cannot have lone "+" or "-"
            throw NumberFormatException.forInputString(s, radix);
        }

3. 숫자로 변환

먼저 자릿수를 가져오고, digit가 0보다 작거나 오버플로우가 나는지 체크한다.

사실 이 코드만 보고 이해하기는 어려울 수 있다. 성공과 실패의 두 가지 예시가 있다.

        int multmin = limit / radix;
        int result = 0;
        while (i < len) {
            // Accumulating negatively avoids surprises near MAX_VALUE
            int digit = Character.digit(s.charAt(i++), radix);
            if (digit < 0 || result < multmin) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result *= radix;
            if (result < limit + digit) {
                throw NumberFormatException.forInputString(s, radix);
            }
            result -= digit;
        }

ex) 성공한 연산 10진수 "2147483647"

 multmin = -2147483647 / 10 = -214748364

이 값을 통해 미리 오버플로우 발생을 예측한다.

마지막 결과에서 -2147483647을 부호판별 후 반환한다. -(-2147483647) = 2147483647

ex) 실패한 연산 10진수 "2147483648"

다음과 같은 결과로 ( result < limt + digit ) 조건이 참이 되어 예외가 발생하게 된다.

result = -2147483640
limit = -2147483647
digit = 8

limit + digit = -2147483647 + 8 = -2147483639

valueOf()

Java 라이브러리에서 valueOf()는 다음과 같이 정의하고 있다.

    public static Integer valueOf(String s) throws NumberFormatException {
        return Integer.valueOf(parseInt(s, 10));
    }

객체형으로 반환하고 있고, 여기서도 오버로딩( Overloading ) 했던 parseInt()가 보인다.

또 하나 valueOf 메서드도 오버로딩( Overloading ) 되었는데 다음과 같다.

1. 미리 생성된 값 IntegerCache.low(-128) ~ IntegerCache.high(127) 사이면 새 객체를 생성하지 않고 반환한다.

2. 그 값이 아니라면 새로 객체를 생성하여 반환한다.

( 미리 생성되는 값 범위는 JVM option에 따라 조정 가능 )

    @IntrinsicCandidate
    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

(추가) parseInt() 사용 예

예제)

System.out.println(Integer.parseInt("123", 10));   // 123
System.out.println(Integer.parseInt("-123", 10));  // -123
System.out.println(Integer.parseInt("101", 2));    // 5 (2진수 변환)
System.out.println(Integer.parseInt("7F", 16));    // 127 (16진수 변환)
System.out.println(Integer.parseInt("Z", 36));     // 35 (36진수에서 'Z'는 35)
System.out.println(Integer.parseInt("007", 8));    // 7 (8진수)

예외발생)

System.out.println(Integer.parseInt("abc", 10));  // 예외 발생 (숫자가 없음)
System.out.println(Integer.parseInt("12345", 2)); // 예외 발생 (2진수 범위 초과)
System.out.println(Integer.parseInt("", 10));     // 예외 발생 (빈 문자열)
System.out.println(Integer.parseInt(null, 10));   // 예외 발생 (null)

결국 valueOf() 메서드도 parseInt()를 사용하며
Integer를 사용하지 않고, 정수만을 반환받기 원한다면 parseInt() 메서드를 사용해야 한다.
Integer객체를 통해 불필요하게 메모리를 사용하게 된다.

Integer와 Int 같은 정수형을 나타내는 자료형으로 볼 수 있다.
하지만 이는 객체와 기본형으로 다르게 같지만서도 다르다.
이번에는 그 차이를 알아보자.

1. primitive type ( 기본형 )

• 값 자체를 스택 메모리에 직접 저장하는 Primitive 즉, 원시적인 자료형이다. 
• 별도의 정의가 필요없이 사용할 수 있으며 고정된 크기를 차지한다.
• 메소드를 사용할 수 없으며 값을 직접 저장하기 때문에 null 을 저장할 수 없습니다.

2. Wrapper Class ( 객체형 )

• 값은 힙 메모리에 객체에 저장되고, 스택 메모리는 그 객체를 가리키는 주소값을 저장한다.
• 참조형 데이터이기 때문에 추가적인 메모리가 소모된다.
• 기본 상태는 null로 초기화 된다.

3. 메모리 구조 예시 ( 정수 )

다음과 같은 코드를 적용할 때 그림과 같이 메모리에 할당된다.

int num = 10;
Integer num = Integer.valueOf(num);

차이점 요약

Wrapper Class는 제네릭 형태로 자주 사용되며,
특히 List<Integer> 와 같은 컬렉션 프레임워크에서 흔히 활용된다.
간단한 코드에서는 당연하게 사용하지만,
방대한 코드 작성 시에는 메모리나 성능, 기능적 요소를 고려해야 한다.
이러한 상황에 닥쳤을 때 비로소 이유를 고민하기보다, 미리 원리를 이해하고 사용하면 더 효율적일 것이다.