99클럽 코테 스터디 23일차 TIL (탐욕법 Greedy(3))

문제

정수 배열 nums가 2n개의 정수로 주어졌을 때, 이 정수들을 n개의 쌍 (a1, b1), (a2, b2), ..., (an, bn)으로 그룹화하십시오. 이때 모든 i에 대해 min(ai, bi)의 합이 최대화되도록 하십시오. 최대화된 합을 반환하세요.

---

 

문제 해결

1. 모든 i에 대해 min(ai, bi)의 합이 최대가 되는 것이기 때문에 정렬이 필요하다 생각했다.
2. Arrays.sort()로 정렬 후 한 쌍의 최소 값들만 더하면 되기 때문에 for문에서 i += 2를 작성했다

나의 풀이

class Solution {
    public int arrayPairSum(int[] nums) {
        int result = 0;
        
        // 오름차순 정렬
        Arrays.sort(nums);

        for(int i = 0; i < nums.length; i += 2){
            result += nums[i];
        }

        return result;
    }
}

---

회고

• 문제 카테고리를 보지않고 어떤 풀이법으로 작성할지 고민해보기

 

아래는 20일차 체육복 문제(그리디)를 풀고나서 GPT에게 물어봤던 답변이다.

AI

그리디 알고리즘(탐욕법)을 사용해야겠다는 판단을 내릴 수 있는 몇 가지 힌트 포인트가 있습니다. 이 문제에서 그런 힌트를 확인해보면:

1. 국소 최적 선택(local optimal choice)

• 문제에서 요구하는 바는 "체육복을 최대한 많이 빌려줘서 최대한 많은 학생이 체육수업에 참여할 수 있도록 하는 것"입니다.
• 그리디 알고리즘은 항상 현재 상황에서 가장 최적인 선택을 하고, 이 선택이 최종적으로도 최적해로 이어진다는 가정 하에 동작합니다.
• 이 문제에서 "바로 앞번호나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다"는 조건이 주어지므로, 체육복을 빌려줄 수 있는 학생이 생기면 그 상황에서 바로 빌려주는 것이 최적의 선택일 가능성이 큽니다.

2. 순차적인 처리 가능성

• 학생 번호가 순차적으로 나열되어 있고, 체육복을 빌려주는 대상이 "바로 앞번호"나 "바로 뒷번호"로 제한되어 있습니다.
• 따라서 학생 번호를 작은 순서부터 순차적으로 처리하며 가능한 최적의 결정을 내려가면 문제가 해결될 가능성이 높습니다.
• 그리디 알고리즘은 이러한 순차적 접근이 가능한 문제에 적합합니다.

3. 단일 선택 기준

• 각 학생이 체육복을 빌릴 때, 특정 학생에게 체육복을 빌려주기로 결정하면 다른 선택지를 고려할 필요가 없습니다.
• 예를 들어, 3번 학생이 4번 학생에게 체육복을 빌려준다면, 더 이상 4번 학생에게 체육복을 빌려줄 방법을 고민할 필요가 없습니다.
• 이처럼 한 번 선택하면 그 선택이 문제를 해결하는데 영향을 미친다는 점이 그리디 접근의 중요한 힌트입니다.

4. 문제의 제약 조건이 단순한 경우

• 이 문제에서는 학생 수가 최대 30명으로 제한되어 있고, 여벌 체육복을 빌려주는 조건이 "바로 앞번호" 또는 "바로 뒷번호"로 한정되어 있어 비교적 단순합니다.
• 그리디 알고리즘은 이러한 단순한 조건하에서 최적해를 쉽게 찾을 수 있는 경우에 유리합니다.