대엉코딩

그리디 알고리즘이란?

->  탐욕알고리즘 이라고도 불리우며, 전체적인 그림을 보지 않고 각각의 단계에서 최상의 선택들을 반복 함으로써 결과를

      도출 해내는 방법이다.

-> 사실 대부분의 경우 최적의 해가 아닐 가능성이 높다.

-> 간단한 예시로 트리의 각각의 노드의 임의의 정수가 있다. 트리의 루트노드 부터 리프 노드가 나올 때 까지 탐색 하여 그 합을 도출    

    하는 데 그 합이 가장 큰 경우의 수 를 구하려고 한다.

-> 이 경우 자식노드로 내려가면서 그 단계마다 가장 큰 자식 노드를 선택할 경우 나중에 전체의 합은 가장 큰 경우의 수가 아닐 가능성       이 매우 높다 ( 물론 우연히 맞을 수 도 있다.)

정당성 을 찾자

-> 그래서 어떠한 문제가 주어졌을 때 이 문제는 그리디 알고리즘을 이용하면 최적의 해를 구할 수 있겠다 라는 것을 생각 하기 위해서       왜 각각의 단계에서 최적의 선택을 했을 떄 전체도 최적의 경우가 되는지에 대한 정당성을 스스로 찾을 수 있어야 한다

-> 그 정당성을 찾음으로써 그리디 알고리즘을 사용할 경우 최적의 해가 나오는 구나 라는 생각을 할 수 있다.

-> 가장 대표적이면서도 기본적인 예시로 동전 거슬러주는 문제가 있는데, 문제를 아마 풀어보신 분들이 많을 것이라 생각된다.

-> 860 원을 거슬러 줘야 하는 경우 라고 가정하자( 500원, 100원 , 50원, 10원은 무한히 가지고 있다고 하자)

-> 가장 큰 단위의 동전인 500원 부터 가능한 많이 사용하고 그 다음 100원을 가능한 많이...! 이런 식으로 그리디 알고리즘을 사용하면

      가장 적은 수의 동전으로 거슬러 줄 수 있다.(500원 1 , 100원 3, 50원 1, 10원 1 ---> 총 6개의 동전 )

-> 단, 이러한 아이디어를 생각 했을 때 저 경우의 수 가 왜 최적인지 정당성을 찾아야 한다.

-> 이 경우에는 바로 큰 수의 동전들이 모두 작은 수의 동전들의 배수 라는 것이다 (나누어 떨어진다.)

-> 만약 400원 짜리 동전도 있었다고 가정을 하면 그리디 알고리즘을 사용하면

     (500원 1, 100원 3, 50원 1, 10원 1) --> 총 6개의 동전 사용 --->최적이 아니다!!!

     (400원 2, 50원 1, 10원 1) --> 총 4개의 동전 사용 

-> 이 경우는 500원이 400원의 배수 (나누어지지) 가 아니기 때문에 그리디 알고리즘을 사용할 경우 최적의 해가 나온다는 정당성을  

     가질 수 없다. 

동전 문제입니다.

처음에 입력조건을 꼼꼼하게 파악하지 않아 다른 경우의 수 를 생각 하다가

다시 문제를 보니 생각보다 훨씬 쉬운 문제였습니다..

필기노트에 기재되어 있습니다.

<필기>

<코드>