https://www.acmicpc.net/problem/22864
22864번: 피로도
첫 번째 줄에 네 정수 $A$, $B$, $C$, $M$이 공백으로 구분되어 주어진다. 맨 처음 피로도는 0이다.
www.acmicpc.net
피로도, 난이도: 브론즈 2
그리디보다는 구현에 가까운 유형, 반복문을 통해 가장 큰 값을 선택한다.
https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성
www.acmicpc.net
신입사원, 난이도: 실버1
실버 1이지만 상당히 어려움... 체감상 골드 4~5
신입 사원의 서류 성적을 기준으로 정렬한 뒤, 면접 시험 점수를 비교.
정렬의 중요성을 느끼게 되는 문제였다.
https://www.acmicpc.net/problem/11501
11501번: 주식
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타
www.acmicpc.net
역순으로 탐색하는 것이 중요한 문제였다.
그리디는 탐색 방식도 중요하다는 것을 알 수 있었다.
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
회의실 배정, 스탠다드한 그리디 문제이다.
난이도: 실버1
그리디 기준은 끝나는 시간이며, 비슷한 문제인 최소 회의실 개수는 골드 5로
start 기준으로 봐야했다.
그리디는 정당성 증명과, 시작, 끝 기준이 중요하다는 것을 알 수 있었다.
https://www.acmicpc.net/problem/1700
1700번: 멀티탭 스케줄링
기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전
www.acmicpc.net
멀티탭 스케줄링
난이도: 골1
가장 늦게, 가장 적게 등 빈도나 시점을 기준으로 정렬하는 그리디 기준도 중요하다는 것을 알 수 있었다.
https://www.acmicpc.net/problem/1339
1339번: 단어 수학
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대
www.acmicpc.net
단어 수학
난이도: 골4
정렬이 중요하다는 내용과도 겹치지만 이것은 정렬 기준이 독특하다.
가중치를 기준으로 정렬을 하는 것이다.
정렬시 가중치를 고려해주어야한다.
그리디는 정렬 기준, 가중치가 중요하다.
그리디 전략 정리:
1. 정렬 기준을 잡아라
2. 시점, 빈도를 기준으로 그리디를 시행해보라
3. 역순 탐색 등 탐색 기준도 정하라
4. 정당성을 증명하라
5. 가중치를 고려해 정렬 기준도 고민하여라
6. 구현하라
'알고리즘, 코딩전략' 카테고리의 다른 글
| [PS일지]큐, 스택, 덱 (0) | 2021.08.09 |
|---|