[인프런] 코딩 테스트 합격자 되기 C++
강의 링크 : https://www.youtube.com/watch?v=KsfmSyIYX3g&t=3s
<Hash>
배열의 경우 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색 해야 함 O(n)
contents 자체를 가지고 위치 (index)를 알 수 있는 것이 해시
해시 함수를 사용해서 변환한 값을 인덱스(해시값)로 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 O(1)
해시함수 : 임의의 키를 해시테이블의 인덱스로 변경해주는 함수
- 해시 테이블의 크기가 N이라면 해시함수는 0 ~ (N-1) 사이 값을 내야 함
- 충돌을 최소화 할수록 좋은 해시함수
* 충돌 : 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환하는 것
[해시함수 종류]
- 나눗셈법 : h(x) = xmodk (x는 키, k는 소수)
- k가 소수여야 함 -> 테이블 크기가 커지면 큰 소수 필요 (큰 소수 구하기 어려움)
- 곱셈법 : h(x) = (((x * A) mod 1) * m), (x는 키, A는 황금 비, m은 최대 버킷의 개수)
- 황금비(A=1.6180339887)를 곱하는 방식
- mod 1 : 소수 부분만 취함 => 0 ~ 0.999999
- 위 결과에 m을 곱하면 0 ~ m-1.xxxx
- 문자열 해싱 : h(s) = (s[0] + s[1]*p + s[2]*p^2 + ... + s[n-1] * p^(n-1)) mod m
- 문자열의 아스키 코드 값을 활용한 해싱
- p는 31 (홀수이면서 메르센 소수 - 값을 균등하게 퍼트리기 위함), m은 테이블 크기
- a = 1, b = 2, ... z = 26로 숫자를 매칭해서 사용
- 숫자가 금방커지므로 구현시 overflow가 발생할 수 있음 -> 수정된 공식 사용
- (a+b)%c = (a%c + b%c) %c
- => h(s) = (s[0] %m + s[1]*p %m + s[2]*p^2 %m + ... + s[n-1] * p^(n-1) %m)%m
[해시 충돌]
서로 다른 키에 대해 해시 함수 결괏값이 같은 경우 "충돌"이 발생함
충돌을 처리하는 대표적인 방법 : 체이닝, 개방 주소법
- 체이닝 : 충돌 발생 시, 해당 버킷에 링크드리스트로 데이터를 연결함
- 특정 버킷에 데이터가 N개인 경우, 탐색 성능은 최대 O(N)이 됨
- 이를 좀 더 효율적으로 하는 방법 : 선형+이진트리
- 개방 주소법 - 선형 탐사 : h(k,i) = (h(k) + i) mod m (k는 키, i는 충돌 시 이동할 버킷 수, m은 버킷 사이즈)
- 충돌 발생 시, 다른 빈 버킷을 찾아 충돌값을 삽입
- 최대한 기존 테이블을 사용하자는 방식 (메모리 save)
- 개방 주소법 - 이중해싱 : h(k,i) = (h1(k) + i*h2(k)) mod m
- 해시 함수를 2개 사용 (경우에 따라 N개까지 확장0
- 2번째 해시함수에 i를 곱하는 방식, 이 때 클러스터를 줄이기 위해 m을 제곱수나 소수로 함
[해시를 사용하는 경우]
- 키-값 쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우 ex) 사전이나, 연락처 검색
- 중복되지 않는 키를 사용하는 경우 ex) 학번, 집주소
예시)
- map
- 해시(x), 이진탐색트리를 활용한 것
- 매번 키 순으로 데이터가 정렬됨 O(logN)
- 2중 반복문 안에 map 데이터 추가 연산하면 O(N^2*logN) -> TLE 발생 가능
- 키 값 정렬이 필요하지 않은데 map 쓰면 안됨
- 해시 문제는 map이 아니라 unordered_map
- 파이썬은 defaultdict가 따로 있는 반면 c++ map은 기본값으로 0 들어감
[풀어볼 만한 문제]
C++ 예시 코드를 보는데 간단한 구현 부분도 문법들이 너무 낯설게 느껴짐
계속 보면서 익힐 필요
준비하고 있는 시험이 있어서 문제는 추후 풀어볼 예정
'Coding Test' 카테고리의 다른 글
[코딩 테스트 합격자 되기] 트리 (0) | 2024.08.03 |
---|---|
알고리즘 문제 오답 노트 (0) | 2024.08.01 |
[코딩 테스트 합격자 되기] 스택/큐 (0) | 2024.07.20 |
[코딩 테스트 합격자 되기] 시간 복잡도 (0) | 2024.07.08 |
[강의] 코딩테스트 시간복잡도 (0) | 2024.06.13 |