본문 바로가기

Algorithm/Greedy

 (40)
(C++) - 프로그래머스(고득점 kit - Greedy) : 구명보트 programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr two pointer로 구현한 문제였습니다. 풀이방법 1. 사람 몸무게를 내림차순으로 정렬합니다. 2. 구명보트를 배치합니다. 2-1. 가장 몸무게가 무거운 사람을 l번째로 가벼운 사람은 r번째 사람으로 정의합니다. 2-2. people[l] + peple[r] > limit이라면 몸무게 제한을 초과합니다. 이 때는 r을 옮기더라도 가장 작은수가 r..
(C++) - 백준(BOJ) 11000번 : 강의실 배정 답 www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이방법 1. 강의 시작시간이 빠른 것이 우선, 만약 강의 시작시간이 같다면 끝나는 시간이 먼저 오도록 정렬해줍니다. 2. min heap pq(끝나는 시간이 빠른 것이 위로 가도록)를 사용해 강의실을 배정합니다. 우선순위 큐의 원소에는 강의 끝나는 시간이 들어갑니다. top()이 강의 시작시간 이하라면 이 강의는 한 강의실에서 이어받으면 되므로 pop 합니다. 이 후 해당 강의의 끝나는 시간을 넣어줍니다. Code #include using namespac..
(C++) - 백준(BOJ) 1449번 : 수리공 항승 답 www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 물이 세는 위치를 저장할 배열을 선언하고 입력받습니다. 오름차순 입력 보장이 안되므로 입력 후에는 오름차순으로 정렬해줍니다. 2. 테이프가 칠해지지 않은 곳을 발견하면 그 위치부터 + l까지 1000을 안넘는 공간에 한해 테이프를 붙입니다. 그 후 테이프의 개수를 저장하는 변수 ans를 1더해 줍니다. Code #include using namespace ..
(C++) - 백준(BOJ) 4796번 : 캠핑 답 www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net greedy문제였습니다. 풀이방법 1. v/p*l일 수 만큼 캠핑을 먼저 갑니다. 2. 나머지 갈 수 있는 캠핑 일 수를 더해줍니다. v%p > l >> p >> v; if(!l && !p && !v) break; caseCnt++; int ans = v/p*l; if(v%p
(C++) - 프로그래머스(고득점 kit - Greedy) : 체육복 programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr greedy문제였습니다. 풀이방법 1. 학생별 체육복 보유 여부를 판별하기 위한 vector선언 2. 체육복을 잃어버린 학생들은 해당 vector의 index를 0으로 만들어줍니다. 3. 그 후 체육복 여분을 가지고 학생의 index를 1씩 증가시켜줍니다. 4. n까지 학생들을 loop를 돌며 확인합니다. 만약 i번째 학생이 체육복이 없다면 양 옆 여분이 있는 학생(체육복 보유..
(C++) - 백준(BOJ) 1931번 : 회의실배정 답 www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정렬 후 회의가 끝나는 시간이 가장 낮은 회의 순으로 배정하시면 됩니다. 풀이방법 1. 회의가 끝나는 시간을 기준으로 오름차순 정렬 2. 회의가 끝나는 시간이 같을경우엔 회의 시작시간을 기준으로 오름차순 정렬 3. 끝시간이 다음 회의 시작 시간보다 작을 때는 회의를 배정 4. 배정했던 회의개수 답 출력 Code #include #include #include using namespace std; int n; int ans; vector v(100000); bool cmp(const pair &a, const pair &b){ i..
(C++) - 백준(BOJ)코딩 11047번 : 동전0 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net greedy 문제였습니다. greedy로 푸는 것이 수학적으로 맞는지를 검증하는지가 중요합니다. 감으로 의존해 푸시면 제대로 문제를 풀 수 없습니다. 좋은 방법 중 하나는 귀류법으로 자신이 세운 가정이 맞는지를 증명해보는 것입니다. 귀류법을 통해 현재 최대 이익을 얻지 않으면 발생되는 손해가 있는지의 여부를 알 수 있습니다. 풀이방법 귀류법으로 증..
(C++) - 백준(BOJ)코딩 1026번 : 보물 www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net greedy 문제였습니다. 풀이방법 상식적? 감으로 생각했을 때 S의 값을 가장 적게 만들기 위해서는 제일 작은 수를 제일 큰 수끼리 짝지어서 곱해주었을 때 그 합이 최소가 됩니다. 문제에서 B의 수는 재배열하면 안되지만 A는 옮길 수 있습니다. 이 말은 자칫 B를 고정하고 A를 한 칸씩 옮기는 brute force를 생각할 수 있으나 A,B 둘다 옮길 때와 A의 원소들만을 옆으로 옮겨줄 때는 같다는 생..

티스토리툴바