Algorithm, programmers, 42885(구명보트)
- 난이도 하 / 탐욕법
탐욕법
정의
: 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘
- 최적화 문제를 푸는데 사용한다
- 근시안적으로 해를 구할 당시에 가장 최적인 해를 구한다
- 동적 계획법보다 효율적이지만 반드시 최적의 해를 구해준다는 보장이 없다
탐욕 알고리즘의 활용
최소수의 동전으로 거스름돈 거슬러주기
편의점에서 돈을 거슬러 줄 때에는 서비스 차원에서 최소한의 동전 개수로 돈을 거슬러 주는 게 좋다. 거스름돈이 550원인데 50원짜리 11개를 주면 받는 손님은 불쾌할 것이다. 이 문제의 해는 거슬러 줄 총액에 해당하는 동전의 집합이고, 최적해는 동전의 개수가 최소가 되는 집합이다.
이외
- 최소비용 신장트리
- 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리)
- ex.크루스칼 알고리즘
- 다익스트라 알고리즘
- 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘
- 허프만 코딩
- 데이터를 압축하는 방법중의 하나로 쓰이는 알고리즘
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;
}
}