탐욕적 기법(Greedy Algorithm)

4796 캠핑(3/25)
처음에 최대로 이용할 수 있는 만큼 하고(L일) 쉬다가((P-L)일) 다시 최대로 이용할 수 있는 만큼(L일)을 반복 한다

1) 위의 조건을 함수로 만들어 준다
2) for문으로 case를 반복해 주고 0 0 0이 입력하면 종료되게 한다

@ V / P * L + min(V % P, L) -> 나머지가(V % P) 사용할 수 있는 기간(L)보다 클 수 있으므로 min을 해주어야 한다

1449 수리공 항승(3/26)
물이 새는 곳 위치에서 테이프 길이(L) 더해주거나 빼준다
더해준 값보다 같거나 크고 빼준 값보다 같거나 작은 물이 새는 곳 위치를 똑같이 반복해준다
@ 그냥 먼저 물이 새는 곳의 위치를 오름차순을 해준다

1) 물이 새는 곳의 위치를 빈 배열로 선언해주고 입력 값을 받은 다음 오름차순 해준다
2) 처음 위치 + 테이프 길이 - 1 까지 물이 새는 곳을 막을 수 있다
처음 위치 + 테이프 길이 - 1 < 현재 위치 이면 테이프 개수를 추가해 주고 현재 위치 부터 다시 계산하는 함수를 만든다

17509 And the Winner is… Ourselves!

11047 동전 0(3/26)
동전의 가치에서 A1=1므로 만들 금액 보다 작은 동전의 가치 중 가장 큰 것부터 순서대로 K원을 채우면 된다

1) 동전 가치 10크기의 배열을 만들어 준다
2) for문으로 동전 가치가 제일 높은 것부터 총 금액보다 작은 동전인지 판단한다
3) 총 금액 보다 낮은 동전은 총 금액에서 빼주고 결과가 양수면 빼준 횟수 만큼 count를 올려준다

# 다른풀이: 동전의 가치가 그 전의 배수 이므로
count = count + money / price[i]; money = money % price[i];
for문 안에 위와 같은 방식으로도 할 수 있다 (36ms -> 0ms)

1931 회의실 배정(3/27)

가능한 빨리 끝나는 다음 회의를 선택한다

1) vector<pair<int, int>> a(n)으로 회의 시간을 저장한다

@ 저장한 값은 .first .second로 접근할 수 있다
2) sort를 이용해 끝나는 시간을 기준으로 오름차순 정렬을 한다

@ sort(v.begin(), v.end())를 해주면 first를 기준으로 정렬된다

@ 정렬 기준을 바꾸고 싶으면 compare 함수를 만들어준 뒤 sort(v.begin(), v.end(), compare)를 해준다
3) 현재 회의가 끝나는 시간이 다음 회의가 시작하는 시간보다 작으면 count를 올려준다

 

# sorting 하는데 nlogn의 time complexity가 걸리고, 회의의 최대 개수를 구하는데는 linear한 시간이 소요되기 때문에 이 문제의 time complexity는 nlogn임을 알 수 있다


11000 강의실 배정(3/27)

시작하는 시간으로 오름차순 정렬을 하고 현재 끝나는 시간 보다 다음 시작 시간이 크거나 같으면 Priority Queue를 pop해준다

1) 수업을 시작 시간 기준으로 오름차순 정렬한다
2) 시작시간이 가장 빠른 수업의 끝나는 시간을 Priority Queue에 push한다
@ priority_queue<int, vector<int>, greater<int>> pq는 가장 작은 값이 우선순위가 되는 큐이다(오름차순)
3) for문으로 다음 수업의 종료시간을 Priority Queue에 push한다
4) Priority Queue의 top이 다음 수업의 시작시간보다 작거나 같으면 Priority Queue를 pop한다
5) Priority Queue의 size를 출력한다

1700 멀티탭 스케쥴링(3/27)
멀티탭이 비어 있는 경우 전기 용품을 멀티탭에 꽂고 다른 전기 용품을 꽂을 때 가장 오랫동안 사용 안하는 것을 빼고 꽂는다

1) 멀티탭이 비어 있는 경우 그냥 꽂는다
2) 전기 용품이 이미 멀티탭에 꽂혀있는 경우 지나 간다
3) 전기 용품이 멀티탭에 없는 경우 제일 마지막에 다시 사용되거나 사용될 일 없는 전기 용품을 찾아 콘센트를 뺀다

2212 센서(3/27)
센서 위치를 오름차순 정렬한다
집중국 1개 ->  모든 센서를 관할함
집중국 2개 -> 센서사이의 차 중 제일 긴 부분을 기준으로 각각 집중국이 관할하면 됨
집중국 3개 -> 센서사이의 차 중 다음 긴 부분을 기준으로 그 부분을 또 각각 나누어 관할하면 됨

@ https://excited-hyun.tistory.com/70

1) 센서 위치를 오름차순으로 정렬한다
2) 센서 위치의 차를 구하고 오름차순으로 정렬한다
3) 위치의 차에서 가장 큰 (k-1)개를 제외하고 합을 구해준다

13904 과제(3/28)
과제 점수를 기준으로 오름차순 해주고 마감일에 최대한 가깝게 수행할 과제를 넣어준다

1) vector pair을 사용하고 과제 점수 순으로 cmp 함수를 이용해 오름차순 정렬 해준다
2) 과제 마감일 부터 거꾸로 for문을 이용해 arr에 비어 있는 날을 찾아 1을 넣어준다
3) 비어 있는 날이 있으면 점수를 합산해 주고 break해준다

15748 Rest Stops

1493 박스 채우기