백준 15829번 - Hasing 문제 C++

📍 백준 15829번 - Hasing 문제  C++

 

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

 

 

🧩 문제요약

문자를 입력받아 hasing 구현하기 

• r = 31
• m = 1234567891

 

👍 이 문제에서 배울점

이 문제는 점수가 small 50점 large 50점으로 나눠져 있다. 

small은 가볍게 풀어도 점수가 나오지만 large를 만족하기 위해서는 자료형을 고민해야한다. 

 

✅ C++의 자료형

자료형		크기	비트 수	값의 표현범위
정수형	char	1byte	8	-128 ~ +127 (8bit = 2^8 = 256가지)
	short	2byte	16	- 32,768 ~ + 32,767 (16bit = 2^16 = 65,536가지)
	int	4byte	32	-2,147,483,648 ~ +2,147,483,647 (32bit = 2^32가지)
	long	4/8byte	32/64	-2,147,483,648 ~ +2,147,483,647 (32bit = 2^32가지)
	long long	8byte	64	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
실수형	float	4byte	32	±1.2 × 10⁻³⁸ ~ ±3.4 × 10³⁸
	double	8byte	64	±2.3 × 10⁻³⁰⁸ ~ ±1.7 × 10³⁰⁸
	long double	8/16byte	64~128	±3.4 × 10⁻⁴⁹³² ~ ±1.1 × 10⁴⁹³² (플랫폼 의존)

cf) long 타입은 플랫폼 의존적이라 window(4byte) / linux(8byte)에 따라 다름. 

long double도 비슷함 window(8byte) / linux(16byte)에 따라 다름. 

 

✔ 요약하면 ✔ 

• int, float는 가장 기본 자료형
• long long과 double은 큰 범위와 정밀도 필요할 때 사용
• unsigned는 양수만 저장 가능, 더 넓은 양의 범위
• 실수형은 정확한 계산보다 근사 계산에 적합

 

small 조건과 같이 1<=L<=5 이면 int에서 해결이 되지만 large와 같이 1<=L<=50이 되면 hash의 계산값이 커지면서 자료형에 따라 값의 제한이 생기게 된다. 때문에 이 문제에서는 자료형을 잘 선택하는 것이 중요하다. 

 

 

✅ 모듈러 연산 법칙

hash의 값이 자료형의 범위를 넘어가는것을 방지하기 위해 m(mod)로 나머지를 계산한다. 

이를 모듈러 연산이라고 하는데, 모듈러 연산은 오버플로우를 방지하고 해시값이 항상 일정하게 나올 수 있도록 한다. 

 

모듈러 연산은 모듈러 연산 법칙을 따른다. 

이 연산을 구현하면 아래와 같다. 

hash = (hash + value * power) % M;
power = (power * r) % M;

 

이렇게 되는 이유는 모듈러 곱셈 법칙을 따르기 때문이다. 

(a⋅b)%M=((a%M)⋅(b%M))%M

 

 

✔ 모듈러 연산 법칙 요약표 

연산종류	공식	설명
덧셈	(a+b)%m = ((a%m)+(b%m))%m	결과를 항상 m보다 작게 유지
뺄셈	(a-b)%m = ((a%m)-(b%m)+m)%m	음수 방지를 위해 +m 후 %m
곱셉	(a⋅b)%M=((a%M)⋅(b%M))%M	큰 수 곱셈도 안전하게 처리
거듭제곱	(ab)%m → 빠른 거듭제곱 사용	반복 곱셈 + 중간중간 % m 필수

 

 

이제 위의 것들을 고려해서 코드를 구현하면된다. 

문제의 글이 길어서 처음에는 완전 식겁했는데, 막상 코드의 내용은 정말 별로 안된다. 

문제를 풀때 자료형에 익숙지가 않아서 해결하는데 생각보다 오래 걸렸다. 

알고리즘은 최적하 하기 위해서는 자료형과도 이제 많이 친해질 필요가 있다. 

 

🧾내가 구현한 코드 

#include <stdio.h>
using namespace std;

const int r = 31;
const int mod = 1234567891;

int main(){
    int L; 
    long long hash=0, power=1;
    char str;
    scanf("%d", &L);
    
    for(int i = 0; i<L; i++){
        scanf(" %c",&str);
        hash = (hash+(str - 96)*power) % mod ;
        power = (power*r)%mod;
    }
    printf("%lld\n", hash%mod);
}