Kruskal
-
알고리즘 ch8 Greedy algotithm학교 수업/알고리즘 2020. 6. 15. 18:50
Optimization Problem- 여러개의 가능한 답 중에 가장 최적의 답 또는 최적의 답과 가까운 답을 고르는 문제- 비용을 최소화 한다거나 이익을 최대화 하는 답을 고르는 문제 Greedy Algorithm- 최적해를 구하는 데에 사용되는 근사적인 방법. - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함) Optimization problem 중 greedy 방법을 사용하는 문제1. Minimum Spanning Tree (MST) - Spanning tree 중 사용된 간선들의 가중치 합이 최소인 트리 즉, 그래프 내에 있는 모든 정점들을 가장 적은 수..
-
[프로그래머스] 지형이동문제 풀이 2020. 6. 5. 16:01
문제 설명N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지..