알고리즘 설계 기법 - Greedy 알고리즘/욕심쟁이 기법

알고리즘 설계기법

욕심쟁이 기법 (Greedy method)

• 최적 해답을 구성할 수 있는 집합을 만들기 위해 필요한 원소를 각 단계마다 하나씩 선택해 나가는 방법
• 선택을 하는 매 순간마다 현재 상태에서 가장 좋아 보이는 원소를 선택하는 전략
• 최적의 해를 찾는 전형적인 해결 방법
• 즉, 각 순간에 지역적으로 가장 좋아 보이는 선택이 보여서 전체적으로 가장 좋은 최종의 답에 이르는 문제가 많기 때문에 전략이라고 할 수 있음
• 이 기법은 모든 최적화 문제를 해결할 수는 없으나, 많은 경우의 문제에 쉽게 적용할 수 있는 기법 중 하나

욕심쟁이 기법 적용 예

• 배낭 채우기 문제
• 거스름돈 문제
• 최단 경로 문제(Dijkstra의 최단 경로 Algorithm)
• 최소 비용 신장 트리
  • Prim(프림)의 알고리즘
  • Krusckal(크루스컬) 알고리즘

연습문제

욕심쟁이 기법 적용 예 - 배낭 문제(knapsack problem)

• n개의 물건과 이 물건을 담을 수 있는 배낭이 있을 때 어떤 물건들을 선택해서 배낭에 넣으면 배낭 안에 있는 물건들의 총 가격이 가장 크게 되는가
• 제약조건
  • 배낭에 넣을 수 있는 최대 무게는 제한한다
  • 배낭 안에 넣은 물건들의 총 무게는 이 제한 무게를 넘지 않아야 한다
• 문제
  • 배낭의 제한 무게는 15Kg
  • 각 무게와 가격은 다음과 같음(분할 가능)
    • 1번: 60원, 4Kg
    • 2번: 45원, 9Kg
    • 3번: 21원, 7Kg
    • 4번: 12원, 3Kg
  • 배낭에 최대로 담을 수 있는 물건들과 총 가격은 얼마인가?

욕심쟁이 기법에 의해 하나씩 물건을 선택할 때 고려할 전략

• 가장 비싼 물건부터 선택하는 전략

60원 4Kg + 45원 9Kg + 21/7 * 2Kg = 111원

• 무게가 가장 적은 물건부터 선택하는 전략

12원 3Kg + 60원 4Kg + 21원 7Kg + 45원/9 1Kg = 98원

• 각 물건의 단위 무게당 가격을 계산한 후 이 값이 더 큰 순서로 물건을 선택하는 전략
  • 무게의 증가에 비해 가격이 최대한 많이 증가하는 전략이 최적의 해답

15원 * 4Kg + 5원 * 9Kg + 4원 * 2Kg = 113원

욕심쟁이 기법 적용 예 - 거스름돈 문제

• 동전의 개수가 최소가 되도록 거스름돈을 주는 문제
• 거스름돈: 890원
• 먼저 가치가 가장 높은 동전부터 거스름돈을 초과되지 않도록 내줌
  • 500원 동전 1개
  • 100원 동전 3개
  • 50원 동전 1개
  • 10원 동전 4개
• 이 과정을 가치가 높은 동전부터 내림차순으로 총액이 정확히 거스름돈이 될 때까지 계속 수행
• 문제
  • 입력한 금액만큼 큰 단위 순으로 지불
    • 5,000원 지폐
    • 1,000원 지폐
    • 500원 동전
    • 100원 동전
    • 50원 동전
  • 금액 입력: 18793
  • 5000원: 3
  • 1000원: 3
  • 500원: 1
  • 100원: 4
  • 50원: 1
  • 10원: 2
  • 나머지: 3

import java.util.Scanner;

public class Greedy_Coin {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        // 최소단위 10, 최대단위 5000
        int price = 0;

        System.out.print("총 금액 입력: ");
        price = scan.nextInt();

        int[] arr = {5000,1000,500,100,50,10};
        for(int i=0; i<arr.length; i++) {
            //금액을 대입해서 자동계산
            if(price/arr[i] > 0) {
                System.out.println(arr[i]+"원: "+price/arr[i]+"개 ");
                price%=arr[i];
            }
        }
        System.out.println("잔돈: "+price+"원");
    }
}

Dijkstra(다익스트라)의 최단 경로 알고리즘

• 하나의 출발점에서 모든 종착점의로의 최단경로를 찾는 문제
• 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
• 집합 S
  • 시작 정점 v로부터의 최단 경로가 이미 발견된 정점들의 집합
• distance 배열
  • 최단 경로를 알려진 정점만을 통하여 각 정점까지 가는 최단 경로의 길이
  • 매 단계에서 distance의 값이 가장 적은(비용이 적은: 최적) 정점을 S에 추가

최소 비용 신장 트리(MST : Minimum Spanning Tree)

• 트리를 구성하는 간선들의 가중치를 합한 것이 최소가 되는 신장 트리
• 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 신장 트리
• MST의 응용
  • 도로 건설
    • 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
  • 전기 회로
    • 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
  • 통신
    • 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
  • 배관
    • 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제
• 최소 비용 신장 트리 알고리즘
  • 프림(Prim)의 알고리즘
  • 크루스컬(Kruskal)의 알고리즘

프림(Prim)의 알고리즘

• 한 번에 하나의 간선을 선택하여 최소 비용 신장 트리 T에 추가
• 구축 전 과정을 통해 하나의 트리만을 계속 확장
• 이 과정은 트리가 n-1개의 간선을 가질 때까지 계속

크루스컬(Kruskal) 알고리즘

• 한 번에 하나의 간선을 선택하여 최소 비용 신장 트리 T에 추가
• 비용이 가장 적은 간선을 선정하되, 이미 T에 포함된 간선들과 사이클을 형성하지 않는 간선만을 추가
• 비용이 같은 간선들의 임의의 순서로 하나씩 추가