문제

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

풀이

해싱 카테고리 문제 중 가장 낮은 난이도의 문제다.

문제에 적혀있는 식을 그대로 코드로 변환하여 구현하기만 하면된다.

그래서 처음에 아래 코드를 작성하여 제출했다.

1차시도

import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		final int r = 31, m = 1234567891;
		int res = 0,l = Integer.parseInt(scan.nextLine());
		String str = scan.nextLine();
		for(int i=0; i<l; i+=1){
		    int character = str.charAt(i) - 'a' + 1;
		    res += character*(int)(Math.pow(r,i))%m;
		}
		System.out.println(res);
	}
}

단순 반복문을 활용하여 시그마 합의 결과를 출력하도록 코드를 구현하였다.

50점이 나왔다. 문자열 길이 L이 1≤L≤5 사이로 입력되었을때는 제대로 동작하나, 1≤L≤50의 상대적으로 큰값이 들어왔을때는 정상적인 값이 출력되지 않았다는 것이다.

원인을 찾던중 백준 질문게시판에서 아래와 같은 내용의 답변을 발견했다.

자바 기준 Math.pow() 매소드는 부동소수점 연산을 하여 결과를 출력하기 때문에 매개변수 값이 클수록 부정확한 결과를 받을수 있다.

부동 소수점 연산?

일단 먼저 부동 소수점 연산에 대해서 이해하기 위해서는 고정 소수점과 부동 소수점에 대한 개념의 이해가 필요하다.

먼저 10진수 소수는 2진수로 변환할수 있는데 예를 들어 0.5를 2진수 소수로 표현하면 0.5는 \(2^{-1}\) 이므로 0.1이 된다. 또 이와 마찬가지로 0.25도 \(2^{-2}\) 이므로 0.01이 된다. 그럼 만약에 0.6을 소수로 표현하면 어떻게 될까?

0.10011001100110011001100110011001100110011001100110011….

끝도 없이 이어지게 된다. 여기서 고정소수점이냐 부동소수점이냐에 따라서 소수의 표현방식이 달라진다.

• 고정 소수점

정수, 소수를 표현할 수 있는 비트의 갯수에 제한이 있는 방법이다. 예를들어 위와 같은 소수를 변수에 넣는다고 할때 만약 해당 변수의 자료형에서 실수의 표현 비트가 15bit가 제한이 있다고 하면 0.6은 0.100110011001100 까지만 저장이 될것이다. 이런경우 당연히 뒤부분이 잘려버렸으니 이 변수에 있는 수는 별다른 보정작업이 없다면 정확히 0.6을 가리키지 못하게 될것이다. 그렇다고 실수를 나타내는데 사용하는 비트의 양을 늘리기에는 한정된 공간에서 정수를 나타내는 비트마저 줄어 어떻게 해도 정확한 수의 표현이 어려워진다. 이러한 제약으로 인해 활용하는 방식이 부동 소수점이다.

• 부동 소수점

부동 소수점 표현은 실수 부분을 더 많이 보존하기 위해서 정수부분을 그대로 저장하는 것이 아닌 최대한 단순화 시킨다. 아래와 같은 방법으로 단순화를 시킨다. (IEEE 754 표준 기준)

1. 먼저 부호비트를 설정(양수 = 0 , 음수 = 1)
2. 정수부가 0이 아니라면 소수점을 좌측으로 이동시켜 1.xxx 형태가 나오게 만든다. 0이라면 우측으로 이동시켜 1.xxx 형태가 나오게 만든다.
3. 소수점을 옮기기전 수에서 2를 몇번 곱해야 해당수가 나오는지 계산(소수점을 옮긴수에서 원래수를 나눴을때 값)
4. 두 수의 차이에 대한 값은 \(2^n\)형태로 표현되어지며 n의 값을 지수 비트 부에 입력
5. 1.xxx 형태로 바꾼 소수의 나머지 xxx부분을 가수 비트 부분에 되는 만큼 최대한 입력

IEEE 754 부동 소수점 표준

[1비트] [ 8비트 ] [ 23비트 ]
부호비트 지수비트 가수 비트

이 방법으로 고정 소수점에 비해서는 조금 더 정확한 실수를 저장할 수 있다. 하지만 부동소수점도 마찬가지로 정확한 소수점을 표현하지는 못한다.

부동 소수점 연산의 문제점

실수도 정확하게 표현이 되지 않는데 계산 했을때도 정확한 답이 나오지 않을 수 있다는건 너무 당연해 보이지만 정수를 부동 소수점 연산을 했을때 어떤문제가 발생하는 걸까?

예를들어 정수 37과 131을 위에서 설명한 부동소수점 변환 방법을 활용해 표현하면 아래와 같다.

[0][1111010][00101] ⇒ 37
[양수][2^5][정수부를 제외한 나머지 실수 부분]

[0][1111000][0000011] ⇒ 131
[양수][2^7][정수부를 제외한 나머지 실수 부분]

두 수를 부동 소수점 연산을 이용해 곱하면

[0][1110011][001011101111]
[양수][2^12][정수부를 제외한 나머지 실수 부분]

위와 같이 나오고 다시 정수로 전환하면 4847이라는 값이 정상적으로 나온다. 여기까지는 문제가 없다.

문제는 연산결과가 가수비트를 초과하는 값이 나오면 그때부터 문제가 되기 시작한다.

예를들어 480,730과 269,602를 곱한다고 해보자

480,730 = 1.110101010111011010 _ 2^18 = [0][1101101][110101010111011010]
269,602 = 1.000001110100100010 _ 2^18 = [0][1101101][000001110100100010]

원래 나와야되는 제대로 된 결과는 다음과 같다.

129,605,769,460 = 1.111000101101000110110001100011110100 * 2^36

그러나 결과를 보면 가수비트가 총 36개가 들어가야되는데 IEEE 754 표준에 따르면 가수비트는 23비트까지만 들어갈수 있다.

이로인해 가수비트 32비트중 23비트까지만 입력이 되어지고 나머지 13비트는 소멸되어진다. 이로인해 실제로 저장되는 값은 다음과 같다.

15,821,016 = 1.11100010110100011011000 * 2^23 = [0][1101000][11100010110100011011000]

따라서 원래 \(480730\times 269602 = 129605769460\) 이여야 하지만 정작 부동소수점 연산을 이용한다면 \(480730\times 269602 = 15821016\) 가 되어버린다는 것이다.

따라서 자바 내부 매소드 중 Math.pow() 함수는 부동 소수점 연산을 진행하고 값이 커질 수록 부정확한 값을 출력할 수 있기때문에 1≤L≤50 일때 정상적으로 동작하지 못한것이다.

따라서 이를 해결하기 위해서는 Math.pow()를 대체할만한 부동 소수점 연산을 하지 않는 다른 매소드를 활용하거나 직접 만들어야한다.

그래서 나는 반복문을 이용해 일일히 곱셈을 진행해 Math.pow() 매소드를 대체하는 매소드를 만들었고 수정하여 제출한 코드는 아래와 같다.

import java.util.Scanner;

public class Main
{
	//Math.pow()함수를 대체
    static long power(int r, int x) {
        long res = 1;
        for(int i=0; i<x; i+=1) res *= r;
        return res;
    }
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		final int r = 31, m = 1234567891;
		int l = Integer.parseInt(scan.nextLine());
		// int 대신 long 자료형 활용
		long res = 0;
		String str = scan.nextLine();
		for(int i=0; i<l; i+=1){
		    int character = str.charAt(i) - 'a' + 1;
		    res += character*power(r,i)%m;
		}
		System.out.println(res);
	}
}

대체 매소드를 만들고 반복문을 이용해 시그마 합을 계산하면서 누적되는 값이 int 범위를 초과할 것 같아 더 큰 정수 자료형인 long 을 활용하였다.

자료형 비교

int ⇒ -2,147,483,648 ~ 2,147,483,647
long ⇒ -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

2차시도 결과

여전히 큰수를 넣었을때 문제가 발생하는 것 같다.

long보다 더 큰 자료형이 자바에 혹시나 있는지 찾아봤다.

있었다.

BigInteger 자료형

별도로 import문으로 로드해줘야 사용할 수 있는 자료형이다.(import java.math.BigInteger)

이 자료형은 다른 정수 자료형과 다르게 변수 초기화도 별도의 BigInteger 객체를 생성하여 진행하고,

사칙연산 또한 별도의 매소드를 활용하며, 매소드로 넘겨지는 사칙연산할 수는 모두 String 형태로 넘겨진다. 아마 String 형태로 넘겨받아 내부 매소드에서 별도의 변환 / 분할 작업을 통하여 연산을 진행하는 것으로 보인다.

BigInteger의 범위는 다른 자료형과 달리 70바이트까지의 수를 받을수 있어서 사실상 대부분의 큰수를 다루는데 큰 지장이 없어 보인다.

이 자료형을 활용하기 위해 원래 long 자료형을 활용한 누적변수를 BigInteger로 대체하였다.

코드는 아래와 같다.

import java.util.Scanner;
import java.math.BigInteger;

public class Main
{
    static BigInteger power(int r, int x) {
        BigInteger res = new BigInteger("1");
        for(int i=0; i<x; i+=1) res = res.multiply(new BigInteger(Integer.toString(r)));
        return res;
    }
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		final int r = 31, m = 1234567891;
		int l = Integer.parseInt(scan.nextLine());
		BigInteger res = new BigInteger("0");
		String str = scan.nextLine();
		for(int i=0; i<l; i+=1){
		    BigInteger character = new BigInteger(Long.toString(str.charAt(i) - 'a' + 1));
		    res = res.add(character.multiply(power(r,i)));
		}
		res = res.remainder(new BigInteger(Integer.toString(m)));
		System.out.println(res);
	}
}

최종 시도

드디어 정답이다.

알수 있는것

1. 소수는 2진수의 형태로 저장될때 자료형이 클수록 더 많은 비트를 담을 수 있어 더 근접한 형태로 저장할 수 있으나, 0.5, 0.75처럼 비트의 길이가 딱 떨어지지 않는다면 정확하게 표현할수 없다.
2. 1번의 이유로 인해 부정확한 소수가 발생하며 이를 연산에 이용하면서 결국 부적절한 결과값을 반환하게 된다.
3. 같은 자료형 이더라도 소수를 저장할때 고정 소수점 방식 보다는 부동 소수점 방식을 활용했을때 더 많은 가수비트를 저장할 수 있어 더 정확하게 값을 저장할 수 있다.
4. 큰 정수의 연산을 부동소수점 연산을 통해 진행할경우 가수비트를 초과한 길이의 결과가 발생하여 결과의 일부비트가 손실된 상태로 반환됨으로써 정확한 연산을 하기 어렵다. 큰수의 연산은 왠만해서는 부동소수점 연산에 활용하지 않는 것이 좋다.
5. 여기에서는 서술하지 못하였으나, 여러 해싱 알고리즘중 하나를 경험하고 배우게 되었음.