[ALGORITHMS] Greedy Algorithm

1. 탐욕 알고리즘(Greedy Algorithm)이란?

핵심 아이디어: "지금 당장 가장 좋아 보이는 것을 선택한다."
매 단계마다 그 순간 가장 최적인(local optimum) 선택을 반복하여 전체적으로도 최적인(global optimum) 해답을 기대하는 방식

적용 분야:
최적화 문제(optimization problem)에서 종종 사용.
단순히 해결책이 아닌 최적의 해결책을 찾는 데 목적이 있다.

2. 탐욕 알고리즘의 약점

지역 최적해(Local Optimum)에 빠질 수 있음: 탐욕적으로 선택한 해가 전체 문제의 최적해가 아닐 수 있습니다.

3.Greedy Algorithm의 구성 요소

1. Solution Function (해결 여부 판단) : 전체 해결책이 완성되었는지를 판단하는 함수.
2. Candidate Set (후보군) : 가능한 선택지들의 집합.
3. Selection Function (선택 함수) : 후보군 중 가장 좋은 것을 선택하는 기준.
4. Feasibility Function (적합성 판별) : 선택이 가능한지 판단 (예: 제약 조건 위반 여부 등).
5. Objective Function (목표 함수) : 현재 선택 혹은 부분 해결책의 가치를 평가하는 기준.

이 과정을 반복하여 전체 해를 구성

4. 잘못된 적용 사례

• 트리에서 루트부터 리프까지의 최대 합 경로 찾기
• Greedy 접근: 항상 자식 노드 중 값이 큰 것을 선택
• 실제 최댓값 경로는 값이 작은 노드를 포함할 수도 있음

결과적으로 최적해를 보장하지 못함

결론

탐욕 알고리즘은 간단하고 빠르지만, 항상 최적의 해를 보장하지는 않는다. 적절한 문제에만 사용해야 하며, 적용 전 문제의 구조를 충분히 이해하는 것이 중요하다.

---

대표 예시 문제 1 )

Problem Description
You are given a set of ropes, each with a different maximum weight capacity. The objective is to determine the maximum weight of an object that can be lifted using any subset of these ropes.

Each rope in a selected subset must evenly share the weight of the object. This means that if k ropes are used to lift an object of weight w, then each rope must endure w/k. However, no rope can endure more than its maximum capacity.

Example
Given ropes = [10, 20, 20], let's analyze why the maximum weight is 40:

• The three ropes have maximum capacities of [10, 20, 20].
• If we use only the rope with 10, the max weight we can lift is 10.
• If we use one rope of 20, the max weight we can lift is 20.
• If we use both ropes of 20, then they evenly split the total weight, meaning each can handle half the load.
• Since each can lift 20, the total weight they can lift together is 20 + 20 = 40.
• If we tried using all three ropes (10, 20, 20), the weight would be divided evenly among three ropes, limiting the total weight.
• Optimal Choice: Using only the two 20 ropes achieves the maximum weight capacity of 40.

API
public int maxWeight(int[] ropes)

Input:
ropes: An integer array representing the maximum weight each rope can endure.

Output:

An integer representing the maximum weight that can be lifted using a subset of ropes.

Constraints:

1 ≤ ropes.length ≤ 100, 1 ≤ ropes[i] ≤ 1000

Main method for Test

public class Test {

public static void main(String[] args) {

    Itm itm = new Itm(); // Create an instance of the Itm class



    // Define an integer array containing the maximum weight each rope can endure

    int[] ropes = {10, 20, 20};

   

    // Compute the maximum weight that can be lifted

    int result = itm.maxWeight(ropes);

   

    // Print the result, expected output is 40

    System.out.println("Maximum weight that can be lifted: " + result);

}

}