패스트캠퍼스 챌린지 13일차

탐욕 알고리즘 (Greedy algorithm)

 - 최적의 해에 가까운 값을 구하기 위해 사용된다.

 - 여러 경우 중 하나를 결정해야할 때 마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서,

   최종적인 값을 구하는 방식

 

 

EX 1 : 동전 문제

public class GreedyAlgorithm {
  public void coinFunc(Integer price, ArrayList<Integer> coinList) {
    Integer totalCoinCount = 0;
    Integer coinNum = 0;
    ArrayList<Integer> details = new ArrayList<Integer>();
        
    for (int index = 0; index < coinList.size(); index++) {
      coinNum = price / coinList.get(index);
      totalCoinCount += coinNum;
      price -= coinNum * coinList.get(index);
      details.add(coinNum);
      System.out.println(coinList.get(index) + "원: " + coinNum + "개");
    }
        
    System.out.println("총 동전 갯수: " + totalCoinCount);
    
    }
}

// 실행
GreedyAlgorithm gObject = new GreedyAlgorithm();
ArrayList<Integer> coinList = new ArrayList<Integer>(Arrays.asList(500, 100, 50, 1));
gObject.coinFunc(4720, coinList);

 

EX 2 : 부분 배낭 문제(Fractional Knapsack Problem)

 • 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제

  - 각 물건은 무게(w)와 가치(v)로 표현될 수 있다.

  - 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있다.

    => 각 물건의 무게 대비 가치를 구해서 물건의 실 가치를 구해서 비교한다.

 

public class GreedyAlgorithm {
  public void knapsackFunc(Integer[][] objectList, double capacity) {
    double totalValue = 0.0;
    double fraction = 0.0;
    
    // 두번째 인자로 정렬방법을 선언하여 사용할 수 있다.
    Arrays.sort(objectList, new Comparator<Integer[]>() {
      @Override // 2차원 배열로 담긴 데이터의 가치의 값을 구하여 정렬
      public int compare(Integer[] objectItem1, Integer[] objectItem2) {
        return (objectItem2[1] / objectItem2[0]) - (objectItem1[1] / objectItem1[0]);
      }
    });
                    
    for (int index = 0; index < objectList.length; index++) {
      if ( (capacity - (double)objectList[index][0]) > 0 ) {
        capacity -= (double)objectList[index][0];
        totalValue += (double)objectList[index][1];
        System.out.println("무게:" + objectList[index][0] + ", 가치:" + objectList[index][1]);
      } else {
        fraction = capacity / (double)objectList[index][0];
        totalValue += (double)objectList[index][1] * fraction;
        System.out.println("무게:" + objectList[index][0] + ", 가치:" + objectList[index][1] + ", 비율:" + fraction);                
        break;
      }
    }
    
    System.out.println("총 담을 수 있는 가치:" + totalValue);
    
    }
}

// 실행
GreedyAlgorithm gObject = new GreedyAlgorithm();
Integer[][] objectList = { {10, 10}, {15, 12}, {20, 10}, {25, 8}, {30, 5} };
gObject.knapsackFunc(objectList, 30.0);

 

 

 • Comparable 과 Comparator 인터페이스
  - Comparable 와 Comparator 는 둘 정렬 기준을 구현하기 위해 사용되는 인터페이스
  - Comparable 인터페이스는 구현체에 compareTo() 메서드를 override 해서 구현
  - Comparator 인터페이스는 구현체에 compare() 메서드를 override 해서 구현
  - 동일 객체에 다양한 정렬 기준을 가진 클래스를 작성하기 위에 같이 선언할 수 있다.  

 

 

• 탐욕 알고리즘의 한계

 - 탐욕 알고리즘은 근사치 추정에 활용되므로 반드시 최적의 해를 구하는것은 아닐 수 있다.

 

 

13일차 인증

 

 

해당 알고리즘부터는 이해는 되지만 실제로 문제를 변형하여 한번씩 코드를 작성 해봐야 할것 같다는 생각드는 챕터다..

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]