[PCCP] 알고리즘 - 그리디

1. 이론

- Greedy:

    - 지역 최적해를 구함. 전역 최적해 장담 불가.

    - 해결과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택을 번복하지 않음

- 그리디 알고리즘 최적해 보장 조건

    - Optimal Substructure(최적 부분 구조): 부분해 과정이 최적해 과정과 일치

    - Greedy Selection Property(그리디 선택 속성): 선택과정이 다른 과정에 영향을 주지 않음

- Spanning Tree

    1) 모든 정점이 간선으로 연결

    2) 간선의 개수는 (정점의 개수 - 1)과 동일

- Minimum Spanning Tree(최소신장트리)

    1) 모든 정점이 간선으로 연결

    2) 간선의 개수는 (정점의 개수 - 1)과 동일

    3) 간선의 가중치의 합이 최소일 경우 성립

 

- 알고리즘 종류: Prim's Algorithm / Kruskal Algorithm

 

- Prim's Algorithm: O(E*logV)
1. 임의의 정점을 하나 선택해서 최소 신장 트리에 추가
2. 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가(그리디적 선택). 단, 순환을 형성하지 않는 정점을 추가
3. 2를 신장 트리 조건에 만족할 때까지 반복

 

- Kruskal's Algorithm: O(E*logE)
1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가(그리디적 선택). 단, 순환을 형성하지 않아야 함
3. 2를 신장 트리 조건에 만족할 때까지 반복

 

+) 다익스트라 알고리즘의 목적: 시작 노드에서 각 노드까지 가는데 필요한 간선의 가중치 합을 최소
+) 최소 신장 트리의 목적: 모든 노드를 연결되게 하면서 모든 간선의 가중치 합을 최소로(간선의 개수=정점의 개수 - 1)
=> 산책 코스를 고민할 때는 다익스트라 알고리즘 사용, 여러 도시를 연결할 도로를 건설할 때는 최소비용으로 도시를 연결하기 위한 최소 신장 트리 알고리즘 사용.

 

- 예제

    - 거스름 돈 문제

    - Knapsack Problem(배낭문제): 무게와 가치가 다른 짐들을 잘 조합해서 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제
    - fractional knapsack problem(부분 배낭 문제): 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 사용. O(N*logN)
    - 0/1 knapsack problem(0/1 배낭 문제): 짐을 쪼갤 수 없어 현재 선택한 짐이 다음 짐 선택에 영향. O(N*W)

 

2. 언어별 문법

<C언어>

 

 

<C++>

 

 

<C#>

 

 

<Java>

 

 

<Python>

 

 

<JavaScript>

 

 

3. 추천 문제

<Programmers>

- Lv 1: 예산(12982) / 예산(12982) 해설

- Lv 2: 구명보트(42885) / 구명보트(42885) 해설

- Lv 2: 귤 고르기(138476) / 귤 고르기(138476) 해설

- Lv 3: 기지국 설치(12979)/ 기지국 설치(12979) 해설

 

- Lv 1: 체육복(42862) / 체육복(42862) 해설
- Lv 3: 단속카메라(42884) / 단속 카메라(42884) 해설
- Lv 2: 큰 수 만들기(42883) / 큰 수 만들기(42883) 해설

 

 

참고자료

- 이것이 코딩테스트다 2021 그리디/구현

- 코딩테스트 필수 알고리즘(시뮬레이션)

- 코딩테스트 합격자되기(파이썬) 16. 그리디