[내일배움캠프] 2022-11-28 TIL

자료구조 알고리즘 원격 강의 진도 나가기

힙

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
• 최댓값이 맨 위인 힙은 Max Heap, 최솟값이 맨 위인 힙은 Min Heap
• 원소 추가, 삭제의 시간 복잡도 O(log(N))

그래프

• 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조
• 노드(Node): 각 데이터/간선(Edge): 관계를 표시한 선/인접 노드(Adjacent Node): 직접 연결된 노드
• 간선의 방향이 있으면 유방향 그래프(Directed Graph), 없으면 무방향 그래프(Undirected Graph)
• 인접 행렬(Adjacency Matrix, 시간 유리), 인접 리스트(Adjacnecy List, 공간 유리)로 표현 가능

DFS & BFS

• DFS: 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. [컴퓨터인터넷IT용어대사전]
  • 공간을 적게 쓰지만 최단 경로 탐색이 쉽지 않음
  • 재귀함수, 스택을 이용하여 구현 가능
• BFS: 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. [컴퓨터인터넷IT용어대사전]
  • 최단 경로를 쉽게 찾을 수 있지만 공간을 많이 사용하고 시간도 오래 걸림
  • 큐를 이용하여 구현 가능

동적 계획법(Dynamic Programming)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. [위키백과]
• 메모이제이션(Memoization): 결과를 기록하는 것/겹치는 부분 문제(Overlapping Subproblem): 문제를 쪼갤 수 있는 구조

*동적 계획법을 이용한 피보나치 수열 알고리즘

input = 50

# memo 변수를 이용하여 메모이제이션
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))

숙제 문제 세 가지 몰입해서 풀어보기

[내일배움캠프] 4주차 숙제 Q1: 농심 라면 공장

[내일배움캠프] 4주차 숙제 Q2: 샤오미 로봇 청소기

[내일배움캠프] 4주차 숙제 Q3: CGV 극장 좌석 자리 구하기