우선순위 큐
대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조.
그림과 같이 힙을 기반으로 구현된다.
파이썬 예시
heapq 사용
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def push(self, item, priority):
# 힙에 (우선순위, 항목) 튜플을 추가합니다.
heapq.heappush(self.heap, (priority, item))
def pop(self):
# 우선순위가 가장 낮은 항목을 제거하고 반환합니다.
return heapq.heappop(self.heap)[1]
def is_empty(self):
# 힙이 비어있는지 여부를 반환합니다.
return len(self.heap) == 0
def peek(self):
# 우선순위가 가장 낮은 항목을 반환하지만 제거하지는 않습니다.
return self.heap[0][1] if not self.is_empty() else None
# 우선순위 큐를 초기화합니다.
pq = PriorityQueue()
# 항목들을 우선순위와 함께 큐에 추가합니다.
pq.push("task1", 3)
pq.push("task2", 1)
pq.push("task3", 2)
# 우선순위 큐에서 항목들을 꺼냅니다.
while not pq.is_empty():
print(pq.pop())
---------------------------------------------------------
#결과
task2
task3
task1task1, 2, 3 순으로 들어왔지만, heapq 모듈을 이용한 heappush, heappop 등에 의해 자동으로 우선순위가 낮은 순으로 출력되었다.
heapq 를 사용하지 않고 구현
class PriorityQueue:
def __init__(self):
self.queue = []
def push(self, item, priority):
# (우선순위, 항목) 튜플을 리스트에 추가합니다.
self.queue.append((priority, item))
# 우선순위에 따라 리스트를 정렬합니다.
self.queue.sort(key=lambda x: x[0])
def pop(self):
# 우선순위가 가장 낮은 항목을 제거하고 반환합니다.
if not self.is_empty():
return self.queue.pop(0)[1]
else:
raise IndexError("pop from an empty priority queue")
def is_empty(self):
# 리스트가 비어있는지 여부를 반환합니다.
return len(self.queue) == 0
def peek(self):
# 우선순위가 가장 낮은 항목을 반환하지만 제거하지는 않습니다.
if not self.is_empty():
return self.queue[0][1]
else:
raise IndexError("peek from an empty priority queue")
# 우선순위 큐를 초기화합니다.
pq = PriorityQueue()
# 항목들을 우선순위와 함께 큐에 추가합니다.
pq.push("task1", 3)
pq.push("task2", 1)
pq.push("task3", 2)
# 우선순위 큐에서 항목들을 꺼냅니다.
while not pq.is_empty():
print(pq.pop())
맵(map)
특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조.
ex) "이승철" : 1
"박동영" : 2
와 같은 방식으로 string:int 형태로 값을 할당해야 할 때 map을 사용.
레드블랙트리 자료구조를 기반으로 형성되고, 삽입시 자동 정렬된다.
맵은 해시 테이블을 구현할 때 주로 사용된다.
셋(set)
특정 순서에 따라 고유한 요소를 저장하는 컨테이너.
중복되는 요소가 없고 오로지 unique한 값만 저장하는 자료구조.
특징
set은 내부적으로 해시 함수를 사용하여 요소를 관리합니다.
요소의 해시 값을 저장하기 위한 추가적인 메모리가 필요합니다.
메모리 사용량은 요소의 수와 요소의 해시 값 크기에 따라 달라집니다.
삽입,삭제,조회 : O(1)
해시 충돌이 발생할 경우: 최악의 경우 O(n)의 시간 복잡도를 가질 수 있지만, 이는 드물게 발생합니다.
파이썬 예시
# Set 초기화
my_set = set()
# Set에 요소 추가
my_set.add(1)
my_set.add(2)
my_set.add(3)
my_set.add(1)
# Set에서 요소 확인
print(2 in my_set) # True
print(4 in my_set) # False
# Set에서 요소 제거
my_set.remove(2)
# Set의 모든 요소 출력
for item in my_set:
print(item)
---------------------------------
#결과
1
3
해시테이블
무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블.
특징
1. 빠른 검색속도
-> 삽입,삭제,탐색 : O(1)
2. 해시 충돌: 서로 다른 키가 동일한 해시 값을 가질 경우 발생합니다. 이를 해결하기 위해 체이닝(Chaining)이나 개방 주소법(Open Addressing) 등의 기법을 사용합니다.
3. 유연한 키 타입: 문자열, 숫자 등 다양한 타입의 키를 사용할 수 있습니다.
파이썬 예시
# 해시맵 초기화
hash_map = {}
# 해시맵에 값 추가
hash_map["apple"] = 3
hash_map["banana"] = 5
hash_map["cherry"] = 7
# 해시맵에서 값 검색
print(f"Value for 'apple': {hash_map['apple']}") # 3
print(f"Value for 'banana': {hash_map['banana']}") # 5
# 해시맵의 값 업데이트
hash_map["apple"] = 4
# 해시맵에서 값 삭제
del hash_map["banana"]
# 해시맵의 모든 키-값 쌍 출력
for key, value in hash_map.items():
print(f"{key}: {value}")
----------
#결과
Value for 'apple': 3
Value for 'banana': 5
apple: 4
cherry: 7해시 충돌 해결방법
1. 개별 체이닝(Separate chaining)
예를들어 키와 해시값이 그림과 같이 되어있고, 해시함수를 통과한 2번인덱스에 윤아, 서현이 겹쳐서 해시 충돌이 일어났다.
이럴 때 그림과 같이 윤아, 서현을 연결리스트로 연결해주는 방식으로 충돌을 해결할 수 있다. 하지만 메모리 사용량이 늘어나고 충돌이 나지 않는 것보다는 효율이 떨어진다.
2. 개방 주소법 (Open adrresing)
오픈 어드레싱(Open Addressing) 방식은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다. 사실상 무한정 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결하며, 이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.
ex) 선형 탐색 (Linear Probing)
제곱 탐색 (Quadratic Probing)
이중 해시 (Double Hashing)
출처
https://ihp001.tistory.com/90 [효팍이의 프로그래밍:티스토리]
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호)
