Greedy

✅ 현재 상황에서 좋은 것만 고르는 방법, 나중에 미칠 영향에 대해서 고려 X

PS. 다익스트라 알고리즘 = 그리디 알고리즘으로 분류, 암기 필요! 그리디 자체가 문제 출제의 폭이 넓어.. 현재 상황에서 가장 좋은 것만 선택해도 문제 풀 수 있는지 파악할 수 있어야 한다!

기준에 따라 좋은 것을 선택하는 알고리즘으로, 문제에서 “가장 큰 순서대로”, “가장 작은 순서대로” … 정렬 사용했을 때 만족 할 수 있으므로 ‘정렬 + 그리디’로 자주 출제

🟢 거스름돈
‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것

❓ 그리디 알고리즘의 정당성
거스름돈 문제에서 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 가능

💚 백준 2839 - 설탕배달

• 입력: n
• 출력: 배달하는 봉지의 최소 개수 (5kg, 3kg 이용)

n이 5로 모두 나눠지는경우, 3kg 이용하는 경우, 실패할 경우 존재

💚 백준 11399 - ATM

• 입력: n
• 출력: 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값

배열로 입력 받고 정렬 후 누적 합 출력
인출 시간이 적은 사람부터 처리하고 나가면 된다.

sort(arr, arr+size);

💚 백준 11047 - 동전0

• 입력: N, K, 동전의 가치
• 출력: K원을 만드는데 필요한 동전 개수의 최솟값

거스름돈 계산이랑 똑같다ㅎ
배열 첫번째 포함 안하고 제출해서 3번째 성공!

ans += k / a[i];
k %= a[i];

💚 백준 1931 - 회의실 배정

• 입력: 회의의 수 N, 2 ~ N+1 줄까지 각 회의의 정보(시작시간, 끝나는 시간)
• 출력: 최대 사용할 수 있는 회의의 최대 개수

어디서 많이 본 그리디 예제ㅎㅎ

vector<pair<int, int>> v;
v.push_back(make_pair(end, start));
sort(v.begin(), v.end());

💚 백준 1026 - 보물

• 입력: n, n개의 수 A&B (S = A[0] × B[0] + … + A[N-1] × B[N-1])
• 출력: S의 최솟값

(B는 재배열하면 안된다!)

bool compare(int a, int b){ return a > b; }
sort(a, a + n, compare);

💚 백준 1541 - 잃어버린 괄호

• 입력: 식
• 출력: (적절한 괄호 사용) 식의 최소

주어진 식이 55-50+40 일때 55-(50+40) 처럼 빼는 수의 크기를 크게 하면 될거같은데
c++에서 split 어떻게 하는지 모름..

stoi() // string to int

💚 백준 2217 - 로프

• 입력: 정수 n, n개의 로프 중량
• 출력: 물체의 최대 중량 (각각의 로프에 w/k의 중량 걸려)

뭔소리야.. 예시를 더 줘ㅠㅠ
5개의 로프 {27, 23, 15, 11, 3} 가 주어지면?
23 * 2 = 46 이 최대

sort(v.rbegin(), v.rend()); // 내림차순 정렬

💚 백준 10162 - 전자레인지

거스름돈을 따로따로 계산하는 느낌이랄까?

a = t / 300;
b = (t % 300) / 60;
c = ((t % 300) % 60) / 10;

💚 백준 1789 - 수들의 합

• 입력: 자연수 s
• 출력: n의 최댓값(n개의 자연수의 합 = s)

EX) S=200, N=19
1+2+3+…+19 = 190
1+2+3+…+19+20 = 210
작은 수부터 더해나가면 ㅇㅇ

💚 백준 13305 - 주유소

• 입력: 도시의 개수 n, 도로의 길이, 리터당 가격
• 출력: 왼쪽 -> 오른쪽 도시로 가는 최소 비용

그만해야지..(2022.07.25)