SCC Algorithm 4주차

nathan·2021년 3월 29일
algorithmpythonscc
0

SCC Algorithm

목록 보기
7/7

[수업 목표]
1. 트리, 힙의 개념과 활용법에 대해 배운다.
2. 그래프, BFS, DFS 에 대해 배워보자.
3. Dynamic Programming 의 개념과 그 필요성을 배워보자.

1. 트리와 힙

1-1. 트리(Tree)

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

  • 선형구조인 스택, 큐 등은 자료를 저장하고, 꺼내는 것에 초점이 맞춰져 있고,
    비선형구조는 표현에 초점이 맞춰져 있다.

  • 트리를 통해 계층 구조의 데이터를 쉽게 표현할 수 있다.

  • 폴더 구조가 대표적인 트리 구조이다.

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



    참고 : 플랜B의 백엔드 엔지니어링

  • 트리의 종류
    - 이진 트리, 이진 탐색 트리, 균형 트리(AVL, Red-Black트리), 이진 힙(MaxHeap, MinHeap) 등 다양한 트리가 있지만, 여기서는 이진 트리와 완전 이진트리만 다룬다.

    • 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식을 갖는다.
      하위 노드가 무조건 0, 1, 2개 중에 하나여야 한다.
    • 완전 이진 트리(Complete Binary Tree) : 노드를 삽입할 때 최 하단 왼쪽 노드부터 차례대로 삽입해야 한다.

  • 완전 이진 트리를 배열로 표현하기

트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않습니다!
그래서 None 값을 배열에 넣고 시작합니다! [None]

      8      Level 0 -> [None, **8**] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [None, 8, **6, 3**] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [None, 8, 6, 3, **4, 2, 5**] 다음 레벨인 4, 2, 5를 넣으면 됩니다!

자 그러면, [None 8, 6, 3, 4, 2, 5] 라는 배열이 되는데
다시 역으로 이 배열을 활용해서 트리 구조를 분석해보겠습니다.
다음과 같은 방법으로 트리 구조를 파악할 수 있습니다.

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

예를 들어서 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3 입니다.
그러면 1 * 2 = 2번째 인덱스! 6!
그러면 1 * 2 + 1 = 3번째 인덱스! 3! 입니다!
부모를 찾아보면, 3 // 2 = 1번째 인덱스 8 이므로 부모를 찾을 수 있습니다.

이를 다시 생각해보면
[None, 8, 6, 3, 4, 2, 5] 는
8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리구나! 생각할 수 있습니다.
  • 트리의 높이(Height)는 루트 노드부터 가장 아래 리프 노드까지의 길이이다.
      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는 ? 2 - 0 = 2!
  • 만약 각 레벨에 노드가 꽉 차있으면 몇 개가 있을까?
    1, 2, 4, ... 2^k (level k) 즉, 2^(k+1) - 1개가 있다고 할 수 있다.

즉 높이가 h 일 때, 최대 노드의 개수는 2^(h+1) - 1개 이다.
이 때 최대 노드의 개수가 N이라면, h는 어떻게 될까?

2^(h+1) - 1 = N
h = log(N+1) - 1

따라서 완전 이진 트리 노드의 개수가 N개라고 했을 때, 높이가 log(N+1)-1이므로 이진 트리의 높이는 최대로 해봤자 O(log(N))이라고 생각할 수 있다.

1-2. 힙(Heap)

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

(1) Min Heap

(2) Max Heap

  • 힙을 통해 최댓값과 최솟값을 쉽게 뽑을 수 있다.

  • 따라서 최댓값 또는 최솟값을 구해야한다면 힙을 쓰면 된다.

  • 힙을 구현하기 위해서 어떻게 해야할까?
    - 힙은 항상 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있도록 하는 자료구조이다.

    • 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
import heapq

example_heap = []
heapq.heappush(example_heap, 1)
heapq.heappush(example_heap, 5)
heapq.heappush(example_heap, 2)
heapq.heappush(example_heap, 7)

print(example_heap) # [1, 5, 2, 7] 기본적으로 MinHeap의 구조를 띄는 것을 알 수 있다. 만약 MaxHeap으로 구현하기 위해서는 push를 할 때 -1을 곱해서 넣고, pop할 때 다시 붙여서 꺼내면 된다.


heapq.heappop(example)
print(example_heap) # [2, 5, 7]

  • 맥스 힙에 원소 추가하기
    - 우선 전체 배열에 새로운 값을 추가한 후, 그 원소의 인덱스인 len(self.items) - 1부터 시작을 한다.(append로 맨 마지막에 넣었기 때문)
    • 부모 노드의 인덱스는 자식노드 // 2의 인덱스라는 점을 기억하여, 새로운 원소 인덱스부터 부모 노드의 인덱스의 노드와 값을 비교한다.
    • 더 크다면 값을 교체하고 cur_index에 parent_index를 넣는다.
    • 이 과정을 cur_index가 제일 꼭대기 칸, 즉 1이 되기 전까지 반복한다.
...
		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
...

MaxHeap에 원소 추가하기의 시간 복잡도
결국 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있기 때문에, 완전 이진 트리의 최대 높이인 logN 즉, O(logN)만큼의 시간이 걸린다고 볼 수 있다.

  • 맥스 힙에서 원소 제거하기
    - 최댓값, 즉 루트 노드를 삭제하고 나머지를 재정렬하여 준다.
    • 스택과 같이 맨 위의 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없다.
    • 따라서 다음과 같은 방법으로 맥스 힙에서 원소를 제거한다.
      1. 루트노드와 맨 끝에 있는 원소를 교체한다.
      1. 맨 뒤에 있는 원소(원래 루트노드)를 삭제한다.
      1. 변경된 노드와 자식 노드들을 비교한다.
      1. 두 자식 중 더 큰 자식과 비교해서 더 크다면 자리를 바꾼다.
      1. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3, 4의 과정을 반복한다.
          1. 2에서 제거한 원래 루트 노드를 반환한다.
...
def delete(self):
        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        prev_max = self.items.pop()
        cur_index = 1

        while cur_index <= len(self.items) - 1:
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            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

            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

            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index

        return prev_max
...

2. 그래프와 DFS & BFS

2-1. 그래프(Graph)

그래프란?
연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조 [천재학습백과]

  • 그래프는 연결 관계에 초점이 맞춰져 있다.

  • 그래프에서 사용되는 용어들은 다음과 같다.
    - 노드 : 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertex)라고도 한다.

    • 간선 : 노드 간의 관계를 표시한 선.
    • 인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(또는 정점)

  • 본래 그래프의 종류는 유방향 그래프와 무방향 그래프가 있으나 여기서는 무방향 그래프만 다룬다.
    - 유방향 그래프(Directed Graph) : 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다.
    - 무방향 그래프(Undirected Graph) : 방향이 없는 간선을 갖는다.


  • 이런 그래프라는 개념을 컴퓨터에서 표현하는 방법은 두 가지 방법이 있다.
    1) 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현
    2) 인접 리스트(Adjacency List) : 링크드 리스트로 그래프의 연결 관계를 표현

          2 - 3
          ⎜       
      0 - 1

**1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!**
  0  1  2  3
0 X  O  X  X
1 O  X  O  X
2 X  O  X  O
3 X  X  O  X

이걸 배열로 표현하면 다음과 같습니다!
graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

**2. 이번에는 인접 리스트로 표현해보겠습니다!**
인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례대로 다음과 같이 저장합니다.

0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}
  • 두 방식의 차이는 바로 시간VS공간이다.
  • 인접 행렬로 표현하면 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다. 허나 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 한다.
  • 인접 리스트로 표현하면 즉각적으로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다. 따라서 연결 여부를 알기 위해서 최대 O(간선)만큼의 시간을 사용해야 한다. 대신 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드+간선)만큼의 공간을 사용하면 된다.

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

  • DFS : 깊이 우선 탐색

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

  • BFS : 너비 우선 탐색

DFS와 BFS를 배우는 이유?
정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에, 모든 경우의 수를 전부 탐색해야 하는 경우도 있다.
대표적 예시가 알파고이다.
대국에서 발생하는 모든 수를 계산하고 예측해서 최적의 수를 계산해내기 위해 모든 수를 전부 탐색해야 한다.

DFS와 BFS는 그 탐색 순서에 차이가 있다.
DFS는 끝까지 파고드는 것이고, BFS는 갈라진 모든 경우의 수를 탐색해보고 오는 것이다.
DFS는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다.
따라서 공간을 적게 쓰지만, 최단 경로를 탐색하기에는 쉽지 않다.
BFS는 최단 경로를 쉽게 찾을 수 있다. 모든 분기되는 수를 다 보고 올 수 있기 때문이다. 허나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있다.

DFS 구현해보기(with recursion)

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}
visited = []


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(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야 합니다!

단점 : 코드를 보면 한 번 봤던 노드들도 또 확인하고 있음을 알 수 있다.
즉, 재귀함수를 통해서는 무한정 깊어지는 노드가 있는 경우 에러가 생길 수 있다. RecursionError...

DFS 구현해보기(with stack)

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

stack에 쌓아놓고, 해당 stack이 비면 바로 함수를 종료하게 된다.
따라서 재귀함수로 구현한 것보다 빠르게 함수를 끝낼 수 있게 된다.

BFS 구현해보기

3. Dynamic Programming

  • 동적 계획법 : 부분 문제의 해를 통해 전체 문제를 해결하는 방법
  • DP라고 줄여 말하기도 하며, 이 방법론을 통해 많은 알고리즘 문제를 해결할 수 있다.

동적 계획법에 대해 설명하기 전 피보나치 수열을 통해 필요성을 느껴보자.

피보나치 수열이란 첫째 및 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다.

즉, n번째 피보나치 수를 Fibo(n)라고 표현한다면,
Fibo(1) 은 1이고,
Fibo(2) 도 1이다! (첫째 및 둘째 항을 1이라고 정했다!)

Fibo(3) 부터는 이전 값과 이전 이전 값의 합입니다!
즉, Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 = 2 이다.

그러면
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_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)


print(fibo_recursion(input))  # 6765

하지만 꼭 이렇게 모든 경우의 수를 다 해봐야 알 수 있을까?
각 수열별로 얼마의 숫자를 갖고있는지만 알면 되지 않을까?

위의 코드는 이미 실험했던 시간들을 또 다시 반복하며 시간을 낭비하고 있다.

따라서 이런 문제를 해결하기 위해서 동적 계획법(Dynamic Programming)이 탄생했다.

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

결국 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다.

즉, 우리가 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 된다.

F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼,
문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다!

이처럼 문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있다!
그러나 다른 점은, 그 결과를 기록하고 이용한다는 점 이다!

여기서 용어정리 간단하게 해드리겠습니다!

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

memo = {
    1: 1, # Fibo(1) 의 값은 1이라고 기록해둔다.
    2: 1  # Fibo(2) 의 값은 1이라고 기록한다.
}

fibo(3) 을 찾아와라!

1. memo[3]이 있는지 본다.
2. 없으니까 fibo(2) + fibo(1) 을 구해야 한다.
3. 그러면 memo[2] 와 memo[1] 이 있는지 찾아본다.
4. 있으니까 그 값을 가져온 뒤 더해서 fibo(3) 을 만든다.
5. memo[3] 에 fibo(3) 을 기록한다. 

fibo(4) 을 찾아와라!
1. memo[4]이 있는지 본다.
2. 없으니까 fibo(3) + fibo(2) 을 구해야 한다.
3. 그러면 memo[3] 와 memo[2] 이 있는지 찾아본다.
	4. memo[3] 이 없으니까 fibo(2) + fibo(1) 을 구해야 한다.
	5. 그러면 memo[2] 와 memo[1] 이 있는지 찾아본다.
	6. 있으니까 그 값을 가져온 뒤 더해서 fibo(3) 을 만든다.
	7. memo[3] 에 fibo(3) 을 기록한다. 
8. memo[3] memo[2] 를 더해 fibo(4) 를 만들고 memo[4] 에 기록한다.
	
fibo(5) 을 찾아와라!
1. memo[5]이 있는지 본다.
2. 없으니까 fibo(4) + fibo(3) 을 구해야 한다.
3. 그러면 memo[4] 와 memo[3] 이 있는지 찾아본다.
	4. memo[4]가 없으니까 fibo(3) + fibo(2) 을 구해야 한다.
	5. 그러면 memo[3] 와 memo[2] 이 있는지 찾아본다.
		6. memo[3] 이 없으니까 fibo(2) + fibo(1) 을 구해야 한다.
		7. 그러면 memo[2] 와 memo[1] 이 있는지 찾아본다.
		8. 있으니까 그 값을 가져온 뒤 더해서 fibo(3) 을 만든다.
		**9. memo[3] 에 fibo(3) 을 기록한다.** 
	10. memo[3] memo[2] 를 더해 fibo(4) 를 만들고 memo[4] 에 기록한다.
**11. memo[3] 이 있으니까 그 값을 가져온다. (9에서 기록해놨다!!!!)**
12. memo[4] 와 memo[3]을 더해 fibo(5) 를 만들고 memo[5] 에 기록한다. 
	

이렇게 기록한 정보를 이용해서 부분 문제를 해결할 수 있었습니다! 

어떻게 메모이제이션이 효율적으로 이용될 수 있는지 이해가 되셨길 바랍니다.

[스파르타 코딩클럽 자료 첨부]

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))
profile
nathan
나는 날마다 모든 면에서 점점 더 나아지고 있다.
이전 포스트

SCC Algorithm 3주차

0개의 댓글