4. 큐(Queue)
- 선형데이터 구조
- FIFO(First In First Out), 먼저 입력된 것이 먼저 삭제됨.(먼저 입력된 소비자가 먼저 서비스를 받는다.)
- 데이터의 한쪽에서는 입력, 다른 한쪽에서 삭제 발생
- 데이터의 시작부분: front, 데이터의 끝부분: Rear
- 한번에 하나의 데이터만 처리가능
#리스트로 구현
queue = []
queue.append(10)
queue.append(7)
queue.append(5)
queue.append(8)
print(queue) #10, 7, 5, 8
queue.pop(0)
print(queue) #7, 5, 8
queue.pop(0)
print(queue) #5, 8
#Node 이용해 구현
class Node :
def __init__(self, data) :
self.data = data
self.next = None
class Queue :
def __init__(self) :
self.front = None
self.rear = None
def printQueue(self) :
tmp = self.front
while tmp :
print(tmp.data, end = ", ")
tmp = tmp.next
def enqueue(self, new_data) :
if self.front == None :
new_node = Node(new_data)
self.front = new_node
self.rear = new_node
else:
new_node = Node(new_data)
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.front == None :
print("빈 큐입니다.")
elif self.front == self.rear :
self.front = None
self.rear = None
else :
self.front = self.front.next
q = Queue()
q.enqueue(10) #10
q.enqueue(7) #10, 7
q.enqueue(5) #10, 7, 5
q.dequeue() #7, 5
q.dequeue() #5
q.dequeue() #
q.dequeue() #빈 큐입니다.
q.printQueue()
#collections 모듈 이용해 구현
from collections import deque
q = deque()
q.append(10)
q.append(5)
q.append(7)
print(q)
q.popleft()
print(q)5. 그래프(Graph)
- 비선형 데이터구조
- 정점(Vertex = Node)과 간선(Edge)로 이루어진 데이터구조
- 사이클(순환)이 없는 그래프를 트리라고 함.(간선이 끊겨 있음)
- 방향 그래프, 무방향 그래프로 구분함.
~무방향 그래프: (1, 2) 와 (2, 1)은 동일함. -> vertex1과 vertex2를 이은 edge
- 데이터의 추가, 삭제가 용이함.
- 데이터간에 충돌이 발생 할 수 있음.
#인접행렬 vs 인접리스트
Vertex 집합 V = {1, 2, 3, 4, 5}
Edge 집합 E = { (1,2), (1,3), (2,3), (2,5), (2,4), (3,4), (4,5) }
- 인접행렬
N = [[0,1,1,0,0], [1,0,1,1,1], [1,1,0,1,1,0], [1,0,0,0,1,0], [1,1,1,0,0,0], [0,1,1,1,1,0]]
- 인접리스트
graph = {
1:[2,3],
2:[1,3,4, 5],
3:[1,2,4],
4:[2,3,5],
5:[2,4]
}
| 연산 | 인접행렬 | 인접리스트 |
| Vertex 삽입 | Vertex를 삽입하기 위해서는 2차행렬을 읽어야 한다. O(𝑛²) | Head 또는 tail 앞 뒤에 삽입한다. O(1) |
| Edge 삽입 | 행렬[i][j] = 1 이므로 O(1) | Vertex 삽입과 동일함 O(1) |
| Vertext 삭제 | 2차행렬을 읽어야 한다. O(𝑛²) | 삭제할 vertex를 탐색하는 시간이 소요됨. O(n) |
| Edge 삭제 | 행렬[i][j] = 0 이므로 O(1) | 삭제할 edge를 탐색하는 시간 이 소요됨. O(n) |
# 그래프 순회(깊이, 너비)
- 주어진 어떤 vertex에서 출발하여 체계적으로 그래프의 모든 vertex를 탐색
- 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search)
①깊이 우선 탐색(DFS)
- 무방향 그래프 G = (V, E) 일 때 임의 vertex i에서 DFS 수행.
~ i를 방문
~ i에 인접한 vertex중에서 아직 방문하지 않은 vertex는 모두 ★stack 에 저장
~ stack에서 vertex를 삭제하여 새로운 i를 설정하고 다시 첫단계부터 진행함.
~ stack이 공백이 되면 탐색 종료.
~ 방문한 i는 보관해야 한다.
#stack : 리스트의 append(), pop() 이용
graph = {
1: [2,3],
2:[1,3,4,5],
3:[1,2,4],
4:[2,3,5],
5:[2,4]
}
def dfs(graph, start) :
visited = []
stack = [start]
while stack :
n = stack.pop()
if n not in visited :
visited.append(n)
#방문하지 않은 인접 노드를 스택에 추가
stack = stack + list(set(graph[n]) - set(visited)) #차집합을 이용하기 위해 list를 set으로 형변환한 후 다시 list로 형변환
return visited
print(dfs(graph, 1))
②너비 우선 탐색(BFS)
- 무방향 그래프 G = (V, E) 일 때 임의 vertex i에서 BFS 수행.
~ i를 방문
~ i에 인접한 vertex중에서 아직 방문하지 않은 vertex는 모두 ★queue 에 저장
~ Queue에서 vertex를 삭제하여 새로운 i를 설정하고 다시 첫단계 실행
~ Queue가 공백이 되면 탐색 종료.
~ 방문한 i는 보관해야 한다.
#queue : append(), pop(0) 이용
graph = {
1: [2,3],
2: [1,3,4,5],
3: [1,2,4],
4: [2,3,5],
5: [2,4]
}
def bfs(graph, start) :
visited = []
queue = [start]
while queue :
n = queue.pop(0)
if n not in visited :
visited.append(n)
#방문하지 않은 인접 노드를 큐에 추가
queue = queue + list(set(graph[n]) - set(visited))
return visited
print(bfs(graph, 1)) #[1, 2, 3, 4, 5]6. 트리(Tree)
- 비선형 데이터구조
- 노드로 구성된 ★계층적 구조
- 최상위노드(루트, Root)에서 아래로 자식노드를 추가하는 방식
~ 루트는 1개
- 노드와 노드를 잇는 선: Edge
- 같은 레벨(계층)에 있는 노드: 형제노드(Silblings)
- 자식이 없는 노드: 단말노드(Terminal) 또는 리프(Leaf)
- 깊이 : 루트에서 특정노드까지의 거리
- 높이 : 해당노드에서 트리의 가장 깊은 노드까지의 거리
- 컴퓨터의 파일 시스템 형식이 트리구조임.
- 트리의 노드 탐색은 중위 탐색, 후위 탐색, 전위 탐색으로 구분됨.
- 트리를 탐색하면서 각 노드를 선형구조로 만들 수 있음.
#★이진트리
- 부모 노드 하나에 자식 노드 2개를 가짐.
~ 데이터부
~ 왼쪽자식 주소부
~ 오른쪽자식 주소부
- 이진트리 레벨(동일 계층) i에서 노드의 최대수는 2𝑖
~ 루트는 레벨 0. 루트 노드 1개
~ 레벨 1 일경우 노드의 최대수는 2개
~ 레벨 2 일경우 노드의최대수는 4개
- 높이가 h인 이진트리 최대노드수는 2ℎ-1
~ 높이가 증가하면, 1 + 2 + 4 + 8… + 2ℎ-1
- N개의 노드가 있는 이진트리에서 가능한 최소높이는 𝑙𝑜𝑔2(𝑁+1)
class Node :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left= Node(8)
root.left.left.right= Node(9)#순회 : inorder(중위탐색), postorder(후위탐색), preorder(전위탐색)
① Inorder(중위탐색) : 왼쪽 → root → 오른쪽 방식으로 순회
- 왼쪽 서브트리를 중위 탐색한다.(왼쪽노드가 있으면 왼쪽 리프까지 탐색)
- 루트 노드를 방문한다.
- 오른쪽 서브트리를 중위 탐색한다.
② Postorder(후위탐색) : 왼쪽 → 오른쪽 → root 방식으로 순회
- 왼쪽 서브트리를 후위 탐색한다.
- 오른쪽 서브트리를 후위 탐색한다.
- 루트 노드를 방문한다.
class Node :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
def postorder(root) : #왼쪽 -> 오른쪽 -> 루트
if root :
postorder(root.left)
postorder(root.right)
print(root.data, end = ', ')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left= Node(8)
root.left.left.right= Node(9)
postorder(root)
③ Preorder(전위탐색) : root → 왼쪽 → 오른쪽 방식으로 순회
- 루트 노드를 방문한다.
- 왼쪽 서브트리를 전위 탐색한다.
- 오른쪽 서브트리를 전위 탐색한다.
class Node :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
def preorder(root): #루트 -> 왼쪽 -> 오른쪽
if root :
print(root.data, end = ', ')
preorder(root.left)
preorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left= Node(8)
root.left.left.right= Node(9)
preorder(root)#그래프 vs 트리
| 비교 기준 | 그래프 | 트리 |
| 개념 | 비선형 구조 | 비선형 구조 |
| 구조 | Vertex(node)와 edge 집합 | Node와 edge의 집합 |
| Edgd | 각각의 vertex는 서로 다른 edge를 가짐 | N개의 노드면 n-1개의 edge를 가짐 |
| Edgd 형태 | 방향성, 무방향성 | 항상 방향성(부모-자식) |
| Root 노드 | 없음 | 존재함 |
| ★탐색 방법 | DFS, BFS | inorder, preorder, postorder |
| 사이클 | 사이클이 존재할 수 있음 | 사이클이 존재하지 않음 |
'파이썬(PYTHON) > 자료구조' 카테고리의 다른 글
| [Python] 자료구조 - 스택 (0) | 2022.08.20 |
|---|---|
| [Python] 배열, 연결리스트 (0) | 2022.08.13 |
| [Python] 정렬 (0) | 2022.08.07 |
| [Python] 재귀호출, 시간복잡도 (0) | 2022.08.06 |
