[PCCP] 알고리즘 - 그리디

1. 이론

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

- 특정한 상황에서 사용 가능

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

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

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

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

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

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

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

- 예제

    - 거스름 돈 문제

    - Knapsack Problem(배낭문제): 부분 배낭문제 / 01배낭문제

 

2. 언어별 문법

<C++>

 

<Python>

 

3. 추천 문제

<Programmers>

- Lv1: 예산

- Lv1: 체육복

- Lv2: 구명보트

- Lv2: 귤 고르기

- Lv2: 큰 수 만들기

- Lv3: 단속카메라

- Lv3: 기지국 설치

 

참고자료

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

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

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