코딩테스트 - 패스트캠퍼스 챌린지 17일차

수강한 강의
Chapter 19 탐욕 알고리즘
- 탐욕 알고리즘의 이해

학습 후기
탐욕 알고리즘(Greedy Algorithm)
최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들로 최종해를 구했다고 해서 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제는 지역적으로 최적이면서 전역적으로도 최적인 문제이다.

필요한 조건
1. 탐욕스러운 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조 조건: 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해이다.
위 두 가지 조건이 만족되어야 탐욕 알고리즘도 최적해를 구할 수 있다.

탐욕 알고리즘이 사용되는 문제들
1. 활동 선택 문제
2. 거스름돈 문제
3. 최소 신장 트리
4. 다익스트라 알고리즘
5. 크루스칼 알고리즘

탐욕 알고리즘이 사용되는 문제 예시로 거스름돈을 걸러줄 때 다양한 종류의 동전(10, 50, 100, 500)으로 동전의 수를 가장 적게 지불하는 문제가 있다. 이 문제의 경우 가장 큰 동전부터 최대한 거슬러 주는 돈을 채우는 방식으로 해결한다. 1270원을 거슬러 줘야 한다면 (500원 * 2개) + (200원 * 1개) + (50원 * 1개) + (10원 * 2개) 총 6개의 동전이 가장 최적해가 된다.

강의에서 배낭 문제도 예시로 나오는데, 배낭 문제란 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분 집합을 찾는 문제이다. 배낭 문제는 아이템들을 분할 가능한 배낭 문제(Fractional knapsack Problem)와 0-1 배낭 문제(0-1 Knapsack Problem)로 나눈다. 전자는 그리디 알고리즘으로 풀 수 있지만, 후자는 동적 계획법 백트래킹 등의 조합 최적화 문제의 풀이 방법으로 풀어야 한다.

분할 가능한 배낭 문제를 풀 때는 아이템의 가치를 아이템의 무게로 나눠 단위 무게당 가치가 높은 것들부터 배낭에 담아 문제를 해결한다. 이때 아이템들을 정렬하는데 강의에서 Java에서 정렬에 사용하는 Comparable 인터페이스와 Comparator 클래스를 알려주었다.

Comparable, Comparator

public class CustomComparable implements Comparable<CustomComparable> {
    public Integer value;

    public CustomComparable(Integer value) {
        this.value = value;
    }

    @Override
    public int compareTo(CustomComparable o) {
        return this.value - o.value;
    }
}

CustomComparable a1 = new CustomComparable(2);
CustomComparable a2 = new CustomComparable(1);
CustomComparable a3 = new CustomComparable(3);
CustomComparable[] ccs = new CustomComparable[]{a1, a2, a3};
Arrays.sort(ccs);

Comparable 인터페이스를 이용하여 compareTo 함수를 Override 하여 정렬할 수 있다.

public void compare(Integer[] list) {
    Arrays.sort(list, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
}

또 다른 정렬 방법으로 Comparator 클래스를 이용하여 정렬할 수 있다.
intellij에서 위의 Arrays.sort 부분을 lambda 식으로 변경할 수 있는 힌트를 줘 아래처럼 줄일 수 있다.

Arrays.sort(list, (o1, o2) -> o1 - o2);

탐욕 알고리즘의 한계
탐욕 알고리즘을 사용한다고 해서 반드시 최적의 해를 구할 수 있는 것은 아니기에 어떤 알고리즘을 사용해서 문제를 풀어야 할지 전략을 잘 세워야 한다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.