코테 스터디 3주차 [해시]

코테 스터디에서 진행하는 책, 출처: yes24

강의 링크(인프런)

(강의 내용 정리에 사용되는 자료의 출처는 저자님의 강의입니다. 출처 - 코딩 테스트 합격자 되기 [박경록])

(자료를 참고해서 제가 시각적으로 더 보기 편하게 편집한 사진들도 있습니다.)

대학원 서류 접수 기간이라, 지금 해놓지 않으면 또 미뤄질 것 같아서 미리 수강하고 정리를 해봤습니다!

 

▶ 강의 목차

• 해시의 개념
• 해시 함수
• 충돌 처리
• 실제 예시

 

▶ 강의 내용 정리

• 배열로 구현한 연락처
  • 이름 → 연락처 (이름에 해당되는 연락처 저장)
  • 만약에 홍길동이라는 사람의 연락처를 알고 싶다면 어떻게 해야 해?
    • 이름 테이블 "홍길동" 선형 탐색
    • 그 위치에 해당되는 전화테이블을 참조
  • 특정 데이터의 위치를 판단할 수 있는 정보가 없으므로, 선형탐색을 해야 함
  • 이 배열에서는 [이름 5] 까지 가려면, 순차적으로 0부터 4까지 탐색해야 함
    • 비효율적임!

 

• 인덱스에 이름정보를 어떻게 넣을 것인가?
  • 홍길동 이름보고 해시함수를 통해서 어느 배열 인덱스 위치에 저장되는지 알 수 있게 해 보자
    • 선형 탐색보다 조금 더 빠르게!

 

 

• 해시를 적용한 연락처
  • 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키-값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
  • 키를 해시 함수에 넣으면 인덱스가 나오는 자료구조
  • 아래 사진으로 이해를 해보자!
  • "함진아"라는 키에 해시 함수를 적용하면 인덱스 2를 얻는다.
    • 몇 번을 해봐도 "함진아"의 해시 함수 적용값은 2가 된다.
    • 이름을 가지고 바로 연락처 위치를 알 수 있다.
    • 이름 자체로 인덱스를 구할 수 있다.
  • 아까 배열에서 선형탐색할 때는 데이터 개수가 N개라면 O(N)이었지만
  • 해시를 이용한 경우 이름 자체로 인덱스를 구할 수 있으므로, O(1)이다!!
  • 해시의 요소 3가지  = 해시 함수, 버킷(테이블의 하나하나), 해시테이블

해시 구조

 

• 해시함수(정의)
  • 임의의 키를 해시 테이블의 인덱스로 변경해 주는 함수
  • 2가지 키 포인트!
  • 해시 테이블의 크기가 N이라면 해시 함수는 0 ~ (N-1) 사이 값을 내야 함
  • 충동을 최소화할수록 좋은 해시 함수
• "홍길동"과 "홍길서"는 다른 키 임
• 서로 다른 키에 대해 해시 함수가 동일한 인덱스를 반환할 경우 충돌이 발생

 

• 해시함수(나눗셈 법)
  • h(x) = x mod k (x는 키, k는 소수) (x를 k로 나눈 나머지 값을 인덱스 값으로 사용)
  • k로 나눈 나머지는 0 ~ k-1이므로 해시 테이블의 크기는 k
  • k가 소수인 이유는 충돌을 줄이기 위함(소수가 아니면 k주기로 해시값 반복 됨. 책에 자세하게 설명 있음!)
• mod가 뭐죠?
• 7 % 4 = 3 (%를 mod라고 생각하면 된다구~)
• 7/4 = 몫이 1이고, 나머지 3

 

• 조금 수학적으로 보는 예시. 7 % 2
  
  • 2로 나눈 나머지
  • 짝수는 무조건 0
  • 홀수는 무조건 1
• 0 or 1이니까 충돌이 엄청 많이 발생할 수밖에 없음
• 해시 테이블의 크기가 K인데, 0,1 만 사용할 수 있다.
• 소수 경우에는 나누어 떨어질 수 없으니, 소수를 많이 사용함

나눗셈 법

• 대신 단점도 있음
  • 해시 테이블의 크기가 커디면 더 큰 소수가 필요함
  • 해시 테이블의 크기가 K이면 0 ~ K-1 까지 나오는 소수가 있어야 함(MOD 했을 때)
  • 소수 자체를 큰 것을 찾는 게 쉽지가 않아서 단점

 

 

• 해시함수(곱셈법, 정의)
  • 나눗셈법은 k가 소수여야 하므로, 테이블 크기가 커지면.. 큰 소수가 필요함(어려움)
  • 그래서 나온 것이 곱셈법!
  • 곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식
  • h(x) = ((x*A)mod 1)*m)
    • x는 키, A는 황금 비, m은 최대 버킷의 개수

 

• 해시함수(곱셈법, 황금비란?)
  • 아래 사진처럼 구한 황금비에서 우리가 사용할 부분은 소수점 부분!
  • 황금비 외울 필요는 없지만 여러 곳에 쓰임. 궁금하면 위키피디아에 검색

 

• 해시함수(곱셈법, 실제연산)
  • h(x) = ((x*A) mod 1) *m)
    • x는 키, A는 황금 비, m은 최대 버킷의 개수
  • 키 값에 A를 곱함
  • 1.7이면 정수는 1 소수는 7
  • mod 1을 하면 소수부분만 취함
  • (x*A) mod 1) 했을 때 나올 수 있는 결과는 0 ~ 0.99999999999
  • 그 결과에 m을 곱하면
  • 0 ~ m-1.xxxxxxxxxxx
    • 이 부분(정수 부분)을 취해서 인덱스에 활용
    • 아래 사진에 있는 표 참고!
  • 곱셈법이 조금 더 복잡하지만, 소수가 필요 없다는 점에 좋음

 

 

• 해시함수(문자열 해싱)
  • 지금까지는 키로 주어졌지만, 문자로 주어지면 어떻게 하는지 알아보도록 하자
  • 문자열의 아스키코드 값을 활용한 해싱

이해를 해야함!

 

• 해시함수(문자열 해싱, 해시함수 설명)
  • 공식을 한번 풀어봅시다~!
  • p는 31 (홀수이면서 메르센 소수. 값을 균등하게 퍼뜨리기 위한)
  • 숫자가 금방 커지므로 구현시 overflow가 발생할 수 있음
    • 예를 들면 31의 50승 이렇게 구해라 하면 오버플로우 발생
    • 구현할 때는 overflow 생각해야 함
    • 그래서 수정된 공식 사용
  • a = 1, b =  2, c = 3, ..... z = 26로 숫자를 매칭해서 사용
  • 각 문자마다 숫자를 하나씩 매칭

 

• 수정된 공식

변형해서 구현한 공식

 

 

• 해시 충돌이란?
  • 서로 다른 키에 대해 해시 함수 결괏값이 같은 경우 [충돌]이 발생함
    • 체이닝, 개방 주소법이 충돌을 처리하는 대표적인 방법

 

 

• 해시충돌처리(체이닝)
  • 충돌 발생 시, 해당 버킷에 링크드리스트로 데이터를 연결함
  • 특정 버킷에 데이터가 N개인 경우, 원하는 값을 찾는데 O(N)이 걸릴 수 있음
  • 최악의 경우
    • 데이터가 N개 있는데 전부 충돌이 되었다!
    • N번째 원소 찾는데 O(N)이다.
    • 근데 이런 경우는 드물다
  • 실제로는 이를 좀 더 효율적으로 하는 방법도 가능하나(선형 + 이진트리) 체이닝의 특징을 설명하기 위해 간소화함
  • But. 우리는 코테 준비를 하는 것이기 때문에 나중에 관심 있으면 심도 있게 공부하는 걸로

 

• 해시충돌처리(개방 주소법 - 선형 탐사)
  • 아까 체이닝에서는 해시테이블 외 추가 공간을 사용했지만, 개방 주소법은 해시 테이블 내에서 해결하려고 한다!
    • 최대한 기존 테이블을 사용하자는 방식
    • 체이닝 기법보다는 메모리를 아낄 수 있음
  • 충돌 발생 시, 다른 빈 버킷을 찾아 충돌값을 삽입
  • 최대한 기존 테이블을 사용하자는 방식(메모리를 아낄 수 있음)
  • k는 키, i는 충돌 시 이동할 버킷 수, m은 버킷 사이즈

 

• 해시충돌처리(개방 주소법 - 이중해싱)
  • 용어 그대로 해시 함수를 2개 사용(경우에 따라 N개까지 확장)
  • 기존에 i를 더했던 선형탐사와 다르게 2번째 해시함수에 i를 곱하는 방식도 가능
  • 이때 클러스터를 줄이기 위해 m을 제곱수나 소수로 함
  • k는 키, i는 임의의 수, h1은 첫 번째 해시함수, h2는 두 번째 해시함수, m은 테이블 크기
  • 해시함수를 2개 적용하고 두번째 해시함수에 i를 곱한다~

 

• 지금까지 배운 것 정리
  • 해시개념
  • 해시함수
    • 나눗셈법
    • 곱셈법
    • 문자열 해싱
  • 해싱충돌처리
    • 체이닝
    • 개방 주소법
      • 선형탐사
      • 이중해싱

 

• 그러면 언제 해시를 활용해서 문제를 풀어야 하나?
  • 키- 값 쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우
    • 예를 들어 사전(단어를 검색해서 뜻을 찾음)이나
    • 연락처(이름을 검색해서 번호를 찾음)
    • 코테에서는 키랑 값을 잘 설정해야 함!!!
    • 이름(키) - 전화번호(값). 이름을 통해 전화번호를 검색한다. 이렇게 해야 하는데
    • 초보자의 경우 전화번호(키) - 이름(값)으로 해버리는 대형사고가 난다!!!
    • 이렇게 해버리면 해시를 사용하는 의미가 없음. 선형 탐색이 되어버린다...
  • 중복되지 않는 키를 사용하는 경우
    • 예를 들어 학번이나 집주소(중복되지 않음)
    • '키 1'이 있고 이에 해당하는 '값 1'이 있음
    • '키 1'에 '값 2'가 있다고 해버리면 기존에 해당하는 값이 없어지고 대체된다! 조심해야 함

 

 

• 언제 해시를 활용해서 문제를 풀어야 하나? (예시 1)
  • 학생 정보 관리 시스템
  • 학생들의 정보를 관리하는 시스템을 예로 들어보겠습니다.
  • 학생의 ID를 키로, 성적을 값으로 저장한다고 가정합니다.
  • (코드 부분은 C++이라 생략하겠습니다!)

QR코드를 스캔하면 해당 문제 코드가 있는 git hub으로 연결됩니다

• 가장 많이 헷갈리는 부분
  • map을 해시로 착각하는 것
  • 해시(x), 이진탐색트리를 활용한 것
  • 매번 키 순으로 데이터가 정렬됨 O(logN) → TLE 발생할 수 있음
  • 예시를 들어보자!
  • 2중 반복문 안에 map에 데이터 추가 연산 O(N^2logN)
  • 키 값 정렬이 필요하지 않은데 map을 쓰면 안 됩니다.
  • 해시 문제는 map이 아니라 unordered_map
• ID             학점
• "12345"      "A"
• "67890"      "B"
• "54321"      "A+"
• 값의 타입을 벡터로?
• ID             학점
• "Alice"      90 85        평균을 구해야 하니까 나누는 건 size를 이용하면 편함
• "Bob"       78 82 88

 

 

• 언제 해시를 활용해서 문제를 풀어야 하나? (예시 2)
  • 문자열이 입력됩니다.
  • 문자열의 각 문자의 개수를 확인하고 싶습니다.
  • (코드 부분은 생략하겠습니다)
  • 키는 char형으로, 개수는 int형으로 입력받음
  • 이외에는 파이썬과 헷갈릴 수 있으므로 생략하겠습니다!

해당 문제 코드가 있는 git hub QR 코드

 

 

• 해시를 사용하지 말아야 하는 경우
  • 특정 키에 여러 가지 값을 매칭해야 하는 경우
  • 앞서 이야기했던 것과 같음!

 

 

 

---

 

 

▶ 강의 후기

• • 배열은 코테를 풀면서 사용해봤는데, 해시라는 개념은 한번도 적용해보지 못했습니다.
  • 저번 강의와 마찬가지로 저자님이 전달하고자 하는 개념은 이해했습니다.
  • 하지만 강의와 스터디의 목적이 코딩 테스트 문제를 푸는 것인 만큼 파이썬 편의 책을 참고해서 문제를 풀어보며 직접 적용하는 시간이 필요할 것 같습니다.
  • 수강하고 천장을 보면서 이걸 설명할 수 있을까? 생각해봤는데 해시함수 공식 부분과 공식을 수정해야하는 이유 그리고 수정한 부분에 대한 설명까지는 힘들 것 같습니다. (해당 부분에 복습이 필요한...)

 

▶ 궁금한 점

• 당장은 없는데 복습과 코테 문제를 풀면서 생길 것 같습니다
• 생기는대로 추가로 작성해 보겠습니다.