다이나믹 프로그래밍 = DP = Dynamic Programming - 알고리즘의 과정에서 하나의 문제에 대해선 한 번만 풀도록 계획하는 알고리즘. - 재귀함수같은 비효율적인 알고리즘을 개선하기 위한 방법. - 이미 계산한 값을 저장했다가 재활용 한다고 생각하면 편하다. - Top-down 방법과 Bottom-up 방법이 존재. - Top-down 방법: 큰 문제에서 시작하여 작은 문제로 분할하며 푸는 것. - 피보나치를 예로 들면 fb[5] = fb[4] + fb[3]이고 이에 따라서 fb[5]를 구하는 문제는 fb[4]와 fb[3]을 구하는 문제로 분할 가능. - 재귀랑 비슷해 보이지만 계산한 값을 저장하여 이미 계산한 값이 있으면 꺼내쓰는 방법으로 효율성을 증대시킴. - Bottom-up 방법: 작..

신장트리 = Spanning Tree - 그래프가 존재할때 모든 정점에 대하여 최소한의 연결만 남긴 그래프. - 한 그래프에서 여러가지의 신장트리가 존재할 수 있다. - 모든 정점을 포함해야 하며 모두 연결 되어있어야 함.(버텍스가 N개일때 간선은 N-1개) - 사이클이 존재하면 안된다. - DFS나 BFS로 구할 수 있다. 최소신장트리 = Minimum Spanning Tree - 간선에 가중치가 있는 그래프의 신장 트리에서 간선의 가중치의 합이 최소가 되는 신장 트리. - 주요 방법으론 Prim 알고리즘와 Kruskal 알고리즘이 있음. Kruskal 알고리즘 - 간선을 가중치 기준 오름차순으로 정렬하여 순서대로 판단해나가는 알고리즘. - 간선을 고를 때 사이클이 나오지 않는지 판단해야 함. - 사이..