자료구조, 알고리즘 4주차: 완전이진트리, 힙, DFS&BFS, Dynamic Programming

이번 주에는 최댓값이나 최솟값을 빠르게 구하기 위한 완전이진트리인 힙 Heap에 대해 중점적으로 배웠다.

그리고 그래프 자료구조인 DFS와 BFS도 배웠고,

문제를 쪼개서 정의할 때 쓰는 동적계획법 Dynamic Programming에 대해서도 배웠다.

 

1. 트리 Tree

거꾸로 세워놓은 나무처럼 보이는 게층형 비선형 자료구조.

이 때 비선형 자료구조는 데이터가 망이나 계층적으로 구성되어 있는 것을 말하며, 표현에 초점이 맞춰져 있다.

노드 Node: 트리에서 데이터를 저장하는 기본 요소

Root Node, Level, Parent Node, Child Node, Leaf Node=Terminal Node, Sibling, Depth등의 용어도 쓰인다.

 

2. 이진트리 Binary Tree와 완전이진트리 Complete Binary Tree

이진트리란 각 노드가 최대 두 개의 자식을 갖는 것을 말한다. 다시 말해 자식 노드가 0,1,2 중 하나다.

완전이진트리는 노드를 삽입할 때 최하단 노드부터 차례대로 삽입한 것을 말한다.

완전이진트리를 배열로 표현할 땐 None값을 0번째 인덱스에 넣고 시작한다.

왼쪽 자식 인덱스 = Index  * 2

오른쪽 자식 인덱스 = Index * 2 + 1

부모 인덱스 = Index // 2

또한 완전이진트리의 높이는 루트부터 가장 아래 Leaf Node까지의 길이를 말한다.

모든 노드의 개수는 2^(k+1) -1 개이며,

이를 다시 말하면 완전이진트리의 노드의 개수가 N개라고 할 때 높이는 최대 O(log(N))이라할 수 있다.

 

3. 힙 Heap

힙이란, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전이진트리이다.

큰 값이 상위레벨에, 작은 값이 하위레벨에 있다.

즉, 부모 노드의 값이 자식 노드의 값보다 항상 크다.

맥스힙에 대해 중점적으로 다루자면, 맥스 힙에 원소를 추가하거나, 맥스 힙에 있던 원소를 제거하는 방법은 다음과 같다.

<맥스 힙에 원소 추가>

1. 원소를 맨 마지막에 넣는다

2. 부모 노드와 비교한다. 자식 노드가 더 크다면 자리를 바꾼다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 반복한다.

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        # 원소를 맨 마지막에 넣기
        self.items.append(value) # 우리가 지금 배열로 관리하고 있으니까 따로 new_node만들지 않고 괄호 안에 value를 넣어준다.
        cur_index = len(self.items) - 1 #인덱스 저장법. 가장 마지막에 넣은 노드의 index를 cur_index로 저장한다.
        # 부모 노드와 비교. 자식 노드가 더 크다면 자리를 바꾼다
        while cur_index > 1 : # 꼭대기는 인덱스가 1이므로, cur_index가 1보다 큰 경우까지 반복한다.
            parent_index = cur_index // 2 #부모 인덱스 가져오기
            if self.items[cur_index] > self.items[parent_index]: # cur_index가 부모인덱스보다 클 때 교환
                self.items[cur_index],self.items[parent_index] = self.items[parent_index],self.items[cur_index]
                cur_index = parent_index #교환 후엔 cur_index를 부모 인덱스로 명명한다.
            else:
                break
        # 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 반복한다
        return


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!

<맥스 힙의 원소 제거>

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소(원래 루트 노드)를 삭제한다. 나중에 리턴해야 하므로 따로 저장한다.

3. 변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교하여 자식이 더 크다면 자리를 바꾼다.

4. 자식 노드 둘보다 부모 노드가 크거나, 가장 바닥에 도달하지 않을때까지 반복한다.

5. 2에서 제거한 원래 루트 노드를 리턴한다.

class MaxHeap:
    def __init__(self):
        self.items = [None]

    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

    def delete(self):
        # 1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

        self.items[1], self.items[-1] = self.items[-1], self.items[1]

        # 2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

        prev_max = self.items.pop() # stack의 pop이용해서 맨 뒤 데이터 뽑아 없애기, prev_max라는 이름으로 저장하고 나중에 리턴.

        # 현재 맨 끝에서 올라온 노드가 어느 노드에서 변경하고 있는지 저장하는 벼수
        # 이 인덱스와 자식 노드 인덱스 비교하기
        cur_index = 1 #맨 끝에서 위로 올라온 노드가 어느 노드와 변경하는지 저장해 놓는 변수 cur_index가 필요함

        # 3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
        # 4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.
        while cur_index <= len(self.items) - 1: # 우리가 가진 인덱스를 벗어나지 않을 때까지 반복
            # 왼쪽 자식과 오른쪽 자식 비교
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            # 어떤 애가 더 큰지를 저장하는 max_index
            max_index = cur_index
                                    # 왼쪽 자식이 있는 상황
            if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]:
                # 왼쪽 자식이 현재 노드 인덱스의 값보다 커야지 max_index를 left_child_index로 바꿀 수 있다.
                # cur_index와 비교하는 것이 아니라 max_index와 비교해야 셋 중 가장 큰 값을 알아서 찾아준다.
                max_index = left_child_index

            if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]:
                max_index = right_child_index

            if max_index == cur_index:# 현재 노드가 자식 노드보다 크다는 말. 교체하지 않아도 된다. 탈출조건.
                break

            # 만약 break과정을 거치지 않았다면, 왼쪽 자식과 오른쪽 자식 중 더 큰 녀석을 cur_index에 저장해놓은 상태.
            # cur_index와 max_index를 변경해주기
            self.items[cur_index], self.items[max_index] = self.items[max_index],self.items[cur_index]
            cur_index = max_index
        # 5. 2에서 제거한 원래 루트 노드를 반환합니다.
        return prev_max


max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]

 

4. 그래프 Graph

그래프란 연결되어 있는 정점과 정점과의 관계를 표현할 수 있는 자료 구조이다.

노드Node는 정점Vertex라고도 불린다. 간선Edge는 노드 간의 관계를 표시한 선이다.

표현 방법에는 두 가지가 있다. 인접 행렬과 인접 리스트.

인접 행렬 Adjacency Matrix 은 2차원 배열로 그래프의 연결 관계를 표현한다.

인접 리스트 Adjacency List 는 링크드리스트로 그래프의 연결관계를 표현한다.

 

5. DFS & BFS

DFS와 BFS는 트리나 그래프를 탐색하는 방법이다.

한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고,

끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

모든 경우의 수를 전부 탐색해야 할 때 탐색하는 순서에 차이를 둔 게 DFS와 BFS다.

<DFS Depth First Search>

끝까지 파고들기.

갈 수 있는 만큼 계속 가다가, 갈 수 없게 되면 다른 방향으로 다시 탐색한다.

즉, 재귀함수를 쓴다. DFS node = node + DFS node와 인접하지만 방문하지 않은 다른 node.

방문하지 않은 조건을 알기 위해  visited라는 배열에 방문한 노드를 기록해야 한다.

1. 루트 노드부터 시작

2. 현재 방문한 노드를 visited에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.

4. 2부터 반복

def dfs_recursion(adjacent_graph, cur_node, visited_array):
    #1. 시작노드(루트노드)인 1부터 탐색
    #2. 현재 방문한 노드를 visited_array에 추가한다.
    visited_array.append(cur_node)
    #3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
    #visited_array = [1]
    for adjacent_node in adjacent_graph:
        if adjacent_node not in visited_array: #탈출조건
            dfs_recursion(adjacent_graph, adjacent_node,visited_array)

하지만 이 방법은 오류를 일으킬 수 있다.

따라서 스택으로 가장 마지막 노드만 꺼내서 탐색하는 방법을 쓰는 것이 낫다.

1. 루트 노드를 스택에 넣는다.

2. 현재 스택의 노드를 빼서 visited에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.

4. 2부터 반복

5. 스택이 비면 탐색을 종료한다.

def dfs_stack(adjacent_graph, start_node):
    # 1. 시작 노드를 스택에 넣는다
    stack = [start_node]
    visited = []

    #2. 현재 스택의 노드를 빼서 visited에 추가한다
    #3. 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가한다.
    while stack:
        current_node = stack.pop()
        visited.append(current_node) # [1]
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited

 

<Breadth First Search>

갈라진 모든 경우의 수를 탐색해보고 오는 것.

현재 인접한 노드 먼저 방문한다.

즉 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,

가장 처음에 넣은 노드를 꺼내서 탐색한다.

가장 처음에 넣은 노드... 즉 큐Queue를 이용해야 한다.

1. 루트 노드를 큐에 넣는다.

2. 현재 큐의 노드를 빼서 visited에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복

5. 큐가 비면 탐색을 종료한다.

def bfs_queue(adj_graph, start_node):
    # 1. 시작 노드를 큐에 넣는다.
    queue = [start_node]
    visited = []
    # 2. 현재 큐의 노드를 빼서 visited에 추가한다
    # 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 queue에 추가한다
    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

 

6. 동적계획법 Dynamic Programming

다이나믹 프로그래밍은 여러 하위 문제를 풀고 그 결과를 기록하고(Memoization) 이용해 문제를 해결하는 알고리즘이다.

문제를 쪼개서(Overlapping Subproblem) 정의할 수 있을 떄 사용한다.

대표적인 예로 피보나치 수열이 있다. Fibo(1) = Fibo(2) = 1, Fibo(n) = Fibo(n-1) + FIbo(n-2)

즉 재귀함수로 풀어야 하는 문제다.

1. 메모용 데이터 fibo-memo를 만든다.

처음 값인 Fibo(1)과 Fibo(2)는 각각 1씩 넣어 저장한다.

2. Fibo(n)을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.

3. Fibo(n)을 처음 구했다면 메모에 그 값을 기록한다.

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

이로써 4주차도 끝!

이제 한 주 더 남았다!

오늘은 타임어택이 있는 날인데... 이번 3,4주차에서 배운 스택, 큐, 힙을 잘 써먹을 수 있었으면 좋겠다.