[알고리즘 중급 1/3] 그리디 알고리즘

결정 할 때, 그 순간에 가장 최적인 방법( 기준을 내가 잡아야 함 )을 선택하면서 답을 찾아간다.

그 순간에 최적인 방법을 선택한다고 해서, 답이 최적이라고 보장할 수는 없다.

 

어떤 문제가 그리디 라는 것을 어떻게 증명할 것인가?

• 두 동전
• 회의실 배정
• 행렬

어떤 코딩 테스트 문제를 만났을 때, 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민하자. 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 다이나믹 프로그래밍(DP)이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민해보자.
 
처음 문제를 만났을 때는 이것저것 다양한 아이디어를 고려해야 한다. 가장 먼저 10원짜리로만 모두 거슬러 주도록 코드를 작성하면 어떻게 되지?라고 생각할 수 있다. 이후에 10원짜리로만 모두 거슬러 주면 최적해를 구할 수 없겠구나라고 문제점을 인식하고, 가능한 또 다른 문제 풀이 방법을 곰곰이 생각해본다. 그러다 결국엔 '가장 큰 500원짜리로부터 거슬러서 가장 작은 10원짜리까지 차례대로 거슬러 준다면 어떻게 될까?'라고 생각을 하고, '거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로, 이렇게 하면 항상 최적해를 보장할 수 있다.'까지 떠올릴 수 있어야 문제의 정답 판정을 받을 수 있다.
https://scshim.tistory.com/224?category=956102