알고리즘 - 그리디(greedy)

탐욕 탐색법이라 불리는 이 친구는 매 순간 최선의 선택을 한다! 가장 인간과 비슷해서 그런지 그리디 친구한테 정이 많이 갔지만 한 번도 써 본적이 없기에 공부를 해보려고 한다.

그리디는 보통 잔돈 문제나 거스름돈 문제에서 많이 나온다. 모든 우의 수를 구하고 순간 순간 가장 알맞은 선택, 예를들어 [1,4,5,6] 배열에서 두 수를 제거해 가장 큰 수 만들기 등에 활용한다.

예시는 블로그에서 따왔다. 먼저 while이 true가 될 때까지 돌린다. if won(타겟)이 잔돈 배열의 첫 번째보다 크면 나눠서 잔돈으로 타겟을 얼마큼 채울 수 있는지 확인하고 won을 바꾼다. 그리고 countes배열에 count를 할당한다. 이런 식으로 계속 돌리면 된다!!

또 다른 예시

k개를 제거했을 때 가장 큰 수에 배열 순서를 바꾸면 안되니까 그대로 푸시하면서 이전에 들어온 것보다 작은지 확인한다. 그리디 귀여워!

출처 : https://loving-wright-d0eedb.netlify.app/blog/greedy-algorithm-in-javascript