JAVA Coding Test Greedy

코딩테스트의 Greedy 과정을 한번 이해해보자

Greedy

그리디를 정의하긴 매우 어렵다고 개인적으로는 생각한다. 보통은 Greedy Algorithm 보다는, Greedy strategy로 많이 부르기도 하는데, 그만큼 어떤 정형화 되어있다기 보다는, 조건에 맞춰서 생각하다보면 최적의 방식을 바탕으로 어..그리디네? 하는 상황이 되기도 한다.

정의

• 각 단계에서 현재 상황에서 최선이라고 생각되는 선택을 하는 방식을 보통 그리디 방식이라고 한다.
• 하지만, 전체의 최적해를 보장하지 않기 때문에, 잘 따져봐야할 것 같다.
• 시간복잡도? → 정해져있지도 않다. O(n) ~ O(n log n)인데, 이는 정렬이 필요할 수 있다면 달라지기 때문이다.

Local Minima에 빠지게 된다면 Global minima를 찾지 못하게 되는 것이 Greedy 알고리즘이라고 생각하면 된다. 왜? → local minima에 빠지게되면, 이게 peak라는 걸 인지하고 더 이상 다음 연산을 하지 않는다. 전체적으로 보면 최적해를 구하지 못하는 구조가 이 특징이다.

그래서 그리디 알고리즘은, 무조건 내가 한번 지나갔을 때 최적이라는 판단이 들 때 쓰이는 구조일 때 쓰인다.

장/단점

• 한 번의 탐색으로 답을 구할 수 있기 때문에 빠른 실행시간을 가질 수 있다. (정렬이 없다는 가정 하에) 그래서 O(n)의 시간 복잡도를 갖었었다.
• 메모리가 매우 효율적이다. 매 순간 판단해서 최적화를 하기 때문에, 그냥 이전 최적값만 가지고 있다면 현재 검사하는 것과 비교해서 만약 지금 것이 최적 값이다 + 다음 것을 검사해서 최적값이 아니다라는 것만 알 수 있다면 충분하다.

그만큼 한정적이라고 볼 수 있는데,

• 최적해를 보장하지 않고,
• 조건이 많아진다면, 최적해가 까다로워지고 이는 보장하기 어려워진다. 한 두개의 변수를 조작했을 때 답을 찾을 수 있을 때 그리디 알고리즘을 사용하곤 한다.

대표적인 그리디 알고리즘

1. 최단 경로 문제(Dijkstra’s Algorithm)
   • 시작 노드로부터 다른 모든 노드까지의 최단 경로를 구하는 문제
   • 각 단계에서 현재까지 가장 짧은 경로를 가진 노드를 선택하고, 이를 기준으로 다른 경로를 갱신하는 방식으로 해결.
2. 배낭 문제 (0/1 Knapsack Problem)
   • 주어진 아이템들 중에서 가장에 담을 수 있는 최대 가치를 구하는 문제 (무게와 가치)
   • 물건의 가치 대비 무게가 가장 높은 순으로 아이템을 선택하여 최대 가치를 구하는 방식으로 해결
   • 부분의 답이 큰 부분의 답이 되고 이 부분들의 답이 전체의 답이 되는 방식
3. 회의실 선택의 문제
   • 주어진 회의들의 시작 시간과 종료 시간이 있을 때, 회의실을 최소한으로 사용하여 모든 회의를 진행할 수 있는 방법을 찾는 문제
   • 시작 시간을 기준으로 회의를 처리하면서 최소 회의실 수를 계산
4. 크루스칼 알고리즘(Kruskal’s Algorithm)
   • 주어진 그래프에서 모든 노드를 연결하는 최소 스패닝 트리를 찾는 문제
   • 간선들을 가중치 순으로 정렬하고, 최소한의 간선부터 선택하면서 사이클이 발생하지 않도록 연결하는 방식
5. 프림 알고리즘(Prim’s Algoritm)
   • 주어진 그래프에서 최소 스패닝 트리를 찾는 문제
   • 이미 연결된 노드에서 가장 가까운 노드를 선택하여 트리를 확장하는 방식
6. 동전 교환 문제(Coin Change Problem)
   • 주어진 동전으로 특정 금액을 만들 때, 최소 동전 수를 구하는 문제
   • 가장 큰 단위의 동전부터 차례대로 사용하여 금액을 맞추는 방식으로 해결

그래서 언제 쓰는데?

1. 최소값/최댓값 문제에서 그리디 알고리즘일 경우가 매우 흔하긴 하다

2. 구체적으로 선택 규칙이 따로 지정되어 있을 때? 혹은

3. 문제를 해결하는 과정이 반복적 대입일 때

4. 제일 중요한 건 순차적 처리가 가능할 때 그리디를 자주 쓴다.

그리디 알고리즘은 “이걸 그리디 알고리즘으로 풀어야지” —-> 접근하면 안됨.

대신 이 문제를 어떻게 풀지? –> 최대한 간단히 풀 방법은 없을까? —> 로직 정리를 하다보면, 어….이거 그리디네? 이런 느낌ㅋㅋㅋ

물론, 다익스트라, 프림, 크루스칼과 같은 종류는 이분탐색이나, BFS/DFS처럼 형식이 정해져있는 것도 있는데 이들은 좀 특수한 케이스들을 모아서 정형화한 것이라고 생각하면 된다.

• 그 외는 안된다.

예시문제-구명보트

아이디어를 떠올려 볼까?

• 구명보트를 최대한 적게 써야하니까 한 보트에 많이 태워야 한다?
• 무거운 사람부터 태워서 내보낸다?
• 제일 가벼운 사람이랑 무거운 사람이랑 합치면서, 못타면 무거운 사람부터 내보내고, 태우면 쌍으로 내보내는 방식?

Why Greedy?

그 순간의 최적의 값에 초점!

• 매 순간 같은 방식을 사용하면서, 기준이 매 순간 같아야 한다.
• ex) 무거운 사람부터 내보낸다면, 무거운 사람의 경우 계속 혼자 내보내다가, 나중에는 가벼운 사람들만 남아서 무조건 둘 씩 타게 되는 상황이 생기게 될텐데, 이는 전체적으로 봤을 때 각 스텝 마다의 최적의 상황이 전체의 최적의 상황이 되기엔 좀 애매한 느낌이 있다.
• 매순간 (가장 무거운 사람 + 가장 가벼운 사람) 조합으로 구성해서 태운다면, 획일화된 기준으로 매 스텝을 진행할 수 있을 것 같다.

로직

• 입력 people: 사람들의 몸무게를 담은 배열 limit: 구명보트의 무게 제한
  • 주어진 변수가 순차적 정렬이 가능함.
  • 정렬을 했기 때문에 우리는 매순간 최선의 선택을 할 수 있다.
  • 한번 건너간 사람은 필요없기 때문에, 중복계산 필요없음.
  • 그 외 변수 별로 따로 계산 할 건 없음. (변수끼리 독립적으로 따로 계산할 사항은 없음.) —-> 여기서 아 이거 그리디구나를 알 수 있다.

• 츨력: 총 필요한 구명 보트의 갯수

• 로직
  1. 구명 보트에 최대 2명씩 태울 수 있음
  2. 각 구명보트에는 무게 제한이 있음.
  3. 두명씩 쌍을 지어서 태울 수 있는지 없는지
  4. 가벼운 사람 두명을 태우는 방식으로 가면, 구명보트 갯수가 최솟값은 아닐꺼다.
  5. 그럼 어떻게든 최소로 구명보트를 줄일 수 있는 방법을 고려해야함. —-> 투포인터!
• Psudo code
  1. people array 정렬
  2. 가벼운 사람 인덱스 / 무거운 사람 인덱스 –> 둘을 합쳐서 태움.
  3. if 가벼운 사람 무게 + 무거운 사람 무게 > limit
  • 무거운 사람만 태움, 무거운 사람 인덱스 –
  • 둘다 태움, 가벼운 사람 인덱스 ++, 무거운 사람 인덱스 –
    1. 카운트해서 출력

구현이 어려울까? 전혀 어렵지 않다.

이걸 그리디 알고리즘으로 풀어야지? 혹은 이거를 무슨 무슨 알고리즘으로 풀어야지 하고 접근하면, 이 간단한 게 나오질 않은 경우를 정말 많이 봤다.

• 나중에 보면서, 매 순간 최선의 선택을 했으니..그리디였구나.. 로 보면서 넘어가면 OKAY

Code

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit){
        int answer = 0;
        Arrays.sort(people);
        int minWeightIdx = 0;
        int maxWeightIdx = people.length - 1;

        while(minWeightIdx <= maxWeightIdx){
            answer++;
            if(people[minWeightIdx] + people[maxWeightIdx] <= limit){
                minWeightIdx++;
                maxWeightIdx--;
            }else{
                maxWeightIdx--;
            }
        }

        return answer;
    }
}