본문 바로가기

Greedy

(5)
[문제해결기법] 5. 욕심쟁이 기법 1. 욕심쟁이 알고리즘 : Greedy algorithm 매 단계마다 각 단계에서 최선의 선택을 한다. (현재 순간마다) 알고리즘이 매우 간단하나, 구한 답이 정답인지 검증이 필요하다. 기본 형태 2. 회의실 배정 문제 한 개의 회의실이 있는데, n개의 회의 일정이 있고 이 회의실을 이용하여 회의한다. 각 회의 i에 대해서 시작 시간 Si와 끝 시간 Fi가 주어진다. 각 회의가 겹치지 않게 하면서 가장 많은 횟수의 회의를 할 수 있도록 일정을 구하는 프로그램을 작성하시오. ❖ 입력 ➢ 첫 줄에는 회의의 수 n ➢ 둘째 줄부터 n+1줄까지 두 정수 Si와 Fi ❖ 출력 ➢ 잡은 회의를 차례대로 출력(둘 이상의 답이 있을 수 있음) 가능한 접근 방법 - 회의시간이 짧은 것 부터 넣는다 -> 반례 존재 - 다..
[C++/PGS] Lv.2 : 구명보트 (GREEDY) https://school.programmers.co.kr/learn/courses/30/lessons/42885# 문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때..
[C++/PGS] Lv.1 : 체육복 (GREEDY) 탐욕법 (Greedy) : 체육복 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때..
[코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다. 하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만, 4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다. 그런데 다음 경우는 어떨까요? 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다. 그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다. 따라서 배수 ..
[알고리즘] Greedy algorithm - 이집트 나눗셈(cpp) 문제 이집트 나눗셈을 하는 프로그램을 작성하시오. 입력 p/q를 나타내는 두 정수 p, q가 사이에 공백을 하나 두고 주어진다. p는 1 이상 1,000 이하, q는 p+1 이상 2,000 이하인 정수 출력 수업 시간에 배운 이집트 나눗셈의 결과로 몇 개의 분수가 나오는지 출력한다. 예를 들어, 5/6은 1/2 + 1/3이므로 2개의 분수가 필요하다. 예제 입력 1 5 6 예제 출력 1 2 예제 입력 2 19 20 예제 출력 2 4 알고리즘 수업의 첫 과제였다. 이집트 나눗셈이란, 유리수 p/q가 주어지면 분자가 1인 분수들의 합으로 p/q를 표현하는 것이다. 예) 5/6 = 1/2 + 1/3 , 3/4 = 1/2 + 1/4 욕심쟁이 기법, 흔히 Greedy 알고리즘이라고 부르는 기법을 사용하여 풀이할 ..

728x90