트리

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조.
[네이버 지식백과] 트리 [tree] (천재학습백과 초등 소프트웨어 용어사전)

Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level

힙

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로!
따라서 최대의 값들을 빠르게 구할 수 있다.

참고로, 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고,
최솟값을 맨 위로 올릴 수도 있다!

최댓값이 맨 위인 힙을 Max 힙,
최솟값이 맨 위인 힙을 Min 힙.

DFS & BFS

DFS

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]

BFS

한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. [컴퓨터인터넷IT용어대사전]

Dynamic Programming

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. [위키백과]

동적 계획법은
여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘.

결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고,
문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 함.

각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것을 겹치는 부분 문제, 이미 실험했던 내용은 기록해두고 쓰면 된다는 것을 메모이제이션.

몰랐던 개념

pop(0)

보통 리스트에서 list.pop()하면 리스트의 맨 뒤 원소를 삭제하고 해당 값을 반환하는데,
list.pop(0)을 하면 맨 앞의 원소를 삭제하고 해당 값을 반환한다.
해당 기능을 이용하면 리스트로 queue 자료구조 구현 가능

>>> queue = ['a', 'b', 'c']
>>> print(queue.pop(0))
a
>>> print(queue.pop())
c

heapq 모듈

Heap : 원할 때 언제든지 최솟값과 최댓값을 뽑을 수 있게 만든 자료구조
heap 이용하고 싶을 때는 heapq 모듈을 이용하면 됩니다.

우리가 만들었던 힙 구조를 유지하면서
원소를 추가하고 삭제하는 기능들을 다 구현!
기본적으로 minheap이다.

>>> import heapq # heapq 를 사용하기 위해서는 맨 위에 heapq 를 가져온다! 라는 구문을 써주셔야 합니다.

>>> heap = []
>>> heapq.heappush(heap, 4)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 7)
>>> heapq.heappush(heap, 3)
>>> print(heap)
[1, 3, 7, 4] # 힙의 형태를 유지한채로 원소가 넣어지기 때문에 heap[0]이 최솟값입니다!

>>> print(heapq.heappop(heap)) # 최솟값을 빼는 방법입니다.
1
>>> print(heap)
[3, 7, 4] # 마찬가지로 힙의 형태가 유지됩니다.

✅ 최댓값을 구하고 싶다면!

음수를 이용하면 됩니다.

-1 을 곱해서 넣고, 뺄 때도 -1을 곱한다면?
최솟값을 기준으로 정렬한다는 점을 이용해서 최댓값을 저장할 수 있습니다!

>>> import heapq # heapq 를 사용하기 위해서는 맨 위에 heapq 를 가져온다! 라는 구문을 써주셔야 합니다.

>>> heap = []
>>> heapq.heappush(heap, 4 * -1)
>>> heapq.heappush(heap, 1 * -1)
>>> heapq.heappush(heap, 7 * -1)
>>> heapq.heappush(heap, 3 * -1)
>>> print(heap)
[-7, -3, -4, -1] # 힙의 형태를 유지한채로 원소가 넣어지기 때문에 heap[0]이 최솟값입니다!

>>> print(heapq.heappop(heap) * - 1) # 최댓값을 빼는 방법입니다.
7
>>> print(heap)
[-4, -3, -1] # 마찬가지로 힙의 형태가 유지됩니다.