탐욕 알고리즘

leetcode 452. Minimum Number of Arrows to Burst Balloons

문제 요약 여러개의 포인트(시작점, 끝점)들이 주어지고 화살을 쏠 때, 여러 포인트들을 모두 맞추는 최소의 화살 개수를 구하는 문제였습니다. 이 문제는 부분에 대한 최적의 해를 구하다보면 전체의 최적의 해에도 도달하는 Greedy Algorithm 문제였습니다. Greedy Algorithm (탐욕 알고리즘) 탐욕 알고리즘이란 그 당시(부분)의 최적의 해를 쫓아 최종적인 해답에 도달하는 방법을 말합니다. 이렇게 해결할 수 있는 문제는 2가지 특징이 있습니다. - 부분의 최적의 해를 쫒아 선택한 것은 그 다음 선택에 영향을 주지 않는다 - 최종적인 해답은 부분의 대한 최적의 해답들로 이루어진다 사실 Greedy Algorithm은 문제 풀 당시에는 '그냥 이렇게 하면 되지 않을까?'(이게 이 당시 최적 아..