스파르티코딩클럽 알고리즘 강의

해시 테이블

• 키를 값에 매핑할 수 있는 구조. (파이썬을 예로 들면 dictionary)
• 장점: 대부분의 연산(earch, insertion, deletion)이 분할 상환 분석에 따른 시간 복잡도가 O(1)임.

해시 함수

임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수.
예)
입력: ABC, 1324BC, AF32B (임의 크기 데이터 3글자, 6글자, 5글자)
위 데이터들이 화살표로 표시한 특정 함수를 통과하면 2바이트의 고정 크기 값으로 매핑된다.
ABC -> A1
1324BC -> CB
AF32B -> D5

특징

• 해시 함수 값의 충돌 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값 균일 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것.
해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나.

load factor = n(해시 테이블에 저장된 데이터 개수) / k(버킷의 개수)
전체 공간의 몇 퍼센트를 차지하는 지 확인하는 지수.
load factor가 증가할 수록 해시 테이블의 성능은 감소한다.
자바: 0.75, 파이썬 0.66, 루비: 0.5 등 언어마다 다름.

해시 함수의 대표적인 기법들

나눗셈 방식

h(x) = x mod m

• h(x): 입력값 x의 해시 함수를 통해 생성된 결과
• m: 해시 테이블의 크기 (일반적으로 2의 제곱수(power)에 가깝지 않은 소수 추천)

개별 체이닝 방식

• 흔한 해시 테이블 방식.
  
  같은 해시 값을 받은 키들에 대해 체이닝 방식으로 처리함(먼저 들어온 키 뒤에 연결리스트로 삽입).

간단한 원리:
1. 키의 해시 값 계산.
2. 해시 값을 이용해 배열의 인덱스 구하기.
3. 같은 인덱스가 있다면 연결 리스트로 연결.

잘 구현하면 대부분의 탐색은 O(1). 하지만 최악의 경우(모든 해시 충돌 발생) O(n).

오픈 어드레싱 방식

충돌 발생 시 탐사를 통해 빈 공간을 찾는 방식.(모든 원소가 반드시 자신의 해시 값과 일치하는 주소에 저장된다는 보장 x)

선형 탐사의 문제점: 클러스터링 (해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 특정 구간에 뭉치는 현상)

오픈 어드레싱 방식의 문제점: 데이터 개수가 버킷 사이즈보다 큰 경우에는 삽입 불가. 이런 경우 리해싱 발생 (기존 버킷보다 더 큰 버킷을 만들어 데이터 복사)

파이썬에서의 해시 테이블

• 해시 테이블로 구현된 파이썬의 자료형: 딕셔너리.
• 딕셔너리의 구현 방식: 오픈 어드레싱

파이썬이 오픈 어드레싱을 사용한 이유

오픈 어드레싱 vs. 체이닝 성능표

load factor가 증가할 때 체이닝 방식의 성능은 일정하게 증가(저하)하지만 오픈 어드레싱 방식의 성능은 lf가 0.8 이전일 때는 체이닝 방식의 성능보다 낮고(좋고) 그 이후에는 급격하게 증가(저하)함.

파이썬의 lf 기준인 0.66을 초과하면 버킷을 늘려버리기 때문에 높은 성능을 유지할 수 있다.

또한 체이닝 방식은 메모리를 할당하는 오버헤드(비용)가 높기 때문에 파이썬은 오픈 어드레싱을 채택했다.

실습

k번째 큰 요소 (최대 힙)

진행순서

1. 최대 힙 구현
2. k번 pop 반복
3. 마지막으로 pop된 값 반환

힙 클래스

우선 힙에 삽입/추출하는 로직은 알고리즘 강의 2주차에 그림과 함께 자세하게 나와있다.

삽입 로직

1. 리스트의 끝에 current 삽입
2. parent보다 current가 큰 경우 둘이 swap
3. current에 parent를 담고 parent에 parent의 parent를 담음 (한 칸씩 위로 올라가기)
4. parent가 첫 번째 요소에 도달했을 때 종료

추출 로직

1. root(첫 번째 요소)와 end(마지막 요소)를 swap
   예를 들면 root: 5->1, end: 1->5
2. end를 pop (보통 pop한 값을 반환해야 하기 때문에 따로 변수에 저장)
3. 새로운 root(1)를 자식노드들과 비교해서 힙의 구조 조정

전체 코드

class BinaryMaxHeap:
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1
    
    # percolate: 스며들다
    def _percolate_up(self):
        # 가장 최근에 추가된 요소
        current = len(self)

        # left라면 2*current, right라면 2*current+1 이므로 parent는 항상 current//2
        parent = current // 2

        # parent와 비교했을 때 parent보다 크다면 swap
        while parent > 0:
            # if self.items[current] < self.items[parent]: # ===> min_heap
            if self.items[current] > self.items[parent]:
                self.items[current], self.items[parent] = self.items[parent], self.items[current]

            # 비교가 끝날 때마다 current는 한 칸씩 위로 올라감
            current = parent
            # parent도 마찬가지로 한 칸씩 올라감
            parent = current // 2

    def _percolate_down(self, current):
        biggest = current
        left = 2 * current
        right = 2 * current + 1

        # left가 self의 범위 안에 있고 items의 left번째 요소가 biggest번째 요소보다 크다면 biggest에 left 저장
        if left <= len(self) and self.items[left] > self.items[biggest]:
            biggest = left

        # right가 self의 범위 안에 있고 items의 right번째 요소가 biggest번째 요소보다 크다면 biggest에 right 저장
        if right <= len(self) and self.items[right] > self.items[biggest]:
            biggest = right

        # 위 두 if문에서 biggest가 바뀌었다면 current번째 요소와 biggest번째 요소 swap
        if biggest != current:
            self.items[current], self.items[biggest] = self.items[biggest], self.items[current]
            # current를 biggest 기준으로 무한 반복 (언제까지? current가 biggest일 때까지)
            self._percolate_down(biggest)


    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None
        
        # 0번째는 None이기 때문에 그 다음 번째인 1이 root
        root = self.items[1]
        # 마지막 요소를 맨 앞으로 가져옴 
        # (원래는 둘이 swap 해야 하는데 어차피 마지막 요소는 바로 pop할거라 굳이 1번째 요소를 마지막에 넣어줄 필요가 없음)
        self.items[1] = self.items[-1]
        # 마지막 요소 제거
        self.items.pop()
        # 힙 수정
        self._percolate_down(1)

        return root

페어 프로그래밍

문제풀이

1. 요세푸스 문제 0

대학교에서 컴공 수업 때 나왔던 문제여서 문제의 이해 자체는 필요 없는 상태였다.
2,3일차 문제풀이에서 덱을 이미 경험했기 때문에 덱을 활용하면 금방 구현할 수 있을 것 같았다.

풀이:
제거할 k번째 요소를 맨 앞으로 오도록 덱을 시프트(rotate(-k)) 해주고 덱에서 삭제한 값을 새로운 리스트에 추가한다.

사실 이게 끝이긴 한데 출력문의 포맷이 주어져있어서 구글링을 통해 print 함수의 매개변수 몇 개와 리스트의 각 요소를 출력하게 하는 문법을 알아냈다.

리스트의 각 요소를 출력하는 한 줄짜리 코드 방법: 대괄호로 print 함수을 감싸고 print 함수 끝에 for문을 넣어주면 된다.

[print(i) for i in list] # 일반적으로 사용하는 for문 처럼 list 대신에 range를 써도 된다. 

전체 코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

sequence = []
deque = deque(range(1, N+1))

while len(deque) != 0:
    deque.rotate(-(K-1))
    sequence.append(deque.popleft())
    
print('<', end='')
[print(i, end=', ' if i != sequence[-1] else '>\n') for i in sequence]

2. 최소 힙

어제 문제 중 최대 힙과 완전히 똑같은 코드이다.
heapq의 디폴트는 최소 힙이기 때문에 어제는 요소를 삽입하고 추출할 때 -1을 곱해서 최소값으로 만들어주었다면 오늘은 그냥 있는 그대로 사용했다.

전체 코드

import heapq
import sys
input = sys.stdin.readline

heap = []

N = int(input())

for i in range(N):
    x = int(input())
    if x != 0:
        heapq.heappush(heap, x)
    else:
        print(heapq.heappop(heap) if len(heap) != 0 else 0)

3. 약수

이 문제 역시 이해만 하면 금방 푸는 문제였다.

풀이:
주어진 숫자들을 리스트에 넣고 그 중 최소값이랑 최대값이랑 곱해주면 끝.

시간을 비교하고 싶어서 리스트 구현과 힙 구현 두 가지 버전으로 풀이를 해봤다. 힙으로 구현하는 게 코드가 훨씬 길어지긴 하는데 시간은 비슷하게 걸리는 것 같다.

전체 코드

# v1
num = int(input())
n = list(map(int, input().split()))

print(max(n) * min(n))

# v2
import sys, heapq
input = sys.stdin.readline

N = int(input())
divisors = list(map(int, input().split()))

min_heap = []
max_heap = []

for i in divisors:
    heapq.heappush(min_heap, i)
    heapq.heappush(max_heap, i * -1)

print(heapq.heappop(min_heap) * (heapq.heappop(max_heap) * -1))