Ch3. 그리디 greedy
1. 당장 좋은 것만 선택하는 그리디
- 현재 상황에서 당장 좋은 것만을 골라 현재의 선택이 나중에 미칠 영향은 고려하지 않는 방법
- 보통 코딩 테스트에서 출제되는 유형은 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
특정한 문제를 만났을 때, 그리디로 문제를 풀 수 있을지 파악할 수 있어야 한다.
- 기준에 따라 좋은 것을 선택하는 알고리즘이기에 기준을 제시해주고, 정렬 알고리즘과 함께 짝을 이루어 출제된다.
1-1. 예제 거스름돈
- 문제
- 소스 코드
- 정당성
: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 X
때문에 화폐이 단위가 무작위로 주어졌을 때에 그리디 알고리즘으로 해결할 수 없다.
1-2. 그리디 알고리즘의 정당성
- 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없는 가능성이 다분하다.
따라서, 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토할 수 있어야 한다.
Tip. 그리디 -> 다이나믹, 그래프 알고리즘
2. 큰 수의 법칙
- 문제
- 문제 해결
: 가장 큰 수와 두번째로 큰 수를 저장한다. 연속으로 더할 수 있는 횟수는 최대 K번이므로
'가장 큰 수를 K번 더하고, 두 번째로 큰수를 한 번 더하는 연산'을 반복하면 된다.
- 소스 코드 1(python, M이 10,000 이하일 때)
- 소스 코드 2(python, M이 100억 이상일 때)
: 반복되는 수열 first와 second가 더해질 때 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.
반복되는 수열의 길이는 (K+1)이고 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.
여기에 (K+1)*M은 first가 반복하는 횟수가 되고, M이 (K+1)로 나누어 떨어지지 않는 것을 고려했을 때,
'가장 큰 수가 더해지는 횟수는 int(M/(K+1)) * K + M%(K+1)'
- 소스 코드 3(c++, M이 100억 이상일 때)
3. 숫자 카드 게임
- 문제
- 문제 해결
: 각 행마다 가장 작은 수를 찾은 뒤에 작은 수들 중에서 가장 큰 수를 찾는 것이다.
- 소스 코드
4. 1이 될 때까지
- 문제
- 문제 해결
: 주어진 n에 대하여 최대한 많이 나누기 연산을 수행하면 된다.
- 소스 코드
'Algorithm&Problem > [Algorithm] 이.코.테.다' 카테고리의 다른 글
[6일차] 이.코.테.다! Ch5 DFS/BFS (0) | 2020.09.22 |
---|---|
[5일차] 이.코.테.다! Ch4 구현 Implementation (0) | 2020.09.20 |
[3일차] 이.코.테.다! Ch2 16~20년 코테 기출 유형 분석 (0) | 2020.09.12 |
[2일차] 이.코.테.다! Ch1 코딩테스트 개요 (0) | 2020.09.11 |
[1일차] 이.코.테.다! Ch0 들어가기 전에! (0) | 2020.09.10 |