[TIL] Tree, Heap, DFS&BFS, DP

조성현·2022년 11월 15일
0

Today I Learned [요약]

1. Tree

  • Tree의 기본적인 용어,
  • 이진 트리(Binary Tree)와 완전 이진 트리(Complete Binary Tree),
  • 완전 이진 트리를 배열로 표현하는 법에 대해 배웠다.

2. Heap

  • Max Heap, Min Heap의 개념과 규칙,
  • Max Heap에 원소를 추가, 제거하는 법에 대해 배웠다.

3. 그래프

  • Tree와 같은 '비선형 구조'와 배열 등의 '선형 구조'에 대해 배웠다.
  • 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacnecy List)를 통한 그래프 표현법을 배웠다.

4. DFS & BFS

  • 왜 DFS & BFS 를 배워야 하는지와 DFS & BFS의 차이점,
  • DFS와 BFS를 구현해보며 각각의 구현방법에 대해 배웠다.

5. Dynamic Programming

  • 피보나치 수열 문제를 통해 DP의 필요성에 대해 체감해보았다.
  • 동적 계획법(Dynamic Programming)의 Memoization과 Overlapping Subproblem에 대해 배웠다.
  • 피보나치 수열 문제를 Memoization을 활용해 해결해보았다.

Today I Learned [상세]

1. Tree

  • 큐(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

트리의 종류에는 이진 트리, 이진 탐색트리, 균형트리, 이진 힙을 비롯하여 다양한 종류가 있다. 그 중 이진트리완전 이진 트리에 대해서 배웠다.

이진트리와 완전 이진 트리 (Binary Tree & Complete Binary Tree)

  • 각 노드가 최대 두 개의 자식을 가진다. (공통 규칙)
  • 완전 이진 트리는 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.
  • 이진 트리의 높이는 O(log(N)) 이다.

완전 이진 트리를 배열에 표현하는 법.

  • [None, 8, 6, 3, 4, 2, 5]라는 배열에서 아래 방법을 통해 쉽게 인덱스에 접근할 수 있다.

    1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
    2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
    3. 현재 인덱스 // 2 -> 부모의 인덱스

2. Heap

Heap은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)로 Max heap과 Min heap이 있다.

Max 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
...

Max heap에 원소를 제거하기

  • 힙은 스택과 같이 맨 위에 있는 원소만 제거할 수 있습니다.
  • 따라서 루트 노드와 맨 끝의 원소를 교체 > 삭제 > 규칙을 준수하는 적합한 위치로 이동 > 맥스 값 반환 순으로 진행하면 됩니다.

4. DFS & BFS

DFS(Depth First Search) 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구합니다.
따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않습니다.

BFS(Breadth-First Search) 는 최단 경로를 쉽게 찾을 수 있습니다! 모든 분기되는 수를 다 보고 올 수 있으니까요.
그러나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있습니다.

1) DFS를 재귀함수로 구현해보기

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 이 시작노드입니다!

2) BFS를 재귀함수로 구현해보기

# 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

5. Dynamic Programming

  • 피보나치 수열 문제를 통해 체감해보는 DP의 필요성
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! 입니다.

동적 계획법(Dynamic Programming)이란

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

  • 결과를 기록하는 것을 메모이제이션(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 하면서 부분문제들을 해결해가는 방식으로 피보나치문제를 빠르게 해결할 수 있습니다.

profile
맛있는 음식과 여행을 좋아하는 당당한 뚱땡이

0개의 댓글