큐(Queue), 스택(Stack) 은 선형 구조라는 자료구조이다.
선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다.
트리는 위와 다른 비선형 구조로써, 데이터가 계층적 혹은 망으로 구성되어있다.
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,
비선형구조는 표현에 초점이 맞춰져 있다.
Node
: 트리에서 데이터를 저장하는 기본 요소Root Node
: 트리 맨 위에 있는 노드Level
: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄Parent Node
: 어떤 노드의 상위 레벨에 연결된 노드Child Node
: 어떤 노드의 하위 레벨에 연결된 노드Leaf Node(Terminal Node)
: Child Node가 하나도 없는 노드Sibling
: 동일한 Parent Node를 가진 노드Depth
: 트리에서 Node가 가질 수 있는 최대 Level트리의 종류에는 이진 트리, 이진 탐색트리, 균형트리, 이진 힙을 비롯하여 다양한 종류가 있다. 그 중
이진트리
와완전 이진 트리
에 대해서 배웠다.
[None, 8, 6, 3, 4, 2, 5]
라는 배열에서 아래 방법을 통해 쉽게 인덱스에 접근할 수 있다.
Heap
은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)로 Max heap과 Min heap이 있다.
...
def insert(self, value):
self.items.append(value)
cur_index = len(self.items) - 1
while cur_index > 1: # cur_index 가 1이 되면 최상위에 도달한 것이라 멈추도록 설정.
parent_index = cur_index // 2
if self.items[parent_index] < self.items[cur_index]:
self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
cur_index = parent_index
else:
break
...
루트 노드와 맨 끝의 원소를 교체 > 삭제 > 규칙을 준수하는 적합한 위치로 이동 > 맥스 값 반환
순으로 진행하면 됩니다. DFS(Depth First Search) 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구합니다.
따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않습니다.
BFS(Breadth-First Search) 는 최단 경로를 쉽게 찾을 수 있습니다! 모든 분기되는 수를 다 보고 올 수 있으니까요.
그러나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있습니다.
def dfs_recursion(adjacent_graph, cur_node, visited_array):
visited_array.append(cur_node)
for adjacent_node in adjacent_graph[cur_node]:
if adjacent_node not in visited_array:
dfs_recursion(adjacent_graph, adjacent_node, visited_array)
dfs_recursion
함수를 재귀함수로 돌리면서, visited_array
에 방문한 노드들을 기록하는 방식으로 DFS를 구현할 수 있습니다. 그러나 재귀함수를 통해서는 무한정 깊어지는 노드가 있는 경우 에러가 발생할 수 있습니다.
이에 대한 대안으로, 스택을 이용하여 DFS를 구현할 수 있습니다.
graph = {
1: [2, 5, 9],
2: [1, 3],
3: [2, 4],
4: [3],
5: [1, 6, 8],
6: [5, 7],
7: [6],
8: [5],
9: [1, 10],
10: [9]
}
def dfs_stack(adjacent_graph, start_node):
stack = [start_node]
visited = []
while stack:
current_node = stack.pop()
visited.append(current_node)
for adjacent_node in adjacent_graph[current_node]:
if adjacent_node not in visited:
stack.append(adjacent_node)
return visited
print(dfs_stack(graph, 1)) # 1 이 시작노드입니다!
# input 인접리스트 방식의 그래프, 시작노드
def bfs_queue(adj_graph, start_node):
queue = [start_node]
visited = []
while queue:
current_node = queue.pop(0)
visited.append(current_node)
for adjacent_node in adj_graph[current_node]:
if adjacent_node not in visited:
queue.append(adjacent_node)
return visited
input = 20
def fibo_recursion(n):
if n == 1 or n == 2:
return 1
return fibo_recursion(n - 1) + fibo_recursion(n - 2)
print(fibo_recursion(input)) # 6765
위 사진과 같이 했던 일을 또 하고 또 하다보니, input 값이 올라가게 되면 시간초과가 나게 됩니다.
- 컴터를 혼내주려면 위 코드를 돌리셔도 됩니다.
- 이를 해결하기 위한 방법이 바로 DP! 입니다.
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. [위키백과]
결과를 기록하는 것을 메모이제이션(Memoization)
이라고 하고,
문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)
라고 합니다
input = 50
# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
1: 1,
2: 1
}
def fibo_dynamic_programming(n, fibo_memo):
if n in fibo_memo:
return fibo_memo[n]
nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
fibo_memo[n] = nth_fibo
return nth_fibo
print(fibo_dynamic_programming(input, memo))
memo
에 피보나치 값들을 Memoization 하면서 부분문제들을 해결해가는 방식으로 피보나치문제를 빠르게 해결할 수 있습니다.