[알고리즘] 자료구조 정리

알고리즘 문제 풀이 시 사용 빈도가 높은 자료구조만 정리 예정

✔️ 해시테이블

해시테이블은 키(key) 값(value)으로 이루어진 데이터를 저장하는 자료구조이고 파이썬에선 딕셔너리를 활용한다.

# 해시 테이블 선언
dict = {}

dict["key1"] = 100
dict["key2"] = 200
dict["key3"] = 300
dict["key4"] = 400

# 딕셔너리 출력
print(dict) # {'key1': 100, 'key2': 200, 'key3': 300, 'key4': 400} 

# 특정 키 값 조회
print(dict["key1"]) # 100
print(dict["key2"]) # 200
print(dict["key3"]) # 300
print(dict["key4"]) # 400

# 특정 키 값 삭제
del dict["key1"]
print(dict) # {'key2': 200, 'key3': 300, 'key4': 400}  

# 딕셔너리 크기 확인
print(len(dict)) # 3

# 특정 키 존재 여부 확인
print("key1" in dict) # False
print("key2" in dict) # True

✔️ 셋

중복되지 않은 요소들의 모임을 나타내는 자료구조로 파이썬에선 set()을 활용한다. (해시테이블 기반)

# 셋 선언
s1 = set()
s2 = set()

# 원소 추가
s1.add(10)
s1.add(20)
s1.add(30)
s1.add(40)

s2.add(10)
s2.add(11)
s2.add(22)
s2.add(33)
s2.add(44)

# 셋 출력
print("s1:", s1)  # s1: {40, 10, 20, 30}
print("s2:", s2)  # s2: {33, 10, 11, 44, 22}
print()
# 원소 삭제
s1.remove(20)
print("20 삭제 후 s1:", s1) # 20 삭제 후 s1: {40, 10, 30}

# 원소의 존재 여부 확인
print(33 in s1) # False
print(33 in s2) # True

# 집합의 크기 확인
print(len(s1), len(s2)) # 3, 5

# 합집합 연산
s3 = s1 | s2
print("s1과 s2의 합집합:", s3)  # s1과 s2의 합집합: {33, 40, 10, 11, 44, 22, 30}

# 교집합 연산
s3 = s1 & s2
print("s1과 s2의 교집합:", s3) # s1과 s2의 교집합: {10}
 
# 차집합 연산
s3 = s1 - s2
print("s1과 s2의 차집합:", s3) # s1과 s2의 차집합: {40, 30}

✔️ 스택

stk = [10,20,30]
stk.append(40)

print(stk)
print(stk[-1])

print(stk.pop())
print(stk)

✔️ 큐

선입선출 선형 자료구조이고 파이썬에선 deque 사용

from collections import deque

# 큐 선언
q = deque()

# 맨 뒤에 원소 삽입
q.append(10)
q.append(20)
q.append(30)

# 큐 출력
print("큐:", q)
print()

# 맨 앞의 원소 삭제
removed_element = q.popleft()
print("삭제된 원소:", removed_element)
print("삭제 후 큐:", q)
print()

# 맨 앞의 원소 확인
front_element = q[0]
print("맨 앞의 원소:", front_element)
print("현재 큐:", q)
print()

# 큐의 크기 확인
print("큐의 크기:", len(q))
print()

# 특정 값의 존재 여부 확인
print(10 in q)
print(20 in q)
print()

# 큐 순회
while q:
    print(q.popleft(), end=' ')

✔️ 우선순위큐

1) 최소힙

from queue import PriorityQueue

pq = PriorityQueue()

# 우선순위 큐 삽입
pq.put(10)
pq.put(20)
pq.put(30)
pq.put(40)

# 우선순위 큐 출력
print(pq.queue) # [10, 20, 30, 40]

# 우선순위가 가장 높은 원소 = 최상위 원소 삭제
print(pq.get()) # 10
print(pq.queue) # [20, 40, 30]

# 삭제하지 않고 최상위 원소 확인
print(pq.queue[0])

# 우선순위 큐가 비어있는지 확인
print(pq.empty()) # False

# 우선순위 큐 그냥 순회
for u in pq.queue:
    print(u, end=" ") # 20 40 30
print()

# 우선순위 큐 우선 순위대로 순회
while pq.queue:
    print(pq.get(), end=" ") # 20 30 40

2) 최대힙

최대힙 같은 경우 따로 라이브러리에서 지원하지 않기 때문에 앞에 원소값에 -를 표시하고 실제로 쓰는 값은 그 뒤에 값을 사용하면 된다.

from queue import PriorityQueue

# 우선순위 큐 선언
pq = PriorityQueue()

# 원소 삽입
pq.put([-40, 40])  # (우선 순위, 값)을 의미
pq.put([-30, 30])
pq.put([-20, 20])
pq.put([-10, 10])

# 우선순위 큐 출력
print("우선순위 큐:", pq.queue)
print(pq.queue)
print()

# 최상위 원소 삭제 (우선순위가 가장 높은 원소를 삭제)
removed_element = pq.get()
print("삭제된 원소:", removed_element)
print("실제 쓸 값:", removed_element[1])
print("삭제 후 우선순위 큐:", pq.queue)
print()

# (삭제하지 않고) 최상위 원소 확인
top_element = pq.queue[0]
print("최상위 원소:", top_element)
print("현재 우선순위 큐:", pq.queue)
print()

# 우선순위 큐의 크기 확인
print("우선순위 큐의 크기:", len(pq.queue))
print()

# 우선순위 큐가 비어 있는지 확인
print("우선순위 큐가 비어 있는지 확인:", pq.empty())
print()

# 우선순위 큐 그냥 순회
for u in pq.queue:
    print(u, end=' ')
print()
print()

# 우선순위 큐 순회 (우선순위 대로 순회)
while pq.queue:  # not pq.empty()
    print(pq.get(), end=' ')