DS Certi (Pro) Linked List , Hash (실전 문제) - jjin-choi/study_note GitHub Wiki

§ Day 03 (Hash 실전 문제)

□ Hash table 초기화

  • hcnt = 0 뿐만 아니라 테이블 자체를 초기화 해주어야 함.

    • hcnt = 0;

    • 0 ~ size -1 까지 hash[i] = NULL;

    • 따라서 size 를 적당히 너무 크지 않게 잡아주어야 함.

    • 혹은 사용한 hash index 별도 배열에 기록 (ex. int useHashIdx[])

    • 사용한 index만 초기화

□ [L] MCS

  • 길이는 60,000 이하.

  • hash 문제가 나올 때에는 부수적인 이유로 나옴. 주된 것은 linked list 혹은 다른 것이고 indexing 이나 문자열 일 때 hash ...

  • 패턴찾기 문제가 hash 문제..

  • hash 문제 format

    • hash key 설정 . A C G T 각 자리 수에 몇 개가 있는지를 넣자. . ex) AGC : 1110 / GAG : 1020 . 이를 CODE 로 어떻게 변경할까 ? (진법 / 각 네 수의 합 - 겹치는 수가 너무 많아짐. / 각 네 수의 제곱의 합 - 마찬가지..) . 자리수가 의미있기 때문에 진법 !
      . 한 자리에 나올 수 있는 최대 숫자가 1000 이므로 (문제에서 주어진 길이 k 가 1000) k 를 1001 진법으로.. . 33 진법으로 해도 되긴 함. 충돌 처리를 잘 하면 되기 때문에
    • collision 처리 (chaining)
    • hash table size 설정 (chaining 시 data 수 ^ 2) . DATA 수는 6만개. 따라서 SIZE 는 2^16 = 65,XXX 정도 . MASK = SIZE - 1
    • hash function 설정 . hidx = CODE & MASK

  • 오답노트

    • probing 을 할 때에 return 이 없을때 hcnt[hidx] 에 할당해주고 cnt++ 에 주의.. !
#include <stdio.h>

typedef unsigned long long ull;
const int MAX_K = (1e3 + 1);
const int MAX_N = (6e5 + 5);
const int SIZE = 1 << 16;
const int MODE = SIZE - 1;

int N, K, hcnt, max = 0;
char str[MAX_N];
int cnt[4];

struct _hash {
	ull code;
	int cnt;
	_hash* next;
	_hash* alloc(ull _code, _hash *_next) {
		code = _code, next = _next;
		return this;
	}
} hbuff[MAX_N], *hash[SIZE]; // hash 는 SIZE 만큼 .. ! 

int hash_func(int mode) {
	ull CODE = 0;
	for (int i = 0; i < 4; i++)
		CODE = CODE * MAX_K + cnt[i];
	
	if (mode)	return CODE;
	else		return CODE & MODE;
}

_hash* probing() {
	int hidx = hash_func(0);
	int code = hash_func(1);

	for (_hash* p = hash[hidx]; p; p = p->next) 
		if (p->code == code) return p;

	return 0;
}

void update_cnt(char c, int flag) {
	if (c == 'A') cnt[0] += flag;
	if (c == 'C') cnt[1] += flag;
	if (c == 'G') cnt[2] += flag;
	if (c == 'T') cnt[3] += flag;
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d %s", &K, str);

	for (int i = 0; str[i]; i++) {
		update_cnt(str[i], 1);
		if (K <= i) update_cnt(str[i - K], -1);

		if (K - 1 <= i) {
			_hash *p = probing();

			if (!p) {
				int hidx = hash_func(0);
				int code = hash_func(1);
				hash[hidx] = hbuff[hcnt++].alloc(code, hash[hidx]);
				hash[hidx]->cnt++;
				if (max < hash[hidx]->cnt) max = hash[hidx]->cnt;
			}
			else {
				p->cnt++;
				if (max < p->cnt) max = p->cnt;
			}
		}
	}

	printf("%d\n", max);

	return 0;
}

□ [M] 바이러스

  • hash key

    • 길이 k인 숫자 배열

  • hash function

    • 배열 길이가 최대 1000 이고, CODE 가 실제 유효한 값은 아님.
    • djb2 : seed 5381, 33 진법
    • 편법.. : DATA 수에 비해 SIZE 가 충분할 경우에는 제곱의 합

  • hash table size

    • DATA 수 1000개, SIZE 2^12, MASK = SIZE -1

  • 오답노트

    • 1 프로그램에 한 번 더해진 것은 다시 더해지지 않도록 처리하기 !
#include <stdio.h>

typedef unsigned long long ull;
const int MAX = 1000 + 5;
const int SIZE = 1 << 16;
const int MODE = SIZE - 1;

int N, K, M, hcnt;
int first[MAX], in[MAX];

struct _hash {
	int base;
	int cnt = 0; // 같은 프로그램 내에서는 더하면 안됨... 
	_hash* next;
	_hash* alloc(int _base, _hash* _next) {
		base = _base, next = _next;
		return this;
	}
} hbuff[MAX], *hash[SIZE];

bool is_match(int base, int arr[]) {
	int l_check = 1, r_check = 1;
	for (int k = 0; k < K; k++) {
		if (first[base + k] != arr[k]) {
			l_check = 0; break;
		}
	}

	for (int k = 0; k < K; k++) {
		if (first[base + k] != arr[K - k - 1]) {
			r_check = 0; break;
		}
	}
	
	if (l_check || r_check) return true;
	return false;
}

int hash_func(int base) {
	ull CODE = (in[base] * in[base] + in[base - K + 1] * in[base - K + 1]);
	return CODE & MODE;
}

_hash* probing(int n, int base, int arr[]) {
	int hidx = hash_func(base);
	for (_hash* p = hash[hidx]; p; p = p->next) {
		if (is_match(p->base, arr)) 
			return p;
	}
	return 0;
}

void make_hash_table(int M) {
	for (int m = K - 1 ; m < M ; m++) {
		int hidx = hash_func(m);

		_hash *p = probing(0, m, first + m - K + 1);
		if (!p) {
			hash[hidx] = hbuff[hcnt++].alloc(m - K + 1, hash[hidx]);
			hash[hidx]->cnt++;
		}
	}
}

int check_virus(int n, int M) {
	int flag = 0;
	for (int m = K - 1; m < M ; m++) {
		int hidx = hash_func(m);
		_hash *p = probing(n, m, in + m - K + 1);
			
		if (p && p->cnt == n && flag != hidx) {
			p->cnt++;
			flag = hidx;
		}
	}
	
	return flag;
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &K);
	
	for (int n = 0; n < N; n++) {
		scanf("%d", &M);

		for (int m = 0; m < M; m++) {
			scanf("%d", in + m);
			if (n == 0) first[m] = in[m];
		}

		if (n == 0) make_hash_table(M);
		else
			if (!check_virus(n, M)) {
				printf("NO\n");
				return 0;
			}
	}

	printf("YES\n");
	return 0;
}

□ [N] ID 찾기

  • 오답노트
    • null 참조 시 Runtime Error:Segmentation fault 발생 !!
    • 문제 잘 읽기.. :) 특히 조건문 !!! 주의하기 (로그인한 ! 경우에만 로그아웃)
    • 음수가 나왔다는 건 뭔가 잘못된거다.. :)
#include <stdio.h>

const int MAX = (int)(5e5 + 5);
const int LEN = 15;
const int SIZE = 1 << 19;
const int MODE = SIZE - 1;

int N, cmd, hcnt, scnt, lcnt;

int strcmp(char*s, char*t) {
	while (*s && *s == *t)  ++s, ++t;
	return *s - *t;
}

void strcpy(char*dest, const char*src) {
	while ((*dest++ = *src++));
}

struct _hash {
	char id[LEN];
	int is_login; // 로그인 시 1
	int is_close; // 탈퇴 시 1
	_hash* next;
	_hash* alloc(char _id[LEN], _hash* _next) {
		strcpy(id, _id), next = _next;
		return this;
	}
} hbuff[MAX], *hash[SIZE], *p;

int hash_func(char KEY[LEN]) {
	int CODE = 0; 
	for (int i = 0; KEY[i]; i++)
		CODE = CODE * 37 + KEY[i];
	return CODE & MODE;
}

_hash* probing(char* id) {
	int hidx = hash_func(id);
	for (_hash* pp = hash[hidx]; pp; pp = pp->next)
		if (!strcmp(pp->id, id)) return pp;
	return 0;
}

int validate(char* id) {
	if (p && !(p->is_close)) return 1;
	return 0;
}

int activate(char* id) {
	if (validate(id))	return p->is_login;
	return 0;
}

int signup(char* id) {
	if (p && p->is_close) {
		p->is_close = 0;
		scnt++;
	}

	if (!p) { 
		int hidx = hash_func(id);
		hash[hidx] = hbuff[hcnt++].alloc(id, hash[hidx]);
		scnt++;
	}
	return scnt;
}

int close(char* id) {
	if (validate(id)) {
		p->is_close = 1; scnt--;
		if (p->is_login) { p->is_login = 0; lcnt--; }
	}
	return scnt;
}

int login(char* id) {
	if (validate(id) && !(p->is_login)) { p->is_login = 1; lcnt++; }
	return lcnt;
}

int logout(char* id) {
	if (validate(id) && p->is_login) { p->is_login = 0; lcnt--; }
	return lcnt;
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	
	for (int n = 0; n < N; n++) {
		char in[LEN];
		scanf("%d %s", &cmd, in);

		p = probing(in);

		if (cmd == 1) {
			int ret = validate(in);
			printf("%d\n", ret);
		}

		else if (cmd == 2) {
			int ret = activate(in);
			printf("%d\n", ret);
		}

		else if (cmd == 3) {
			int ret = signup(in);
			printf("%d\n", ret);
		}

		else if (cmd == 4) {
			int ret = close(in);
			printf("%d\n", ret);
		}

		else if (cmd == 5) {
			int ret = login(in);
			printf("%d\n", ret);
		}

		else if (cmd == 6) {
			int ret = logout(in);
			printf("%d\n", ret);
		}
	}

	return 0;
}

□ [O] 패턴 찾기

  • 오답노트

    • hash size : data 수가 1000 * 1000 이므로 그 이상.. 1 << 20
    • hash key : M * M 상태
    • hash function : . M * M 값을 2진법으로 표현하여 code 생성 . M * M 앞쪽 4*5 값을 2진법으로 표현하여 code 생성 (-> 0 ~ 1 << 20, 즉 code 값이 hash index)
    • 배열 값을 and 연산 으로 해서 필요한 부분만 골라내보기
    • 굳이 다 할 필요 없이 45만으로도 비교해도 충분.. (나올 수 있는 경우 (2^(45)) 의 수가 데이터 수 (1000 * 1000) 만큼 되기 때문에 이상적임)
    • B 배열 크기 설정 잘 하자. hash pointer p 가 이상한 값을 가리킴
    • 디버깅 시에는 ctrl + F10 을 !

  • 풀이

    • init() : 모든 A 의 시작점에서의 code 값을 계산해서 hash table 에 상태 저장
    • query() : B 의 code -> hidx 값을 계산해서 hash table[hidx] probing 통해 같은지 확인.
const int MAX = (int)(1e3 + 3);
const int MIN_R = 4;
const int MIN_C = 5;
const int SIZE = 1 << 20;
const int MODE = SIZE - 1;
int N, M, A[MAX][MAX], B[24][24], hcnt;

struct _hash {
	int r, c;
	_hash* next;
	_hash* alloc(int _r, int _c, _hash* _next) {
		r = _r, c = _c, next = _next;
		return this;
	}
} hbuff[MAX * MAX], *hash[SIZE];

int hash_func(int R, int C, int mode) {
	int ret = 0;
	for (int r = 0; r < MIN_R; r++) 
		for (int c = 0; c < MIN_C; c++) {
			if (mode == 'A') ret = (ret << 1) + A[r + R][c + C];
			if (mode == 'B') ret = (ret << 1) + B[r][c];
		}
			
	return ret & MODE;
}

void init(int n, int ap[][1000], int m) {
	::N = n, ::M = m;
	hcnt = 0;

	// initialize hash table 
	for (int i = 0; i < SIZE; i++) hash[i] = 0;
	
	// copy ap to A array 
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++) 
			A[r][c] = ap[r][c];
		
	// push pattern to hash table 
	for (int r = 0; r < N - M + 1; r++)
		for (int c = 0; c < N - M + 1; c++) {
			int hidx = hash_func(r, c, 'A');
			hash[hidx] = hbuff[hcnt++].alloc(r, c, hash[hidx]);
		}
}

bool compare_pattern(int R, int C) {

	for (int r = 0; r < M; r++) 
		for (int c = 0; c < M; c++) 
			if (A[r + R][c + C] != B[r][c]) return 0;
			
	return 1;
}

int query(int bp[][20]) {
	
	// copy bp to B array 
	for (int r = 0; r < M; r++)
		for (int c = 0; c < M; c++)
			B[r][c] = bp[r][c];
	
	// find pattern 
	int hidx = hash_func(0, 0, 'B');
	for (_hash* p = hash[hidx]; p; p = p->next) 
		if (compare_pattern(p->r, p->c))
			return p->r * N + p->c;

	return 0;
}
⚠️ **GitHub.com Fallback** ⚠️