파이썬으로 자료구조 구현하는 방법

참고: 파이썬 자료구조 15min, 파이썬으로 자료구조 구현하기

코드

실습 링크: Colab 코드 - [Python] 자료구조

1. 배열

• []

2. 리스트

• []
• list.append(num)

3. 해시셋

• set()
• {num}
• set.add(num)
• set.remove(num)

4. 해시맵

• dict()
• {key: value}
• dict.get(key) = value
• dict[key] = value
• key in dict; boolean
• dict.keys()
• dict.values()
• dict.items()
• len(dict)

5. 스택

• []
• list.append(num)
• list.pop() - LIFO (Last In First Out)

6. 큐

• deque()
• collections
• q.append(num)
• q.popleft() - FIFO (First In First Out, 선입선출, 줄서기)

7. 힙(우선순위 큐)

• heapq
• []
• heapq.heappush(list, num)
• heapq.heappop(list) - 최솟값 뱉어낸 후 값 삭제
• heapq.heapify(list) - 주어진 배열을 '힙' 구조로 변환

8. 이진 트리

• Node 정의
• Node의 left, right 노드 정의

9. 그래프

1) matrix (2차원 배열) [[]]로 정의하는 방법 -> [[0, 0, 0], [0, 0, 0]]
2) {} 안에 list [] 로 정의하는 방법 -> {0: [1, 2, 4], 1: [1, 3]}

• 튜플 (num, weight) 형식으로 가중치 추가 가능
  -> {0: [(1, 1), (1, 2)], 1: [(0, 1), (1, 3)]}

heap (우선순위 큐) 함수

heappush(arr, num) 원리

1. 이진 트리의 가장 아래쪽 단계의 비어있는 자리에(왼쪽부터 채워넣어야 함, 힙의 규칙) num을 집어넣는다.
2. 해당 num이 자신의 부모노드와 비교하여 작으면 부모노드와 자리를 switch한다.
3. 이 과정을 반복하여 부모노드보다 크거나 같으면 그대로 둔다.

ex)

import heapq

heap = []
heapq.heappush(heap, 9)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 2)
heapq.heappush(heap, 6)

print(heap)

따라서 정답은 [2, 3, 5, 9, 7, 6] 이다.

모듈 heapq 함수

파이썬에서는 heapq 모듈은 배열(리스트)을 이용하여 완전 이진트리를 구현한다. 완전 이진트리는 왼쪽부터 빈 공간 없이 차례대로 채워지기 때문에, 배열을 이용하여 효율적으로 관리할 수 있다.

• heappush(arr, data) : 힙 arr에 새로운 데이터를 삽입한다.
• heappop(arr) : 힙 arr에서 루트 노드(최소값)를 꺼낸 후 삭제한다.
• heapify(x) : 주어진 배열을 힙 구조로 변환한다.