728x90
**본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.**
그리디 알고리즘
: 부분적인 최적 전략을 반복적으로 취하는 알고리즘
당장 보이는 이득을 좇아가는 것도 이 알고리즘의 일부!
★ 그리디 문제 판별법
- 부분적인 최적 전략을 반복적으로 취해서 답을 구할 수 있는 문제
- 부분 문제에 대해 구한 최적해들이 모두 전체 문제의 최적해의 일부인 문제
★ 그리디 문제 접근법
- 문제의 상황이 그리디 알고리즘에 적합한지 살펴본다.
- 어떤 기준으로 순서를 세워, 그 순서대로 처리하면 이득이 되는지 생각해본다.
- 직관 혹은 증명을 통해 어떤 기준이 확실하다면 구현한다.
-> 만약, 그 기준이 보이지 않는다면 DP 등 다른 풀이를 생각해보자.
그리디 문제 유형은 크게 다음과 같이 나누어 볼 수 있다.
- 처리순서 고려
- 제약에 대한 고려
- 최적전략의 반복
관련 문제
- 처리순서 고려
1931. 회의실 배정 (정답코드)
11399. ATM (정답코드)
9237. 이장님 초대 (정답코드)
16206. 롤케이크 (정답코드)
6068. 시간 관리하기 (정답코드)
14908. 구두 수선공 (정답코드) - 제약에 대한 고려
2022.01.23 - [PS/Baekjoon] - [백준/C++] 23559번: 밥(G5)
20921. 그렇고 그런 사이 (정답코드)
11047. 동전0 (정답코드)
1946. 신입사원 (정답코드) - 최적전략의 반복
2022.01.23 - [PS/Baekjoon] - [백준/C++] 13305번: 주유소(S4)
2022.01.14 - [PS/Baekjoon] - [백준/C++] 9009번: 피보나치(S1)
2022.01.14 - [PS/Baekjoon] - [백준/C++] 2437번: 저울(G3)
13413. 오셀로 재배치 (정답코드)
19941. 햄버거 분배
11501. 주식
12931. 두 배 더하기 (정답코드)
728x90
'PS > Algorithm' 카테고리의 다른 글
| [알고리즘 개념정리] 6. 완전탐색/백트래킹 (0) | 2022.01.29 |
|---|---|
| [알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱) (0) | 2022.01.27 |
| [알고리즘 개념정리] 3. 동적계획법(DP) (0) | 2022.01.19 |
| [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)+기초지식 (0) | 2022.01.16 |
| [알고리즘 개념정리] 1. 정렬 (sort STL), 특정 변수 기준으로 정렬하기 (0) | 2022.01.11 |
댓글