백준_15829_Hashing

 

문제가 굉장히 깁니다.

 

 

해시 함수)

해시 함수란, 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수입니다.

자료구조에서도 사용되고, 암호용으로 사용되기도 하죠.

 

이 문제에서는 알파벳(a~z) 에 1~26까지 순서대로 고유 번호를 부여하여 해시 값을 계산합니다.

 

하지만, 이렇게만 하면 비둘기 집의 원리* 에 의해 중복되는 해시 값을 가질 수 있습니다.

(문자열은 다르지만 구성하는 알파벳이 같다면 해시 값이 동일하게 나옵니다.)

 

따라서, 충돌(중복)이 최대한 적게 일어나게 하기 위해 각 항에도 고유 번호(항의 번호에 해당되는 만큼 특정 숫자를 거듭제곱해 곱해주기)를 부여합니다.

최종적으로 이 함수가 문제에서 말하는 해시 함수입니다.

이 함수는 자주 쓰인다고 하니 꼭 기억해두는게 좋을 것 같습니다.

이 문제에서는 r=31, M=1234567891 로 둘 다 소수입니다.

 

 

*비둘기 집 원리 : n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말합니다.

 

 

풀이)

이 문제에서는 각 항마다 31의 거듭제곱을 곱해줘야 하기 때문에 오버플로우 현상을 조심해야 합니다.

오버플로우 현상을 해결하는 것이 주 목적이기 때문에 small 과 large로 50점씩 점수가 나뉘어져 있는 것을 확인할 수 있습니다.

 

오버플로우 문제를 해결하지 않을 시 50점을 넘길 수 없습니다.

 

 

어떻게 오버플로우가 일어나지 않도록 방지할 수 있을까요?

아래의 모듈러의 성질을 이용한다면 쉽게 해결할 수 있습니다.

 

1. { 2 + (2^2) + (2^3) + (2^4) + (2^5) + (2^6) + (2^7) } Mod3 = 2 

2. { (2 Mod3) + (2^2 Mod3) + (2^3 Mod3) + (2^4 Mod3) + (2^5 Mod3) + (2^6 Mod3) + (2^7 Mod3) } Mod3 =2

 

보시다시피, 1번과 2번의 결과값이 같습니다.

 

2번은 1번의 각 항마다 모듈러 연산을 한번씩 더 해준 식입니다.

각 항마다 모듈러 연산을 해주었기 때문에, 각 항의 숫자 크기가 작아지고, 오버플로우 현상을 방지할 수 있습니다.

 

아래는 이해하기 쉽도록 간단히 적은 오버플로우를 방지하는 해시값 계산 반복문입니다.

해시값 = 0;
고유값 = 1;

for(int i =0 ; i < 문자열의 길이; i++)
{
    해시값 = 해시값 + (a[i] * 고유값)Mod M
    고유값 = (고유값 * 31)Mod M
    해시값 = 해시값 Mod M
}

 

각 항마다 모듈러 연산을 하고,

31의 거듭제곱이 범위를 넘어서지 않도록 모듈러 연산을 해주고,

마지막으로 모듈러 연산의 결과의 합인 해시 값에 모듈러 연산을 해주면

오버플로우가 일어나지 않는 작은 수로도 해시 값을 계산할 수 있습니다.

 

 

전체 코드)

#include <stdio.h>

int main(void)
{
    int L = 0;
    scanf("%d", &L);

    char word[L];
    scanf("%s", word);

    int alphabet_num[L];               // 입력받은 문자열의 알파벳의 고유번호 저장할 배열
    int M = 1234567891;                // moduler
    unsigned long long hash_key = 0;   // 해시값을 저장할 변수
    unsigned long long Unique_num = 1; // 31의 거듭제곱 변수
    for (int i = 0; i < L; i++)
    {
        alphabet_num[i] = word[i] - 96; // 아스키 코드를 이용하여 알파벳을 숫자로 변환

        hash_key = hash_key + (alphabet_num[i] * Unique_num) % M;
        Unique_num = (Unique_num * 31) % M;
        hash_key %= M;
    }
    printf("%llu\n", hash_key);

    return 0;
}

 

문자열을 입력받아서 숫자로 변환한 값을 넣을 배열을 하나 만들었습니다.

그 후 해시값을 계산하는 반복문을 작성하였습니다.

 

오버플로우가 일어나지 않도록 모듈러의 성질을 생각해 볼 수 있는 문제였습니다.