[알고리즘] 그리디 알고리즘

그리디 알고리즘

만약 문제 중에 그리디 알고리즘이 나오면? -> 가장 나중에 풀자!
생각보다 까다로울 수 있는 문제일 수 있기 때문에 마지막에 시간을 많이 갖고 풀어야 함

결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘

그때 그때는 최적일지도 모르지만, 최종적으로는 답이 최적이 아닐 수도 있는 가능성 존재

그리디 알고리즘은 언제 써야하나?

지금 이 순간, 가장 좋은 경우를 선택하는 것이 항상 최적인 경우

그냥 생각하면 쉬워보이지만, 왜 최적인지 증명을 해야하기 때문에 그리디 알고리즘은 상당히 어려운 영역임