해시 테이블(Hash Table)
- 먼저 키(key)와 값(value)으로 구성된 데이터가 필요하다.
- 여기서 “key”를 해시값으로 만들어, 해당 해시값을 “인덱스”로써 활용하여 테이블에 저장한다. 여기서 해시값은 정수 형태가 된다.
- 데이터(value)를 해시하여 인덱스로 쓰는 거 아니냐는 사람들이 있는데, 이럴 경우 value가 같으면 인덱스가 중복될 수 있다. 해시함수는 같은 입력에 대해서 항상 같은 해시값을 만들기 때문이다.
- 어떤 값을 찾든 O(1)의 복잡도를 가진다. 고유값으로 접근하면 되기 때문.
- 해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다.
해시 테이블의 장/단점
- 장점 : 자료의 검색, 읽기, 저장 속도가 빠르다. 즉 데이터 조회가 빠르다.
- 장점 : 자료가 중복되는지 확인하기 쉽다.
- 단점 : 저장 공간이 더 필요할 수 있다.
- 단점 : 충돌을 해결할 방법이 필요하다.
해시 값이 같을 경우
- key가 달라도 해시 값이 같을 때가 있다.이걸 “충돌(Collision)”이라고 하며, 2가지 방법으로 해결될 수 있다.
- 분리 연결법(Separate Chaining, 체인법) : 충돌한 키의 데이터를 연결 리스트로 저장한다.
같은 인덱스에 먼저 저장된 첫 노드가, 다음 노드의 주소를 가지고 있다.
- 개방 주소법(Open Addressing, 더블 해싱) : 충돌 시, 다음 빈자리를 찾아 저장한다.
두 가지 해시함수를 사용해 첫번째 해시값이 충돌되면 두번째 해시값을 더해 주소를 계산한다.
개방 주소법은 효과적이지만 적재율이 높을 경우 처리속도와 효율이 떨어질 수 있다. 적재율이 80%를 넘어가면 성능이 급격하게 떨어진다.
파이썬으로 해시 테이블을 사용하려면
- python에서 해시 테이블을 사용하려면 dictionary 자료형을 사용해야 한다.
- dictionary 자료형이 해시 테이블 그 자체이며, 더블 해싱을 이용한 개방 주소법을 사용한다.
- "MurmurHash" 해시함수를 사용하고, 적재율이 0.66을 초과하면 resizing을 통해 해시 테이블의 크기를 2배로 늘린다.
- 일반적으로 적절한 적재율은 0.7 정도이나, 메모리를 조금 더 쓰더라도 안정성을 추구하는 파이썬만의 방향성이 반영된 것으로 보인다.
적재율(Load Factor)
- 해시 테이블에 얼마만큼의 데이터가 저장되어 있는지 표현하는 지표
- 데이터 수 / 테이블 슬롯 수 -> 적재율
ex) 10크기의 테이블에 5개 데이터 저장 -> 적재율 : 0.5
- 적재율이 너무 높으면 해시 충돌이 자주 발생할 수 있다.
- 적재율이 너무 낮으면 메모리의 낭비가 발생할 수 있다.
- 일반적으로 적절한 적재율은 0.7 정도이다.
피보나치 수
- 앞 두 수의 합이 뒤의 숫자를 이루는 수열
- ex) 1 1 2 3 5 8 13 21 34 55 .......
1. 파이썬 피보나치 수 구현 (반복문)
n = int(input())
a = 0
b = 1
for _ in range(n):
a, b = b, (a + b)
print (a)
숫자 n을 입력받아 반복문으로 n번째 피보나치 숫자를 출력하는 코드이다.
2. 파이썬 피보나치 수 구현 (재귀)
def fi(n):
if n <= 2:
return 1
return fi(n - 1) + fi(n - 2)
print(fi(7))
마찬가지로 숫자 n을 입력받아 n번째 피보나치 숫자를 출력하는 함수이다.
재귀식으로 구현하면 구현이 더 간단하지만, 시간과 메모리를 더 잡아먹을 수 있다는 단점이 있다.
실제로 백준 피보나치 문제에 재귀로 제출했는데 시간 초과가 떴지만 반복문은 통과되었다.
이진트리(Binary Tree)
- 모든 노드들이 둘 이하의 자식을 가진 트리, 둘보다 크면 이진 트리가 아니다.
- 하나의 노드만 존재하는 트리도 이진 트리이다.
완전 이진 트리(Complete Binary Tree)
- 마지막 레벨을 제외하고 노드들이 가득 차 있는 트리
- 자식 노드는 반드시 왼쪽부터 채워져야 함
힙(Heap)
- “완전 이진트리” 형태로 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조
- 부모-자식간 정렬은 보장하나 형제간 정렬은 보장하지 않는다. “반 정렬 상태”
- 최대 힙(Max Heap), 최소 힙(Heap)으로 나뉜다.
최소 힙(Min Heap)
- 부모 노드가 자식 노드보다 작거나 같은 완전 이진트리
- 루트 노드가 가장 작다.
최대 힙(Max Heap)
- 최소 힙과 반대로, 부모 노드가 자식보다 크거나 같은 완전 이진트리
- 루트 노드가 가장 크다.
최소/최대 힙의 삽입 과정
- 트리의 가장 마지막 부분에 데이터를 삽입 후, 부모 노드와 반복적으로 비교하고 교체되어 알맞은 자리를 찾아간다
최소/최대 힙의 삭제 과정
- “최상위 노드”를 삭제와 동시에 반환한다.
- 이후 최상위 노드에 가장 마지막 위치의 노드를 위치시켜, 자식 노드와 반복적으로 비교하고 교체되어 알맞은 자리를 찾아간다. 자식 노드가 2개라면 더 작은/큰 값과 교체한다.
우선순위 큐(Priority Queue)
- 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 선입선출(FIFO) 자료구조이다.
- 반면 우선순위 큐는 “우선순위가 높은 데이터”가 먼저 나간다.
- 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.
- 파이썬의 heapq로도 구현할 수 있는데, heapq는 최소 힙만 지원하기 때문에 값을 저장할 때 음수로 저장한 후 꺼낼 때 abs()함수로 양수로 만들면 마치 최대 힙처럼 사용할 수 있다. -> 음수로 만들면 최댓값이 최소값이 되고, 최소 힙에선 최소값이 루트 노드로 가니까.
'크래프톤 정글 > TIL' 카테고리의 다른 글
| [크래프톤 정글 5기] week02 알고리즘 주차 열한번째 날, 파이썬 나눗셈, 위상 정렬 (0) | 2024.03.31 |
|---|---|
| [크래프톤 정글 5기] week02 알고리즘 주차 아홉번째 날, 분할 정복, 뮤터블, 그래프, 트리, DFS/BFS, 이진검색트리, 서로소집합 (2) | 2024.03.29 |
| [크래프톤 정글 5기] week01 알고리즘 주차 다섯번째 날, CPU, 인스트럭션, 퀵 정렬(Quick Sort) (0) | 2024.03.26 |
| [크래프톤 정글 5기] week01 알고리즘 주차 네번째 날, 스택, 큐, DFS, 그래프, 백트래킹, 이분 탐색 (2) | 2024.03.24 |
| [크래프톤 정글 5기] week01 알고리즘 주차 두번째 날, Big-O, 시간/공간 복잡도 (2) | 2024.03.23 |