트리, 그래프, DFS, BFS, Dynamic Programming

10:00 ~ 10:50
쉽게 배우는 알고리즘 트리-1, 2

• 트리는 비선형 구조, 선형 구조: 스택, 큐 등
  

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

이진트리
---o Level 0
-o---o Level 1
o---o-o Level 2

완전이진트리

• 왼쪽부터 한칸씩 모두 채워야 함, 따라서 배열로 표현이 가능
• 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 None
  ---8 Level 0 -> [None, 8]
  -6---3 Level 1 -> [None, 8, 6, 3]
  4-2-5-- Level 2 -> [None, 8, 6, 3, 4, 2, 5]
  

2 or 5 등의 자리가 비어있다면 완전이진트리가 아님

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

이진 트리의 최대 높이는 O(log(N))

11:00 ~ 13:00
쉽게 배우는 알고리즘 힙
답안

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):
        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        prev_max = self.items.pop()        # pop 익숙해지기
        cur_index = 1
        length = len(self.items) - 1
        max_index = cur_index
        while cur_index <= length:
            if cur_index * 2 <= length and self.items[cur_index] < self.items[cur_index * 2]:
                self.items[cur_index], self.items[cur_index * 2] = self.items[cur_index * 2], self.items[cur_index]
                max_index = cur_index * 2
            if cur_index * 2 + 1 <= length and self.items[cur_index] < self.items[cur_index * 2 + 1]:
                self.items[cur_index], self.items[cur_index * 2 + 1] = self.items[cur_index * 2 + 1], self.items[cur_index]
                max_index = cur_index * 2 + 1
            if cur_index == max_index:
                break
            cur_index = max_index
        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]

나의 답

last_index = len(self.items)-1  # -1과 같은 의미, 끝값을 표현할 때는 -1로 표현
        index=1
        if self.items[index] is None: # 개인적으로 값이 없을 때도 고려
            return "가져올 값이 없습니다"
        else:
            self.items[index], self.items[last_index] = self.items[last_index], self.items[index]
            Max_data = self.items[last_index]
            self.items[last_index] = None
            while index * 2 < len(self.items)-1:
                if self.items[index] < self.items[index * 2] and self.items[index] < self.items[index * 2 + 1]:
                    if self.items[index * 2] > self.items[index * 2 + 1]:
                        self.items[index], self.items[index * 2] = self.items[index * 2], self.items[index]
                        continue
                    else:
                        self.items[index], self.items[index * 2 + 1] = self.items[index * 2 + 1], self.items[index]
                        continue
                elif self.items[index] < self.items[index * 2]:
                    self.items[index], self.items[index * 2] = self.items[index * 2], self.items[index]
                elif self.items[index] < self.items[index * 2 + 1]:
                    self.items[index], self.items[index * 2 + 1] = self.items[index * 2 + 1], self.items[index]
                else:
                    break
        return Max_data

• max_index라는 변수를 사용하면 코드를 확실히 단순하게 진행시킬 수 있다.
• index 마지막 값은 -1로 표기하는 것이 훨씬 간단하다.

14:00 ~ 14:50
쉽게 배우는 알고리즘 그래프
그래프는 바로 연결 관계에 초점
노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

유방향 노드(a)와 무방향 노드(b)

그래프를 표현하는 방법
1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현: 시간 단축
1. 이를 인접 행렬, 2차원 배열로 나타내면 다음과 같습니다!

-	0	1	2	3
0	X	O	X	X
0	O	X	O	X
0	X	O	X	O
0	X	X	O	X

graph = [
    [False, True, False, False],
    [True, False, True, False],
    [False, True, False, True],
    [False, False, True, False]
]

2) 인접 리스트(Adjacnecy List): 링크드 리스트로 그래프의 연결 관계를 표현: 공간 단축
0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2

graph = {
    0: [1],
    1: [0, 2]
    2: [1, 3]
    3: [2]
}

15:00 - 21:00
쉽게 배우는 알고리즘 DFS & BFS & Dynamic Programming
DFS(Depth-First Search): 끝에 도달할 때까지를 반복하여 탐색하는 방법

• visited라는 배열 활용
• 순서

1. 루트 노드부터 시작한다.
2. 현재 방문한 노드를 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4. 2부터 반복한다.

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]
}
visited = []
def dfs_recursion(adjacent_graph, cur_node, visited_array):
    visited_array.append(cur_node)
    for adjacent_node in adjacent_graph[cur_node]:  # 이건 생각치도 못했다. 재귀하여 다시 열린 for문에서 if가 돌든 안 돌든 adjacent_node만 다 돌면 이전 재귀의 for문으로 돌아간다..
        print(adjacent_node)
        if adjacent_node not in visited_array:
            dfs_recursion(adjacent_graph, adjacent_node, visited_array)
    return visited_array
dfs_recursion(graph, 1, visited)  # 1 이 시작노드입니다!
print(visited)

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):
    visited = []
    stack = [start_node]
    while stack:        # stack이 모두 비워지면 자동적으로 False 나옴.. 와
        cur_node = stack.pop()
        visited.append(cur_node)
        for adjacent_node in adjacent_graph[cur_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited
print(dfs_stack(graph, 1))

BFS(Breadth-First Search): 인접한 곳부터 우선적으로 탐색하는 방법

• queue를 활용

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}
def bfs_queue(adj_graph, start_node):
    visited = []
    queue = [start_node]
    while queue:
        cur_node = queue.pop(0)
        visited.append(cur_node)
        for adj_node in adj_graph[cur_node]:
            if adj_node not in visited:
                queue.append(adj_node)  # 방문하지 않은 노드를 추가
    return visited
print(bfs_queue(graph, 1))

Dynamic Programming
피보나치 수열

input = 20
def fibo_recursion(n): # Top Down 방식: 재귀로 해당 하는 값을 얻기 전까지 아래 메소드가 열리고 열리고 열리고 열리고~~~~ 하다가 끝에 도달 하면 거기서 부터 값을 가져 와서 닫히고 닫히고 닫히고~~~~~ 진행
    if n == 1 or n == 2:
        return 1
    print(n)
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)
print(fibo_recursion(input))

피보나치 수열 with Dynamic Programming

input = 100
memo = {
    1: 1,
    2: 1
}
def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        print(fibo_memo[n])
        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))

• DP 없이 계산하면 했던 계산을 반복하기 때문에 시간 낭비가 상당하다.
• 두 번째 코드처럼 계산한 값을 그때 그때 저장해 두었다가 다시 사용하면 시간을 매우 아낄 수 있다.