그리디 알고리즘

 : 그리디 알고리즘 ( 탐욕법 )
     ( 참고 출처 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )
     현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
     알고리즘 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
     지금 당장 좋은 것만 선택해도 최적의 해를 구할 수 있는 지가 중요하기때문에 정당성 분석이 중요하다.

     1 - 1 - 100
       ㄴ2 - 1

     이렇게 간단한 그래프가 있다고 했을때, 
     루트노드로부터 마지막 레벨까지 이동했을때 각 노드들의 합을 최대로 경로를 찾고자 할때
     1 + 1+ 100 = 102
     1 + 2 + 1 = 4
     이 두 루트중 첫번째 루트가 당연히 더 크지만,
     그리드 알고리즘으로 해결한다면 두번째 루트트 선택하게 될것이다.

     이렇듯 그리드 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
     하지만, 코딩 테스트에서 그리드 알고리즘 문제는 이렇게 일반적이지 않은 특수한 상황을
     문제로 출제한다고 하니 참고하자.
     위에서 언급한, 최소한의 아이디어를 떠올릴 수 있는 능력을 보는게 아닐까 싶다.
     그리고 그 풀이가 정당한지 검토할 수 있어야 한다.

     예를 들어,
     가게의 점원이 500원, 100원, 50원, 10원의 동전을 무수히 많이 가지고 있다.
     손님에게 잔돈을 거슬러줄때 사용되는 최소한의 동전을 개수를 구하는 알고리즘을 짠다고 생각해보자.
     단순히 500원짜리로 줄 수 있는 최대한의 동전을 주고, 그다음 100원 그다음 50원 그다음 10원의 개수를
     순차적으로 계산하면 될 것이다.

     이건 최소한의 아이디어를 떠올린 단계이다.

     가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 근거는 무엇일까?
     가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 떄문이다.

     이 단계가 정당성을 검토한 것이다.
     앞으로 이러한 문제를 접하면 이러한 정당성을 검토하는 단계를 거쳐보아야겠다.

     막연히 문제풀때 당연히 이렇지 하고만 풀었는데 너무 그리디하게 접근한게 아닌가 싶어 충격이였다.
     ( 코드 : https://github.com/kucnea/CodingTestPractice/blob/master/src/com/algorithm/greedy/Q1.java )


     두번째 예시로,
    
     숫자 N, K가 주어질때, N을 1로 만드는데 최소한의 연산의 횟수를 구하는 알고리즘을 구성하자.
     연산은
     1. N에서 1을 뺀다.
     2. N을 K로 나눈다.
     단, 2번 연산은 N이 K로 나누어 떨어질때만 사용가능하다.

     나는 2번연산이 가능한지 탐색 후, 가능하면 2번연산을 먼저하고 그렇지 않으면 1번 연산을 진행해
     연산의 반복횟수를 반환하도록 코드를 작성했다.
     이러한 선택의 정당성으로는 k가 1보다 클 경우 2번연산으로 N이 1에 가까워지는 정도가 더 크기때문이다.
     물론 k가 1일경우 무한히 반복되기에 k가 1일 경우에는 1번 연산을 하도록 했다.

     영상을 보는 도중 문제를 설명할때는 k에 대한 언급이 없었는데 이후에 문제 제시에는 k가 2이상일때로 설정되어 필요는 없는 부분이 되겠다.
     반복문대신 재귀함수를 사용한건 특별한 이유가 없다.
     ( 코드 : https://github.com/kucnea/CodingTestPractice/blob/master/src/com/algorithm/greedy/Q2.java )


     세번째 예시이다.

     사실 볼품 없는 내 코드를 보여주는건 해당 강의 영상이 java코드가 나오지 않는 경우가 있다.
     아직 실력이 적어 도움이 안될 수 있지만 누군가는 도움이 될 수 있을거라 생각해 java로 구현한 코드를 기재하려 한다.

     각 자리가 숫자로만 ( 0 ~ 9 ) 로만 이루어진 문자열 S가 주어졌을때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며
     숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 코드를 작성하라.
     단, 일반적 사칙연산과 달리 모든 연산은 왼쪽에서부터 오른쪽으로 진행한다.

     이것도 단순하다, 먼저 숫자와 연산을 할 숫자 둘 중 하나가 0 또는 1이 아니라면 곱하는게 숫자가 더 커지기때문에
     두 수가 모두 2이상인 경우에 곱하고 그 외에는 더하는 코드를 작성하면 된다.
     ( 코드 : https://github.com/kucnea/CodingTestPractice/blob/master/src/com/algorithm/greedy/Q3.java )
     ( 내가 작성한 코드의 if문 안의 조건보다, 2이상인 경우로 두 변수를 묶어서 더 간단하게 작성할 수 있다. )

     강의 영상에도 나오지만, 숫자로 변환하는 과정없이 아스키 코드를 이용해 더 간단하게 할 수 있는 것도
     solution2메소드를 보면 확인 할 수 있다.


     네번째 예시이다.
  
     모험가 N명이 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했다.
     공포도가 높은 모험가는 위험상황에서 대처가 어려워, 공포도가 X인 모험가는 반드시 X명이상 모험가 그룹에 참여해야 한다.
     최대 몇 개의 모험가 그룹을 만들 수 있을지 코드를 작성하자. ( 단, 모든 모험가가 그룹에 속하지 않아도 된다. )

     제시되는 정보는 N = 5 이고, 각 모험가의 공포도는 2 3 1 2 2 와 같은 방식이다.
 
     내가 처음에 착안한 아이디어는 내림차순으로 정렬해 큰 수부터 제거하는 방법을 생각했다.
     3 2 2 2 1 이라고 했을때,
     3에서 3명이 그룹을 채택하고, 길이를 2로 만들면 그 다음 큰 그룹으로 2를 만들어 총 2개의 그룹을 생성하는 방식이었다.

     그리고 해설을 보니
     최대 개수의 그룹을 만들기위해서는 작은것부터 만들어야 개수를 더 많이 만들 수 있기에 잘못생각했다는 것을 알았다.

     그래서 해설에 나온대로 작은 크기의 그룹부터 먼저 만드는 방식으로 코드를 짜보았는데 굉장히 보기가 어렵다. ( solution2메소드 )

     최종적으로 해설을 다 보고 코드를 작성한 것은 solution3 메소드를 참고하길 바란다.
     
     solution3를 작성하고보니.. 마음이 아팠다.
     오름차순으로 정리한 것을 이용해 깔끔한 조건문으로 최대 개수의 그룹 수를 찾아내는 방법이 정말 멋졌다.
     나도 저렇게 써낼 수 있기를..
     ( https://github.com/kucnea/CodingTestPractice/blob/master/src/com/algorithm/greedy/Q4.java )

     보시면 알겠지만, 오름차순으로 정리되어있기떄문에 가능한 방법이다.
     새로 들어오는 그룹원마다 카운트를 한다.
     그룹원의 수는 점점 증가하고, 그 값이 들어오는 그룹원의 공포도와 같아지면
     그룹내 인원의 최대 공포도와 그룹원의 수가 같아지는 것이다.
     그럼 그룹수를 증가시키고 그룹을 비우고 다음 그룹을 맞이하면 되는 것이다.