[Algorithms] 탐욕법 (Greedy) with 프로그래머스

탐욕법은 문제를 해결할 때 현재 단계에서 가장 최선의 선택을 반복적으로 수행하여, 전체 최적해(Optimal solution)에 도달하려고 하는 알고리즘입니다.

---

탐욕법의 핵심 개념

1. 탐욕 선택 속성

• 현재 단계에서 가장 최선의 선택을 함으로써 최적해를 구할 수 있는 속성.
• 탐욕적 선택이 전체 문제에 영향을 미치지 않고 독립적이어야 함.

2. 최적 부분 구조

• 문제의 최적해가 부문 문제의 최적해로 구성되어야 함.
• 동적 계획법(DP)에서도 사용되는 개념으로, 탐욕범의 필수 조건 중 하나.

---

탐욕법의 장단점

장점

• 단순성과 효율성: 구현이 쉽고, 문제를 빠르게 해결할 수 있음.
• 속도: 동적 계획법이나 완전 탐색 보다 일반적으로 더 빠름.

단점

• 최적해 보장 불가: 모든 경우에서 최적해를 보장하지 않음.
• 문제에 대한 제약 조건 필요: 탐욕 선택 속성과 최적 부분 구조를 만족하지 않으면 사용할 수 없음.

---

탐욕법의 동작 원리

1. 정렬(선택적): 문제의 데이터를 특정 기준에 따라 정렬.
2. 탐욕 선택: 각 단계에서 가장 최적의 선택을 반복적으로 수행.
3. 종료 조건: 더 이상 선택할 항목이 없거나, 문제의 조건을 모두 만족했을 때 종료.

---

탐욕법과 동적 계획법(DP)의 비교

특징	탐욕법	동적 계획법
접근 방식	현재 단계에서 최적 선택	모든 경우를 고려하여 최적해
중복 문제	고려하지 않음	중복 계산을 제거
속도	일반적으로 더 빠름	더 느릴 수 있음
적용 조건	탐욕 선택 속성, 최적 부분 구조	최적 부분 구조

---

프로그래머스 예제: 구명보트

1. 사람들의 몸무게가 담겨있는 people 배열을 오름차순으로 정렬합니다.
2. i는 가장 무거운 사람부터 시작, idx는 가장 가벼운 사람부터 시작합니다.
3. 가장 무거운 사람과 가장 가벼운 사람의 몸무게 합이 limit이하이면, 두 사람을 같은 보트에 태울 수 있습니다.
4. 합이 limit을 초과하면, 가장 무거운 사람은 혼자 보트에 태우고 i를 하나 줄입니다.
5. answer는 보트 수를 카운팅합니다.

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int idx = 0;
        for(int i = people.length - 1; i >= idx; i--) {
            if(people[i] + people[idx] <= limit) {
                idx++;
            }
            answer++;
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=java

프로그래머스

끝.