[스파르타코딩클럽] 알고리즘 4주차

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

트리

뿌리와 가지로 구성되어 거꾸로 세워 놓은 나무처럼 보이는 계층형 비선형 자료 구조이다.

지난 주에 작성했던 큐와 스택의 자료구조는 선형 구조라고 하는데, 선형구조는 자료를 구성하고 있는 데이터들이 순차적으로 나열된 형태의 구조를 말하는 것이다.

그러나 트리는 비선형 구조이다.
비선형 구조는 데이터가 계층적 혹은 망으로 구성되어 있는 구조 이다.

선형구조와 비선형 구조의 차이점은
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

트리 구조의 가장 대표적인 구조로는 컴퓨터 폴더 구조가 있다.

트리 용어

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

트리의 종류

이진 트리 : (Binary Tree) 각 노드가 최대 두 개의 자식을 가진다. 하위 노드가 무조건 0~2개만 있어야 한다.
완전 이진 트리(Complete Binary Tree) : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것이다.

완전 이진트리를 배열로 저장할 수 있다.
⠀⠀⠀ 8
⠀⠀6⠀⠀ 3
⠀4⠀⠀2⠀⠀5
[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을 넣는다.

현재 인덱스 * 2 = 왼쪽 자식의 인덱스이다.
현재 인덱스 * 2 + 1 = 오른쪽 자식의 인덱스이다.
현재 인덱스// 2 = 부모의 인덱스이다.

완전 이진 트리의 높이

트리의 높이 : 루트 노드부터 가장 아래 리프(Leaf) 노드까지의 길이를 말한다.
⠀
⠀
만약, 각 레벨에 노드가 꽉 차있다면 각 레벨에는 몇개의 노드가 있는 것일까?

완전 이진 트리이기 때문에 각 노드는 2개의 자식 노드만 가질 수 있다.

⠀⠀⠀⠀⠀⠀1⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀level 0 -> 1개
⠀⠀⠀2⠀⠀⠀⠀3⠀⠀⠀⠀⠀⠀⠀⠀⠀level 1 -> 2개
⠀⠀4⠀5⠀⠀6⠀7⠀⠀⠀⠀⠀⠀⠀⠀level 2 -> 4개
⠀8⠀⠀9....14⠀15⠀⠀⠀⠀⠀⠀⠀level 3 -> 8개

레벨을 k라고 하면 각 레벨에는 $2^k$

전체 완전 이진 트리의 노드의 개수는 시그마를 이용해 풀어보면

$1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h$

그러면 최대 노드의 개수가 N이라면, 높이(h)는 어떻게 될까?
=> $2^(h+1) -1 = N$

힙

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전 이진 트리이다.

힙은 항상 큰 값이 위에 있거나 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 그래서 부모 노드의 값이 자식 노드의 값보다 항상 커야 하는 것이다.

⠀⠀⠀⠀8 ⠀⠀⠀⠀⠀Level 0
⠀⠀6⠀⠀⠀3 ⠀⠀⠀Level 1
⠀4 2 ⠀1 ⠀⠀⠀⠀⠀# 자식 노드보다 부모 노드가 크니까 힙이 맞다

++ 힙은 최대값을 맨 윌 올리 수도 있고, 최솟값을 맨 위에 올릴 수도 있다.

Min Heap <=> Max Heap

맥스 힙에 원소 추가

힙의 규칙 : 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨이 있어야 한다.
이 규칙을 지키면서 원소를 추가하거나 삭제해야 한다

방법

원소를 맨 마지막에 넣는다. (맨 왼쪽부터 차례대로)
부모 노드와 비교한다. 만약 추가한 노드가 부모 노드보다 크다면 자리를 바꾼다
부모 노드보다 크지 않을 때까지 이 과정을 반복한다.

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

    def insert(self, value):
        self.items.append(value) # 배열의 마지막에 새 노드를 삽입힌다.
        cur_index = len(self.items) - 1 # 배열의 자리를 변경하기 위해서 각 노드의 index를 알아야 한다.
        while cur_index > 1: 	# 현재 index가 1보다 클 동안 반복한다. 즉, 1이면 가장 최상의 부모 노드이면 반복을 멈춘다.
            parent_index = cur_index // 2 	# 부모 노드는 현재 노드의 index의 2를 나누면 알 수 있다. 
            if self.items[cur_index] > self.items[parent_index]:	# 현재 노드가 부모 노드보다 크다면, 
                self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]	# 그 자리를 변경한다.
                cur_index = parent_index	# 변경하고 현재의 index를 부모의 index번호로 변경한다. 
            else:
                break 	# 만약 크지 않다면 반복문을 빠져나간다.


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]

맥스 힙의 원소를 추가하는 동작의 시간 복잡도는 가장 큰 값을 넣었을 때 완전 이진 트리의 꼭대기까지 올라간다고 보았을 때 이진 트리의 높이만큼의 시간 복잡도가 걸린다고 생각하면 됨으로 $O(log(N))$

맥스 힙의 원소 제거

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.
즉, 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수 없다!!

힙이라는 자료 구조가 원래 최댓값, 최솟값만 찾아내는 구조이기 때문에 가장 최상의 노드만 제거할 수 있게 된다.

그래서, 루트 노드를 삭제할 수 있다!

방법

루트 노드와 맨 끝에 있는 원소를 교체한다.
맨 뒤에 있는 노드를 삭제한다.
변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 과정을 반복한다.
원래의 루트 노드를 반환한다.

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] # -1 => 마지막 노드를 의미
        prev_max = self.items.pop()     # 루트 노드를 pop()을 이용해 배열에서 삭제 후 변수에 저장해 둔다.
        cur_index = 1   # 비교해야 할 노드의 index 를 저장해둔다.

        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    # 왼쪽 노드의 인덱스를 max 인덱스에 넣는다. 
            # 오른쪽 노드와도 왼쪽 노드의 인덱스와 비교한 것처럼 동일하게 비교한다.
            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:  # 왼쪽, 오른쪽 노드와 다 비교했음에도 max 인덱스가 현재 인덱스와 동일하다면
                break                   # 반복문을 빠져나간다
            # 반복문을 빠져나가지 않았다면 현재 인덱스의 위치와 max 인덱스의 위치를 변경한다.
            self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
            cur_index = max_index   # 현재 인덱스에 max 인덱스를 넣어 반복한다.
        return prev_max  # 8 을 반환해야 합니다.


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]

맥스 힙의 원소 제거의 시간 복잡도는 맨 위에 있던 노드가 맨 아래 레벨 까지 내려온다고 가정해서 분석해보면 이진 트리의 높이 만큼의 시간 복잡도가 걸리는 것으로 이진 트리의 높이의 시간 복잡도와 동일하게 $O(log(N))$

그래프

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조이다.
-> 그래프는 노드와 노드 사이의 연결 관계에 초점이 맞춰져 있다.

노드 : 연결 관계를 가진 각 데이터를 의미한다. 정점(Vertax)라고도 한다.
간선(Edge) : 노드 간의 관계를 표시한 선
인접 노드(Adgacent Node) : 간선으로 직접 연결된 노드 (또는 정점)

그래프는 유방향 그래프와 무방향 그래프가 있다.

유방향 그래프 : 방향이 있어서 방향 쪽으로만 가는 단방향 관계를 나타낸다.
무방향 그래프 : 방향이 없어서 쌍방 관계가 가능한 그래프이다.

컴퓨터에서 그래프 표현하기

1) 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
2) 인접 리스트(Adjacnecy 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]
}

1과 2의 차이점은? 시간과 공간의 차이이다.

인접 행렬은 즉각적으로 0과 1이 연결되었는지 여부를 바로 알 수 있다. 그러나 모든 조합의 연결 여부를 저장해야 하기 때문에 $O(노드^2)$

인접 리스트를 사용하면 즉각적으로 연결된 노드들을 확인할 수는 없고, 각 리스트를 다 돌아보아야 한다. 그래서 어떤 노드들이 연결되었는지 파악하기 위해 최대 O(간선)만큼의 시간을 사용해야 한다. 하지만 모든 조합의 여부를 저장할 필요가 없어서 O(노드 + 간선) 만큼의 공간만 사용하면 된다.

DFS & BFS

DFS : 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]
BFS : 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. [컴퓨터인터넷IT용어대사전]

모든 데이터를 탐색해야 하는 경우에 사용되는 방법이다.

DFS : 끝까지 파고드는 것
BFS : 갈라진 모든 경우의 수를 탐색해보고 오는 것

DFS는 끝까지 파고드는 것이라 그래프의 최대 갚이 만큼의 공간을 요구한다. 그래서 공간을 적게 쓴다. 그렇지만, 최단 경로를 탐색하는 것은 쉽지 않다.
하지만,
BFS는 최단 경로를 쉽게 찾을 수 있다. 모든 분기되는 수를 다 볼 수 있기 때문이다. 하지만, 모든 경우의 수를 저장해야 하다 보니 공간을 많이 써야 하고 시간이 오래 걸릴 수 있다.

DFS(Depth First Search) 구현

갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조

노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
만약 끝에 도달했다면 리턴한다.

각 트리의 구조에서 어떤 루트에 방문했었는지 알기 위해서는 표시를 해 놓아야 한다. (visited)

루트 노드부터 시작한다.

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

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

2부터 반복한다.

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]
}

[1]-> [2,5,9]
visited = [1]⠀
[2] -> [1,3]
1은 방문했으니 [3]으로 이동
[3] -> [2,4]⠀
2는 방문했으니 [4]로 이동
[4]에는 방문할 곳이 없으니 다시 최상위 루트 노드로 올라옴

[1] -> [2,5,9][2]는 방문했으니 [5]로 방문
.....
이렇게 끝까지 내려갔다가 더이상 방문할 곳이 없을 때 최상위 노드로 다시 올라오면서 모든 노드를 탐색하는 방법이다.

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

    return


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

무한정으로 깊어지는 노드가 있을 경우 RecursionError 에러가 발생할 수 있다. 그렇기에 재귀함수 말고 다른 방식으로 DFS를 구현해 보자.

DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다.
이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
가장 마지막에 넣은 노드들만 꺼내서 탐색하면 된다는 뜻이다.
즉, 스택을 이용하면 된다.

방법
1. 루트 노드를 스택에 넣습니다.
2. 현재 스택의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
4. 2부터 반복한다.
5. 스택이 비면 탐색을 종료한다.

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]	# 시작하는 노드를 stack 에 저장해준다.
    visited = []
    while stack:	# stack 이 비지 않을 때까지 반복한다.
        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))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

BFS(Breadth-First)

BFS는 현재 인접한 노드 먼저 방문해야 한다.
인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.
=> 큐를 이용하면 BFS 를 구현할 수 있다!

방법
1. 루트 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

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

Dynamic Programming (동적 계획법)

피보나치 수열 - 재귀함수

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

n번째 피보나치 수를 Fibo(n)라고 표현하면,Fibo(1) 은 1이고, Fibo(2) 도 1이다.
즉, Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 = 2이 된다.
Fibo(n) = Fibo(n - 1) + Fibo(n-2) 라고 표현할 수 있다.

Q. 피보나치 수열의 20번째 수를 구하시오.

input = 20

# fibo(N) = fibo(n-1) + fibo(n-2)
def fibo_recursion(n):
    # 1 + 1 = 2
    # 1 + 2 = 3
    # 2 + 3 = 5
    # 3 + 5 = 8
    if n == 1 or n == 2:    # 탈출조건
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)


print(fibo_recursion(input))  # 6765

이 코드의 단점은 input의 수가 커지면 (ex.100) 연산이 너무 오래 걸리게 된다는 단점이 있다.

했던 작업을 또하고, 또 반복하면서 계속 삽질을 하고 있게 된다. 이미 했던 일을 기록했으면 이런 반복적인 일은 하지 않아도 될 것이다.

동적 계획법이란?

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

여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다.
문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다!

메모이제이션(Memoization) : 결과를 기록하는 것
겹치는 부분 문제(Overlapping Subproblem) : 문제를 쪼갤 수 있는 구조

피보나치 수열을 메모이제이션 방법을 사용해 다시 풀어본다.

방법
1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

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))

숙제

Q1.

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.
⠀
해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.
⠀
현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오.
⠀
dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.
⠀
stock = 4
dates = [4, 10, 15]
supplies = [20, 5, 10]
k = 30

heapq라는 라이브러리가 이미 존재함으로
import heapq해서 heap 자료 구조를 사용할 수 있다.

>>> import heapq # heapq 를 사용하기 위해서는 맨 위에 heapq 를 가져온다! 라는 구문을 써주셔야 합니다.

>>> heap = []
>>> heapq.heappush(heap, 4) 	# .heappush로 원소를 넣을 수 있고
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 7)
>>> heapq.heappush(heap, 3)
>>> print(heap)
[1, 3, 7, 4]	# 자동으로 heap 구조로 원소들을 배열해 준다.
>>> print(heapq.heappop(heap))
# 최솟값을 빼는 방법

위 코드는 최솟값으로 구하는 min_heap 방법이었다면, max_heap으로 구하고 싶다면, 음수를 사용한다.

>>> import heapq # heapq 를 사용하기 위해서는 맨 위에 heapq 를 가져온다! 라는 구문을 써주셔야 합니다.

>>> heap = []
>>> heapq.heappush(heap, 4 * -1)
>>> heapq.heappush(heap, 1 * -1)
>>> heapq.heappush(heap, 7 * -1)
>>> heapq.heappush(heap, 3 * -1)
>>> print(heap)
[-7, -3, -4, -1] # 힙의 형태를 유지한채로 원소가 넣어지기 때문에 heap[0]이 최솟값입니다!

>>> print(heapq.heappop(heap) * - 1) # 최댓값을 빼는 방법입니다.
7
>>> print(heap)
[-4, -3, -1] # 마찬가지로 힙의 형태가 유지됩니다.

데이터를 넣을 때마다 최대값을 동적으로 변경시키며
최솟/최댓값을 바로 꺼낼 수 있는 heap 구조를 사용하면 된다.

코드에 주석으로 설명 달아 놓았음

import heapq

ramen_stock = 4
supply_dates = [4, 10, 15]  # dates
supply_supplies = [20, 5, 10]   # supplies
supply_recover_k = 30       # k


def get_minimum_count_of_overseas_supply(stock, dates, supplies, k):
    heap = []
    answer = 0          # 최소한 해외 공장으로부터 몇번 공급 받아야 하는지
    last_added_data_index = 0   # 공장이 멈추지 않는 한 가장 마지막에 넣은 날짜의 인덱스 값
    while stock <= k:       # 남은 물량이 원래 공장에서 공급받을 수 있을 때까지 반복
        # last_added_data_index 가 dates 배열의 길이를 넘어가면서 조회하지 않도록 탈출 조건 작성
        # 날짜 배열의 값이 stock 의 값보다 작거나 같아야 공장을 돌리 수 있기 때문에 조건을 담
        while last_added_data_index < len(dates) and dates[last_added_data_index] <= stock:
            heapq.heappush(heap, -supplies[last_added_data_index])      
            # 현재 stock 보다 적거나 같은 날짜에 공급 받을 수 있는 supplies 의 값을 heap 에 push 한다.
            last_added_data_index += 1  # 최소한으로 공급을 받아야 하니 날짜를 올려 dates 배열에 가능한 날짜가 있는지 확인해본다.

        answer += 1     # 위에 while 문을 돌고 나왔으면 일단 공급을 받았단 이야기이기 때문에 answer에 1을 더해준다. 
        heappop = heapq.heappop(heap)   
        stock += -heappop   # 공급을 받았기 때문에 stock에 heap의 최상위에 있는 supplies의 값을 더해준다. 
    return answer


print(get_minimum_count_of_overseas_supply(ramen_stock, supply_dates, supply_supplies, supply_recover_k))
print("정답 = 2 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15], [20, 5, 10], 30))
print("정답 = 4 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(4, [4, 10, 15, 20], [20, 5, 10, 5], 40))
print("정답 = 1 / 현재 풀이 값 = ", get_minimum_count_of_overseas_supply(2, [1, 10], [10, 100], 11))

Q2.

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
⠀
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
⠀
로봇 청소기는 다음과 같이 작동한다.
⠀
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
⠀
입력 조건
로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. 이 때 d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.
⠀
또한 청소하고자 하는 방의 지도를 2차원 배열로 주어진다.
빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.
⠀
로봇 청소기가 있는 칸의 상태는 항상 빈 칸이라고 했을 때,
로봇 청소기가 청소하는 칸의 개수를 반환하시오.
r, c, d = 7, 4, 0
room_map = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
⠀

이 문제는 로봇 청소기가 청소하는 칸의 개수를 알고 싶어 한다. 그래서 갈 수 있는 모든 칸을 전부 탐색해야 한다. 즉, BFS를 사용한다.

방법
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
⠀⠀⠀왼쪽 방향으로 회전한다는 개념 구현
⠀⠀⠀a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
⠀⠀⠀b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
⠀⠀⠀c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
⠀⠀⠀d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

# 주석으로 설명 작성하였음
current_r, current_c, current_d = 7, 4, 0
current_room_map = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

# 0 은 청소하지 않은 장소,
# 1은 청소하지 못하는 장소,
# 2는 청소한 장소


# 북 동 남 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]


# 방향 전환
def get_d_index_when_rotate_to_left(d):
    return (d + 3) % 4
# 북 (왼쪽으로 회전) -> 서 : 0 -> 3    =>  (0 + 3) % 4 = 3
# 동 (왼쪽으로 회전) -> 북 : 1 -> 0    =>  (1 + 3) % 4 = 0
# 남 (왼쪽으로 회전) -> 동 : 2 -> 1    =>  (2 + 3) % 4 = 1
# 서 (왼쪽으로 회전) -> 님 : 3 -> 2    =>  (3 + 3) % 4 = 2
# ==> rotate -> index 가 (+ 3 % 4)


# 후진
def get_d_index_when_go_back(d):
    return (d + 2) % 4
# 북 (후진) -> 남 : 0 -> 2    =>  (0 + 2) % 4 = 2
# 동 (후진) -> 서 : 1 -> 3    =>  (1 + 2) % 4 = 3
# 남 (후진) -> 븍 : 2 -> 0    =>  (2 + 2) % 4 = 0
# 서 (후진) -> 동 : 3 -> 1    =>  (3 + 2) % 4 = 1


def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
    count = 1               # 청소하는 칸의 개수
    n = len(room_map)       # row
    m = len(room_map[0])    # column
    room_map[r][c] = 2      # 청소가 된 칸은 2로 업데이트 시킨다
    queue = list([[r, c, d]])   #

    while queue:        # queue 가 끝날 때 까지 반복한다
        r, c, d = queue.pop(0)      # queue에 들어 있는 첫번째 칸을 꺼낸다
        temp_d = d      # 방향이 계속 돌아가기 때문에 임시 방향을 변수로 설정해준다
        for i in range(4):      # 모든 방향에 대해서 갈 수 있는 방향을 구한다
            temp_d = get_d_index_when_rotate_to_left(temp_d)    # 왼쪽으로 회전
            new_r, new_c = r + dr[temp_d], c + dc[temp_d]       # 왼쪽으로 회전시 새로운 row 와 column 의 위치 변동

            # 새로운 row와 새로운 column의 칸이 len() 을 넘어가지 않고, 또 0으로 청소되지 않았다면
            if 0 <= new_r < n and 0 <= new_c < m and room_map[new_r][new_c] == 0:
                count += 1      # 그 칸을 청소를 하는 칸이기 때문에 청소한 칸의 변수에 1을 더하고
                room_map[new_r][new_c] = 2      # 이 칸은 청소 되었다는 의미로 2를 2차원 배열에 작성해 준다.
                # 새로운 칸을 queue 에 추가해 주는데, 이동한 칸에서 다시 한 번 탐색을 해 주어야 하기 때문이다.
                queue.append([new_r, new_c, temp_d])
                break   # 탐색해서 올바른 방향이 나왔다면 break 로 for 문을 빠져나간다.
            elif i == 3:    # 네 방향이 모두 청소가 되어 있거나, 벽일 경우, 후진한다.
                # get_d_index_when_go_back -> 뒤로 가는 함수를 사용해 row 와 column 을 변경한다.
                new_r, new_c = r + dr[get_d_index_when_go_back(temp_d)], c + dc[get_d_index_when_go_back(temp_d)]
                queue.append([new_r, new_c, temp_d])
                # 후진하여 새로운 장소로 옮겼는데 1 = 벽인 경우,
                if room_map[new_r][new_c] == 1:
                    return count    # 다 청소 했다고 생각하고 청소한 칸의 값을 반환해준다.


# 57 가 출력되어야 합니다!
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))
current_room_map2 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 29 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(6,3,1,current_room_map2))
current_room_map3 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 33 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(7,4,1,current_room_map3))
current_room_map4 = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
print("정답 = 25 / 현재 풀이 값 = ", get_count_of_departments_cleaned_by_robot_vacuum(6,2,0,current_room_map4))

Q3.

극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다.
공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.
⠀
예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다.
단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.
⠀
예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고,
6번 좌석이나 8번 좌석에도 앉을 수 있다.
그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.
⠀
그런데 이 극장에는 “VIP 회원”들이 있다.
이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
⠀
예를 들어서,
그림과 같이 좌석이 9개이고,
4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다.
또한 <213465789> 와 <132465798> 도 가능한 배치이다.
그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.
⠀
오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다.
총 좌석의 개수와 VIP 회원들의 좌석 번호들이 주어졌을 때,
사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 반환하시오.

피보나치 공식을 사용하면 된다.

변경 가능한 좌석들의 규칙
좌석 [1, 2] 를 옮겨본다.
가능한 경우는 [1, 2][2, 1] 총 2개다.

좌석 [1, 2, 3] 를 옮겨보면
가능한 경우는 [1, 2, 3][2, 1, 3] [1, 3, 2] 총 3개다.

좌석 [1, 2, 3, 4] 를 옮겨보면
가능한 경우는 [1, 2, 3, 4][1, 2, 4, 3] [1, 3, 2, 4][2, 1, 3, 4] [2, 1, 4, 3] 총 5개다.

2, 3, 5, 8 ... 피보나치 공식을 사용하면 된다.

원래 피보나치 공식은 F(1) = 1 이었는데, 여기서는 F(1) = 1, F(2) = 2, F(3) = 3(2)개의 좌석을 옮기는 방법) 으로 생각하고 공식을 사용하면 된다.

# 주석으로 설명 작성
seat_count = 9
vip_seat_array = [4, 7]     # 고정되어 있는 좌석
# 최대 한 좌석만 이동할 수 있다

memo = {
    1: 1,
    2: 2
}


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


def get_all_ways_of_theater_seat(total_count, fixed_seat_array):
    all_ways = 1        # 곱의 연산을 사용할 것이기에 1로 두기도 하고, 아무 자리도 옮기지 않았을 경우의 수도 1이기 때문에 1로 시작한다.
    current_index = 0
    for fixed_seat in fixed_seat_array:  # fixed_seat_array = [4, 7] -> index 가 아니라 번호이다.
        fixed_seat_index = fixed_seat - 1   # 그래서 1을 빼줌으로써 배열의 index 값을 구할 수 있다.
        count_of_ways = fibo_dynamic_programming(fixed_seat_index - current_index, memo)
        # fixed_seat_index - current_index = 사이 사이에 있는 변경할 수 있는 좌석들의 개수가 나온다. [(123) 4 (56) 7 (89)
        # count_of_ways = 고정된 좌석 사이 사이마다 있는 좌석들에서 나올 수 있는 경우의 수
        all_ways *= count_of_ways   # 곱 연산
        current_index = fixed_seat_index + 1    # 0 1 2 3 을 해 주었기 때문에 4 부터 진행하라고
    # 위 for 문은 7까지 진행되고 끝난다. 그래서 7 뒤에 있는 좌석들도 경우의 수를 구해야 하기 떄문에
    # total_count 에서 current_index 를 뺀 수를 다시 피보나치 함수에 돌려 경우의 수를 구한다.
    count_of_ways = fibo_dynamic_programming(total_count - current_index, memo)
    all_ways *= count_of_ways
    return all_ways


# 12가 출력되어야 합니다!
print(get_all_ways_of_theater_seat(seat_count, vip_seat_array))
print("정답 = 4 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(9,[2,4,7]))
print("정답 = 26 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(11,[2,5]))
print("정답 = 6 / 현재 풀이 값 = ", get_all_ways_of_theater_seat(10,[2,6,9]))

실전 문제에 다가갈 수록 점점 더 어려워지는 것 같다.
하루종일 붙잡고 강의를 보고 문제를 풀어서 그런지 힘이 너무 빠진다.....

내가 복습을 제대로 안해설까 아직도 알고리즘이 너무 어렵다 ㅠㅠㅠ

Author And Source

이 문제에 관하여([스파르타코딩클럽] 알고리즘 4주차), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@likeablue_bee/스파르타코딩클럽-알고리즘-4주차

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)