참고 영상:https://www.youtube.com/watch?v=PNPIk3hc6ic&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98
그리디(greedy): 당장 눈 앞에 보이는 최적의 상황만 쫓는 알고리즘
특징
1.특정 상황에서는 최적의 해를 보장할 수도 있다.
2.극단적이다.
3.정렬이 많이 쓰인다.
ex) 거스름돈
560원을 거슬러준다 치면 10원짜리 56개보다 500원 1개 50원 1개 10원 1개가 더 편하다. 즉 "무조건 더 큰 화폐단위부터 거슬러준다."는 알고리즘만 지키면 최적의 해를 보장할 수있다.
백준에 있는 그리디 5문제를 쉬운거부터 풀어보자
백준 11047 동전 0
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
쉬워서 설명 생략,다음 가보자
백준 1931 회의실 배정
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
5문제 중에 제일 어려운 문제인 것 같다.
하나도 모르겠다.
그리디에서는 정렬을 많이 쓴다고 했다. 정렬을 써보자.
여기서 조건은 "회의가 빨리 끝나야 한다."이다.
일단 삽입정렬로 끝나는 시간이 빠른 순서대로 정렬한다.
처음에 이렇게 짰다가 예외를 놓쳤다.
끝나는 시간이 겹치는 경우를 생각 안 했다.
ex)
2 2
1 2
로 들어오면 1 2를 카운트하지 않는다.
그래서 정렬을 두 번해야 한다.
1.끝나는 시간 순으로 오름차순 정렬하고
2.그 후 다시 시작 시간 순으로 오름차순 정렬해야 한다.
그냥 위에 썼던 코드를 살짝 수정하였다.
근데 이거 쓰니까 시간초과가 뜬다... 아무래도 정렬이 느려서 그런 것 같다.
일단 정렬 공부하고 있는게 아니니까 파이썬의 sort()를 이용해서 맞추었다.
다음 문제를 풀어보자
백준 11399 ATM
"최소"가 되려면 무조건 금방 끝나는 사람이 앞에 있어야 한다.
오름차순 정렬을 해주고 배열에 더해주었다.
파이썬에서 배열을 복사할 때 그대로 넣으면 얕은 복사(주소값만)가 된다. 그래서 map함수를 이용하여 깊은 복사(값 복사,독립된 인스턴스 생성됨)를 해주었다.
백준 1541 잃어버린 괄호
이런 문자열 문제는 파이썬이 정말 유리한 것 같다.
1.일단 -를 기준으로 분리해서 리스트에 저장한다.- ~ - 전부 괄호를 치는 셈이다.
2.리스트의 첫 번째 원소만 양수고 나머지는 전부 음수로 칠 수 있다.
백준 13305 주유소
초기에는 무조건 첫 번째 도시에서 기름을 채워야 하므로 초깃값들 세팅
그 후 조건을 분기한다.
1.현재 도시 기름값 \< 다음 도시 기름값인 경우
현재 도시 기름값 현재-다음다음 도시 거리
다음 도시의 인덱스만 옮기고 현재 도시는 유지한다.
2. 반대의 경우
다음 도시 기름값 다음-다음다음 도시 거리
다음 도시의 인덱스,현재 도시의 인덱스를 모두 한칸 씩 옮긴다.
다음다음 도시 거리를 곱하는 이유는 현재 도시에서 다음-다음다음 도시를 갈 분량의 기름을 채울지 말지 결정하는 것이기 때문이다.
