[TIL] Queue & deque, Hash & Collision

Today I Learned [요약]

1. 알고리즘 문제(링크)를 풀며 큐(queue)에 대해 복습을 진행했다.

• DalSeo.com(링크)의 자료를 참고하며 알고리즘 문제를 deque를 활용해 해결했다.

2. 해쉬

• 해쉬 테이블(Hash Table)과 해쉬 함수(Hash Function)를 비롯한 개념학습 및,
• 충돌(Collision)을 해결하는 방법인 Chaining과 Open Addressing에 대해 학습했다.

Today I Learned [상세]

1. 알고리즘 문제를 풀었다.(queue / deque)

<프로그래머스 / 스택, 큐 / 주식가격 문제 / 링크 >

• 문제를 풀기 전 DalSeo.com(링크)의 자료를 참고하며 알고리즘 문제를 deque에 대해 학습했다.
• deque의 popleft() 메서드를 활용해 데이터를 제거하고, result에 담아 반환하면 되겠다는 계획을 세운 뒤 알고리즘 풀이를 시작했다. (중간에 살짝 막혀서 예시답안을 참고하긴 했다.)

from collections import deque

def solution(prices):
    prices = deque(prices)
    result = []

    while prices:
        non_drop_second = 0
        current_price = prices.popleft()

        for next_price in prices:
            if current_price > next_price:
                non_drop_second += 1
                break
            non_drop_second += 1

        result.append(non_drop_second)

    return result

input값을 deque로 받고, current_price에 prices.popleft() 값을 담아 non_drop_second를 구하여 return했다.

• 중간에 한번 TabError라는 처음보는 에러를 접했다. 습관적으로 스페이스바에 손이 가있어서 그랬는지... 특히나 파이썬 할 때는 스페이스바와 거리두기를 실천해야겠다는 다짐을 해본다.

2. 해쉬.(Hash Table, Function / Collision - Chaining)

해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다
hash(key) % len(self.items) 활용하여 데이터에 인덱스를 부여한다.

hash("fast")
-146084012848775433
hash("slow")
7051061338400740146

1) 충돌(Collision)

그러나 단순 배열에서 해쉬로 인덱스를 부여할 경우, 매핑이 되어 데이터를 덮어쓰는 충돌이 발생한다.

이를 해결하기 위한 첫번째 방법으로 링크드 리스트를 활용한 체이닝(Chaining)이 있다.

class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())
            
    def put(self, key, value):        
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)
        
 	def put(self, key, value):        
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)

인덱스 값이 겹치더라도, 링크드 리스트의 특성을 활용하여
동일 인덱스 > key 값이 일치하는 데이터 추출의 과정을 통해 원하는 데이터를 얻을 수 있다.

단, 해쉬테이블은 공간을 많이 사용하는 자료구조이다.
살을 주고 뼈를 취하는(살 == 공간, 뼈 == 시간) 방식이라고 볼 수 있다.

• 충돌을 해결하는 두번째 방법으로는 '개방주소법(Open Addressing)이 있다.
  간단하게 설명하자면, 배열의 남는 다음 공간에 넣는 방식이다.
  강의에서 크게 다루지 않기도 했고, 크게 메리트 있는 방식이라 느껴지지 않아 간단한 자료를 서칭하여 공부하였다. (개방주소법 관련 링크)