[코딩테스트] Java - 탐욕법(Greedy)

탐욕법

- 탐욕법(greedy): 문제 해결 과정에서 결정 순간마다 눈앞에 보이는 최선의 선택을 하며 선택을 번복하지 않음. 부분적으로 최적해를 구함

- 그리디의 최적해 보장 조건: 최적 부분 구조 + 그리디 선택 속성

+) 최적 부분 구조(optimal substructure): 부분해를 푸는 과정이 최적해를 구하는 과정과 일치

+) 그리디 선택 속성(greedy selection property): 선택 과정이 다른과정에 영향을 주지 않음

 

(그리디 풀이법)

- 지역의 최적해 구하기

- 최적 부분 구조를 만족하는지 확인

- 그리디 선택 속성을 만족하는지 확인

 

(최소 신장 트리)

- 신장 트리(spanning tree): 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프

- 최소 신장 트리(minimum spanning tree): 신장 트리 중 간선의 가중치의 합이 최소인 경우

- 최소 신장 트리 알고리즘: 프림 알고리즘(prim's algorithm), 크루스칼 알고리즘(kruskal algorithm)

 

(Prim's Algorithm)

- 시간복잡도: 인접리스트 O(E*logV), 인접행렬(O(N^2))

1. 임의의 점점 하나를 선택하여 최소 신장 트리에 추가

2. 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가.(순환을 형성하지 않아아 함)

3. 과정 2를 신장 트리 조건에 만족할 때까지 반복

 

(Kruskal Algorithm)

- 시간복잡도: O(E*logE)

1. 그래프의 모든 간선을 가중치 기준으로 오름차순으로 정렬

2. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가.(순환을 형성하지 않아야 함)

3. 과정2를 신장 트리 조건에 만족할 때까지 반복

 

(배낭 문제)

- 배낭 문제(knapsack problem): 배낭에 담을 수 있는 최대 무게가 존재하고 무게와 가치가 다른 짐들을 잘 조합하여 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제

- 배낭 문제의 유형: 부분 배낭 문제(fractional knapsack problem), 0/1 배낭 문제(0/1 knapsack problem)

 

(부분 배낭 문제): 짐을 나눌 수 있음

- 시간복잡도: 부분 배낭 문제 O(N*logN)

1. 짐별로 무게당 가치를 구함

2. 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣음(짐 쪼개기 가능)

3. 과정 2를 배낭이 허용하는 용량이 0이 될 때까지 수행

 

 

(0/1 배낭 문제): 짐은 나눌 수 없음

- 시간복잡도: 0/1배낭 문제 O(N*W)

- 그리디로 해결 불가: 현재 선택한 짐이 다른 짐의 선택에 영향

- 동적계획법으로 접근

 

예제

(거스름돈 내어주기)

- 입력: money(거스름돈), coins(화폐 단위 리스트)

- 출력: 화폐 단위별 사용 개수를 반환(화폐 단위가 큰 순서 기준)

import java.util.*;

class Solution {
    private static int[] solution(int money, int[] coins) {
        Arrays.sort(coins, Collections.reverseOrder());
        
        ArrayList<Integer> change = new ArrayList<>();
        for (int coin: coins) {
            if (money >= coin) {
                change.add(money / coin);
                money %= coin;
            }
        }
        return change.stream().mapToInt(Integer::intValue).toArray();
    }
}

(부분 배낭 문제)

- 입력: items(무게와 가치가 있는 짐들의 리스트), weight(배낭의 허용 무게)

- 출력: 사용한 짐들의 개수(소수점 포함)

ㅇ