본문 바로가기

Algorithm/Greedy

 (43)
(C++) - 백준(BOJ) 1715번 : 카드 정렬하기 www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net min heap을 사용해 푼 문제였습니다. 풀이방법 1. 카드 묶음을 입력 받고 minHeap에 push해줍니다. 2. 카드 두장을 뽑고 답 변수 ans에 더해준 다음 합쳐진 카드를 다시 minHeap에 push합니다. Code #include using namespace std; int n, card; int main(){ int ans = 0; cin >> n; priority_queue mi..
(C++) - 백준(BOJ) 2217번 : 로프 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 귀류법으로 greedy로 푸는 것이 합당한지 검증합니다. 귀류법이란 세운 명제에 반하는 명제를 세운 후 해당 명제가 거짓임을 보여 결론적으로 기존 명제가 참임을 증명하는 방법입니다. 먼저 가정을 세웁니다. 가정 : 들어올릴 수 있는 중량이 최대인 로프를 선택하면 최대 중량을 들어올릴 수 있다. 반하는 가정 : 들어올릴 수 있는 중량이 최소인 로프를 선택하면 최대 ..
(C++) - 백준(BOJ) 1700번 : 멀티탭 스케줄링 답 www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net greedy문제였습니다. 풀이방법 플러그를 꽂는 방법을 생각해야 합니다. 1. 전기용품 이름이 현재 멀티탭에 꽂혀있는 경우 : 뺄 필요가 없습니다. 2. 전기용품 이름이 현재 멀티탭에 꽂혀있지 않은 경우 : 빈 멀티탭에 꽂아줍니다. 3. 멀티탭이 모두 차서 빼야되는 경우 : 앞으로 사용되지 않는 용품이거나 가장 나중에 사용되는 용품인 경우 이 제품을 빼줘야합니다. 따라서 모든 multiTap 구멍을 찾아서 꽂혀..
(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번째 학생이 체육복이 없다면 양 옆 여분이 있는 학생(체육복 보유..

티스토리툴바