TIL 11. 트리, 힙, 그래프, DFS & BFS, D.P.

트리

트리는 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형구조다.
폴더처럼 계층 또는 망 형식으로 구성되고 표현에 초점이 맞춰져 있다.

반대로, 선형구조는 스택, 큐와 같이 하나하나 순서대로 위치한 것이며 자료저장과 꺼내는 것에 맞춰져 있다.

---

트리의 용어

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

---

트리의 종류에는 여러가지가 있지만, 그 중 이진트리와 완전 이진트리만 보자면,
이진트리는 각 노드가 최대 두 개의 자식만 가진다. 0개, 1개 또는 2개의 자식만 있어야 한다.
완전 이진트리는 각 노드가 최대 두 개의 자식을 가지면서, 가장 왼쪽부터 차례대로 노드가 채워져야 한다.

트리를 구성할 때는 편의를 위해 0번째 인덱스는 사용되지 않는다.
그러므로 [None, ... , ..., .....]으로 구성된다.
예를 들어, 가장 위 노드가 9, 그 아래는 5와 6, 5아래는 1과 2, 6아래는 3과 4 일 때,
이걸 배열로 나타내보면 [None, 9, 5, 6, 1, 2, 3, 4]가 된다.

완전 이진 트리의 높이는 가장 아래 노드(leaf node)위치 - 가장 상위 노드(root node)위치이다.
ex) [None, 1, 2, 3, 4]는 2 - 0 이므로 높이는 2다.
각 레벨에 노드가 꽉 차있다면 몇 개가 있는지도 알 수 있는데, k = level이라면 2^k가 해당 레벨의 노드 개수다.

힙

힙은 데이터에서 최대값, 최소값을 빠르게 찾기 위해 만들어진 완전 이진 트리다.
max힙은 큰 값이 상위에, 작은 값이 하위에 있어야 한다.
즉, 부모 노드의 값이 자식 노드에 비해 커야한다.
min힙은 그 반대로 작은 값이 상위에, 큰 값이 하위에 있어야 한다.

그래프

그래프도 비선형구조이다. 연결관계라는 표현에 맞춰져 있기 때문이다.
노드와 노드를 연결한 선을 간선(Edge)라고 하며, 어떤 한 노드와 간선으로 직접 연결된 노드를 인접노드라고 한다.

그래프는 방향이 있는 간선을 갖는 유방향 그래프, 방향이 없는 간선을 갖는 무방향 그래프가 있는데,
유방향은 한 방향으로만 진행할 수 있고, 무방향은 방향 따위가 없다.

DFS & BFS

DFS, BFS는 자료 검색, 그래프 탐색을 하는 방법이다.
DFS는 탐색하는 경우의 수의 다음에 경우의 수가 있다면, 끝까지 파고 들다가
끝에 다다르면 다시 위로 올라와서 다른 경우의 수를 파고 드는 것이고,
BFS는 탐색하는 경우의 수 다음에 또 다른 경우의 수가 있어도 탐색하지 않고 그 주변의 경우의 수를 탐색하는 것이다.

DFS는 한 가지의 경우의 수만 파고 들기 때문에 그래프의 최대 깊이 만큼의 공간만 요구하지만,
최단 경로를 탐색하기는 쉽지 않다.
BFS는 모든 경로를 다 탐색하다가 다음 경로로 넘어가기에 최단 경로를 쉽게 찾을 수 있지만, 모든 분기의 경우의 수를 다 저장해야해서 공간을 많이 쓰고 모든 경우의 수를 다 탐색하고 오기 때문에 오래걸릴 수도 있다.

Dynamic Programming

• 피보나치 수열
  첫째, 둘째 항은 1이며 그 뒤의 모든 항은, 바로 앞 두 항을 합친 수열이다.
  ex) 1, 1, 2, 3, 5, 8

n번째 피보나치 수를 fibo(n)이라고 표현한다면,
fibo(1)과 fibo(2)는 1이고, fibo(3)은 fibo(1)의 값인 1과 fibo(2)의 값이 2를 더한 3이다.
Fibo(4) 는 Fibo(3) + Fibo(2) = 2 + 1 = 3
Fibo(5) 는 Fibo(4) + Fibo(3) = 3 + 2 = 5
Fibo(6) 은 Fibo(5) + Fibo(4) = 5 + 3 = 8 .....
결국 Fibo(n) 은 Fibo(n - 1) + Fibo(n-2)다.

재귀함수로 표현하면 아래처럼 된다.

input = 20


def fibo(n):
    if n == 1 or n == 2:
        return 1
    return fibo(n - 1) + fibo(n - 2)