# greedy

timosean

문제 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routesi에는 i번째 차량이 고속도로에 진입한 지점, routesi에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다. 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다. 입출력 예시 ![](https://velog.velcdn.com/images/timosean/post

timosean

문제 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한 사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costsi 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다. 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어

timosean

문제 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한 사항 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다. 각 사람의 몸무게는 40kg 이상 240kg 이하입니다. 구명보트의 무게 제한은 40kg

timosean

문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 사항 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 풀이 아이디어 스택을 이용한다. (answer을 스택으로 만든다) Greedy하게 진행한다. 즉, numbers를 순회하면서, 다음 로직을 수행한다. 만약 answer가 비어있지 않으면서 k > 0이고,

khhkmg0205

Greedy Algorithm 🎃 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 그리디 알고리즘, 또는 욕심쟁이 알고리즘, 탐욕 알고리즘 등등으로 불린다. 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 지역적으로는 최적의 답이지만, 그 답들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 📣두 가지 조건 만족 탐욕스런 선택 조건(greedy choice property) 앞의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조 조건(optimal substructure) 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다. >이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못하지만, 어느 정도 최적

jyj7452

출처 - https://www.acmicpc.net/problem/11399

jyj7452

출처 - https://www.acmicpc.net/problem/11047 동전 n종류, 가격의 합 k 입력받기 n, k = map(int, input().split()) a = [] 필요한 동전 개수 coin = 0 n번 반복하며 입력 받은 동전의 가치를 a 리스트에 넣기 for i in range(n): a.append(int(input())) 내림차순 정렬(k를 나눌 수 있는 가장 큰 값부터 찾기위해) a.sort(reverse=True) a 리스트 반복 for i in a: coin += k//i # 동전 가격의 합을 입력받은 동전 가치로 나눈 몫 k = k%i # 동전 가격의 합을 동전 가치로 나눈 나머지를 갱

comdongsam

문제 링크 문제 풀이 아이디어 Greedy! 제가 생각하는 이번 문제의 핵심은 “각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.”라는 표현입니다. 문제에서도 볼드 처리가 되어 있는데요. 이 말은 즉 “같은 집에 1번 이상 방문해서 배달 혹은 픽업을 할 수 있다”는 뜻입니다. 따라서 극단적으로 말하면 일직선에 위치한 집들에 가면서는 “배달만”하고 오면서는 “픽업만” 할 수 있다는 뜻입니다. 즉 트럭에 배달할 짐을 가득 채워가도 돌아올 때 가득 채워서 픽업을 해올 수 있다는 점입니다. 즉 그리디 알고리즘을 사용할 때 “중간에 픽업할 자리가 부족하지 않을까?”라는 걱정을 하지 않아도 된다는 점입니다. 따라서 가장 먼 집부터 배달합니다. 가장 먼 집을 2번 이상 방문하는 것은 비효율적이기 때문입니다. 가장 먼

whitehousechef

https://www.acmicpc.net/problem/11399 initial very simple, we just sort the list and add the values together my correct code: another solution I searched google and some peeps did like this complexity O(n) time and space complexity

skins0329

Solution Explanation > 문제의 요구사항을 간추려보면 nums배열에서 가장 큰 요소에 1를 0번부터 k-1번까지 더한 수들의 총합을 구하는 것이다. 즉, max + (max + 1) + (max + 2) + ... + (max + k-1)을 뜻한다. 위 식을 for문을 이용해 구현하면 해결가능하다.

seungjae

문제 이해 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다. 문제 접근 회의를 최대한으로 많이 하려면 어떻게

whitehousechef

https://www.acmicpc.net/problem/1931 initial This is very similar to min. arrows to burst balloons in Leetcode. We want to get the meetings that end the earliest and prioritise them. To find the largest number of meetings using the given start and end times, you need to sort them in order of the meetings that end the fastest. The reason is simple. The sooner it ends, the more meetings there are to consider later. This is because if you prioritize sorting in order of starting early, it may

whitehousechef

https://www.acmicpc.net/problem/2217 initial Well it is simple. If we want to pull as much weight, we want to iterate through every rope and since it is guaranteed that the longer (bigger value ropes) can withstand as much as the short rope, we can do like this correct: complexity Time Complexity: Input Reading: Reading the input values and populating the list lst takes O(n) time, where "n" is the number of elements in the list. Sorting: Sorting the list lst using `lst

y00913

15903번: 카드 합체 놀이 그리디 알고리즘을 이용한 문제이다. 가장 작은 점수를 출력하기 위해서는 카드 합체를 진행할 때 작은 값끼리 진행해야 한다. 그래서 오름차순으로 정렬해주는 우선순위 큐를 사용하였고 이를 내림차순으로 바꾸어 저장해주기 위해 을 곱해 저장하였다. 반복문을 돌면서 을 구해 이를 더한 후 다시 우선순위 큐에 넣어주며 작은 값끼리의 카드 합체를 진행하였다. 그 후 큐에 있는 모든 값들을 저장해 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.

whitehousechef

https://www.acmicpc.net/problem/1026 Initial Right away I thought of sorting both lists. We need the smallest number of A to be multiplied with the biggest number of B to result in the smallest answer possible (or vice versa. But they said list B should not be sorted. So is there a way NOT to sort B but somehow get the biggest number of B? Yes! max()! Then how do we iterate through elements in B with just max()? We don't want to keep getting the max value so we also use remove() method

jasmine0714

문제 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자. 입력 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생

skins0329

Solution Explanation > 이 문제의 유형은 엄밀히 말하면 Greedy Algorithm에 관한 문제이다. 왜냐하면 단 하나의 숫자만 바꿀때 최댓값을 얻어야 하는데 그러기 위해서는 가장 높은 자리의 숫자를 바꿔야한다. 즉, 가장 높은 자리의 숫자를 바꾸는 것(6을 9로)이 최적의 해답이 되는 것이다. 그래서 각 자릿수를 순회하기 위해 배열로 전환한 후 6일 경우 9로 바꾸고 바로 리턴해주면 된다. Other > replace 메소드를 사용하면 아주 간단하게 6을 9로 바꿀 수 있다.

skins0329

Solution Explanation > 문제의 조건을 간단히 줄여보면 R의 개수와 L의 개수가 같아야 스플릿이 가능하다는 것이다. 예를 들어 앞의 R의 개수가 5개면 뒤의 L의 개수가 5개가 있어야 스플릿이 가능하다. R과 L의 순서를 거꾸로해도 마찬가지이다. 이 규칙을 활용하기 위해서는 R이나 L의 개수를 기억해야한다. 그래서 기억을 위해 변수 하나를 선언하고 R이 나타나면 +1를 하고 L이 나타나면 -1를 하기로했다. 변수가 0이 될 경우, R과 L의 개수가 같다는 것이므로 count 변수에 1을 추가해준다.

ssook1222

📍 문제 당신과 친구는 n개의 문제로 이루어진 참/거짓(T/F) 문제 시험을 봤습니다. 여러분은 본인이 제출한 답안과 친구의 답안을 알고 있으며, 친구가 그 답안 중에서 k개의 문제를 정확하게 맞췄다는 것을 알고 있습니다. 그렇다면, 당신은 몇 개의 문제를 맞췄을까요? 당신이 정확하게 맞춘 최대 문제 수를 계산하세요. (여러 경우가 있겠지만, 가장 많이 맞춘 경우의 수를 구하면 됩니다.) 입력 입력의 첫 줄에는 데이터셋의 수를 나타내는 정수 $m$이 포함됩니다. 각 데이터셋은 정확하게 $k$를 나타내는 정수로 시작합니다. 데이터셋의 두 번째 줄에는 당신이 작성한 $n$ (1 ≤ $n$ ≤ 1000)개의 문자로 이루어진 답안이 포함됩니다. 각 문자는 'T' 또는 'F'