Algorithm, programmers, 42885(구명보트)

• 난이도 하 / 탐욕법

  탐욕법

  정의

  : 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘

• 최적화 문제를 푸는데 사용한다
• 근시안적으로 해를 구할 당시에 가장 최적인 해를 구한다
• 동적 계획법보다 효율적이지만 반드시 최적의 해를 구해준다는 보장이 없다

탐욕 알고리즘의 활용

최소수의 동전으로 거스름돈 거슬러주기

편의점에서 돈을 거슬러 줄 때에는 서비스 차원에서 최소한의 동전 개수로 돈을 거슬러 주는 게 좋다. 거스름돈이 550원인데 50원짜리 11개를 주면 받는 손님은 불쾌할 것이다. 이 문제의 해는 거슬러 줄 총액에 해당하는 동전의 집합이고, 최적해는 동전의 개수가 최소가 되는 집합이다.

이외

1. 최소비용 신장트리
   • 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리)
   • ex.크루스칼 알고리즘
2. 다익스트라 알고리즘
   • 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘
3. 허프만 코딩
   • 데이터를 압축하는 방법중의 하나로 쓰이는 알고리즘

---

package org.programmers;

import java.util.Arrays;

public class boat {

	public static void main(String[] args) {
		int[] p = {70,80,50};

		solution(p, 100);
	}
	public static int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);
        int head = 0;
        for(int i = people.length-1; i >= 0; i--) {
        	// 마지막 남은 한 사람
        	if (i==head) {
        		answer++;
        		break;
        	}
        	// 제일 몸무게 큰사람 + 작은 사람 이 limit보다 작으면 같이 태워보낸다
        	if (people[i] + people[head] <= limit) {
        		head++;
        		answer++;
        		// 마지막 남은 두사람이었다면 for문 나간다
        		if (i==head) {
            		break;
            	}
        	} else {
        	// 제일 몸무게 큰사람만 태워 보낸다
        		answer++;
        	}
        }
        return answer;
    }
}

---

Reference

• 문제로 가기
• 탐욕 알고리즘