그리디 알고리즘 개념정리와 문제

✏️ 그리디 알고리즘 간단하게 이야기하면 뒷 일은 생각안하고 당장에 눈 앞에 있는 것중에 가장 좋은 것만을 택하는 알고리즘이라고 볼 수 있다. 시작점부터 시작해서 가장 큰수를 얻어야하는 문제가 있다. 여기서 노란색 화살표로 표현된 것이 그리디 알고리즘, 주황색 화살표로 표현한 것이 최적해이다. 처음에 10을 거쳐야 가장 큰 수인 500을 얻을 수 있지만 그리디 알고리즘은 당장에 가장 큰 수인 15를 먼저 선택했기떄문에 20을 출력하게 된다. 그리디(Greedy)알고리즘은 이처럼 최적해를 보장해주지 않는다. ✏️ 그리디 알고리즘의 사용조건 첫째. 그리디 알고리즘은 최적해를 보장해주지 않는다고 했다. 즉, 그리디 알고리즘을 이용했을때 최적해가 나오는 문제에 그리디알고리즘을 이용할 수 있다. 이를 만족시킬 조..