그리디

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net [문제] [풀이] 왼쪽에서 오른쪽으로 파이프를 쭉 연결해야 하는데 , 최대한 많이 연결해야 한다. 그러기위해선 2가지의 조건을 생각해야한다. 1. [오른쪽위 , 오른쪽, 오른쪽아래] 순서대로 연결해야함 => 만약 y좌표가 0번째에서 출발해서 맨 오른쪽 아래에 꽂히면 다른 1~n 번째에서는 절대 연결이 불가능 2. 이 문제는 백트래킹문제가 아니라 그리디 문제이기 때문에 모든 경우를 따지면 안된다 => 종결조건에 다..

https://programmers.co.kr/learn/courses/30/lessons/92343 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr [문제] [풀이] 처음엔 트리 DP 문제인줄 알고 접근했었다가 다시 돌아올 수 있다는 조건때문에 풀지 못했었다. 이 문제는 오히려 중복체크를 하지 않아도 되기때문에 그리디+탐색으로 충분히 풀 수 있었다. 1. 탐색..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr . [문제] [풀이] 낮은 스코빌 지수의 음식 2개를 뽑아서 새로운 음식을 만드는데 스코빌 지수가 K 보다 높을 떄 까지 반복한다. 계속 해서 낮은 수치의 값이 필요하므로 우선순위큐를 사용. 음식을 섞으려면 2개를 뽑아야 하는데 2개가 없다면 -1 를 리턴 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 풀이 이전에 풀었던 컵라면 문제와 동일하다. https://katastrophe.tistory.com/73 1. 기간순으로 오름차순 정렬된 우선순위 큐(q1)에 삽입 2. 페이 순으로 오름차순 정렬된 우선순위 큐(q2)에 삽입 2_1. 삽입한 원소의 기간보다 q2의 사이즈가 더 크면 큐의 맨 앞의 원소를 poll. ( 더 적은 페이를 제거 ) 3. q2를 ..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net [문제] [풀이] 문제의 조건을 만족하기위해선 데드라인을 만족과 동시에 컵라면을 제일 많이 받을 수 있는 쪽으로 해야한다. 현재 경과 일을 i 라고하면 , i 이상의 데드라인 문제들을 풀 수 있지만 i 이전의 문제들을 풀 수 없다. 즉 , i 이상의 데드라인 문제들을 보면서 컵라면이 제일 많은 순으로 가져가야함. 경과일마다 처리해야하는 문제들을 1부터 차례대로 보기위해 데드라인순으로 우선 오름차순정렬을 한..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net [문제] [풀이] 정렬 , 그리디 문제이다. 책을 제자리에 놓기위해 그 만큼 전진을 해야하는데 , 최대 M권을 같이 들고갈수 있기 때문에 기준점으로부터 제일 멀리있는 지점을 고르면 m-1개는 가는길에 갖다 놓을 수 있기때문에 우선 제일 멀리있는 지점을 찾아야 한다. 그러나 제일 마지막에 놓는 책은 다시 돌아올 필요가 없기 때문에 편도로 한번만 가고 나머지는 왕복처리하면 끝. 우선순위 큐를이용해서 양수면..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 풀이 [마감일 , 점수] 쌍으로 여러 입력이 주어지는데 , 예제를 보자 [6 , 5] [4, 60] 의 경우 6일마감 과제는 4일차 때 수행할 수 있지만 , 4일마감 과제는 6일차 때 수행할 수 없다. 즉 , 마감일이 늦은 순으로 처리를 먼저 하되 그때 처리할 수 있는 과제 중에서 점수를 가장 많이 주는것을 해야한다. 결론적으로는 주어진 입력에 대해서 1. 마감일이 늦은 순으로 내림차순 정렬 2. 점수를 많이주는 순으로 내림차순 정렬 ..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 풀이 단순 그리디 접근 방법으로 풀 수 있다. 1. 상자랑 크레인을 입력받아 무거운 순 으로 정렬 2. 크레인 갯수 만큼 상자를 순회하여 만약 크레인이 이 상자를 적재 가능하면 상자리스트에서 제거 3. 다음 크레인으로 상자를 순회하여 적재가능하면 또 제거 .. 이런식으로 반복 4. 크레인을 순회할때마다 시간1초씩 늘려주고 , 상자리스트가 is.Empty()면 끝 1 2 3 4..