그리디란?
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 방법
-> 단계별로 진행한다 할때, 뒷 상황을 고려하지 않고 현재 상황에서 best 선택지를 픽
-> 이렇게 선택할때 최적의 해를 보장하지는 않음(뒷 사항을 고려하지 않았기에)
그리디로 풀 것인지 판단하는 과정이 되게 중요!
밑 3단계 반복
1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약조건에 벗어나지 않는지 검사
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할수 있는지 검사, 해결 못한다면 1로 돌아감
그리디 이해 예시
예 :
620원이 있다면, 620원 이하의 가장 큰 액수가 500원짜리이므로
먼저 500원짜리 동전을 하나 사용하고, 120원이 남습니다.
이제 500원짜리는 못 쓰죠. 대신 그 다음으로 큰 100원짜리를 사용할 수 있습니다.
그리고 남은 20원은 10원짜리 2개를 사용할 수밖에 없고 이렇게 하면 답은 동전 4개가 됩니다.
880원의 경우는 마찬가지로 500+100+100+100+50+10+10+10으로 나타낼 수 있고 답은 8위와 같은 과정이 성립하는 이유
-> 반드시 큰 쪽이 작은 쪽 액수의 배수이기 떄문
저 배수라는 성질이 성립하지 않으면 이 성질도 깨지고, 그리디 알고리즘도 더이상 사용할 수 없습니다.
60, 50, 10원짜리 동전을 사용한다고 해봅시다. 이제 60은 50보다 크지만 50의 배수는 아니죠.
이때 220원을 표현하려고 하면, 60원짜리부터 무작정 사용하다 보면 3개 동전을 사용하고 40원이 남는데 이건 10원짜리 4개로밖에 나타낼 수 없으므로 총 7개를 사용하게 됩니다.
그러나 답은 50원짜리 4개와 10원짜리 2개를 사용하여 6개가 가능하지요.
문제1(동전 0) - 실버 4
https://www.acmicpc.net/problem/11047
그리디로 풀수있도록 뒤의 동전 가격이 앞에 나오는 동전 가격의 배수가 된다는 조건을 부여
-> 이때 최소로 사용하기 위해서는 가장 가격이 큰 동전부터 차례대로 사용
문제2(캠핑) - 브론즈 1
https://www.acmicpc.net/problem/4796
문제에서 주어진 캠핑장은 연속하는 P일 중 L일 동안만 사용할 수 있음
-> 따라서, 가장 많은 캠핑일을 누리기 위해 캠핑장을 사용할 수 있는 기간 중 최대한 사용
가장 간단한 문제
문제3(수리공 항승) - 실버3
https://www.acmicpc.net/problem/1449
테이프의 끝을 활용해서 문제를 풀자~
문제4(회의실 배정) - 실버1
https://www.acmicpc.net/problem/1931
그리디를 활용하는 대표적인 문제중 하나
-> 그리디라고 생각안하고 풀었으면.. 꽤나 어려웠을것 같다
회의가 빨리끝나는 순서대로 선택(시간은 안겹치게)
문제 5(강의실 배정) - 골드5
https://www.acmicpc.net/problem/11000
문제는 간단했지만 생각하는 과정이 복잡했다..(우선순위큐를 사용하였음)
-> 특히 queue.offer()을 할때 어떠한 경우에 강의실을 새로 만들어줘야할까를 잘생각해야함...
문제 6(센서) - 골드 5
https://www.acmicpc.net/problem/2212
위 풀이를 참고하자... 솔직히 문제보고 어찌 풀어야 할지 감도잡히지 않았다 ㅠㅠ
문제 7(멀티탭 스케줄링) - 골드 1
https://www.acmicpc.net/problem/1700
이 문제는 그리디로 풀어야 겠다고 인지하는것은 쉬웠는데... 구현이 어려웠따...
-> 인터넷을 참고해서 풀었으니 구현을 다시 한번 잘해보자 ㅠㅠ
문제 8(과제) - 골드 3
https://www.acmicpc.net/problem/13904
생각을 좀 잘해보면 구현해보기는 쉬운 문제
-> 구현할때 priorityQueue를 사용했는데 굳이 사용하지 않아도됨
문제 9(카드 정렬하기) - 골드 4
조금만 잘생각하면 풀기 괜찮음!
문제 10(수 묶기) - 골드 4
https://www.acmicpc.net/problem/1744
문제 11(잃어버린 괄호) - 실버 2
https://www.acmicpc.net/problem/1541
정규표현식을 잘써야 풀기 좋은 문제
-> 로직 자체는 쉬움
