Greedy 검색 결과

해당 글 3건

[프로그래머스](Greedy) 구명보트 (C++)

구명보트(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 접근법 문제에서 요구한 구명보트 개수의 최솟값을 구하기 위해서는 제한 무게를 넘지 않는다면, 가장 무거운 사람이 가장 가벼운 사람과 탑승해야 한다. 다음과 같은 상황을 생각해보자 보트의 무게 제한: 150kg 사람들의 무게: 100kg 80gk 60kg 50kg 가장 무거운 사람인 100kg인 사람이 가장 가벼운 50kg과 같이 탑승해야 보트를 가장 효율적으로 사용할 수 있다. 만약 80k..
Algorithms/Greedy 2021. 7. 16. 10:01

[프로그래머스] (Greedy) 큰 수 만들기 (C++)

큰 수 만들기(Level2) 문제 전체 문제 보기 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 접근법 그리디란 부분적인 최적의 해가 전체적인 최적의 해가 되는 알고리즘을 말한다. 그래서 먼저 부분적인 최적의 해를 정의해 보고, 부분적인 최적의 해가 전체적인 최적의 해가 될 수 있다면 그리디로 풀 수 있다. 그래서 이문제를 풀기 위해 먼저 부분적인 최적의 해를 정해보자. 이 문제에서 구해야 하는 값은 number 라는 수에서 k개의 숫자를 제거했을 때 가장 큰 수이다. 큰 수를 만들기 위해서는 앞에 있는 숫자를 가장 크게 만들어 주면 된다. 앞에 있는 숫자를 가장 크게 만들기 위해서 우리는 어떤 수를 삭제해야 할지 기준을 마련해야 한다. 이 기준이 부분적인 최적의 해가 될 것이다. 문..
Algorithms/Greedy 2021. 7. 15. 09:07

[프로그래머스](Greedy) 체육복 (C++)

체육복(Level1) 문제 전체문제 보기 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 접근법 이 문제는 Level1 문제 답게 복잡하게 생각한다거나, 특별한 반례를 고민해야하는 문제는 아니다. 아래와 같이 간단하게 해결 할 수 있다. 실제 코딩테스트에서 이런 문제가 나온다면 빠른 시간에 풀수 있어야 하기 때문에 빠르게 문제를 해석하고 구현하는 연습을 하자. 모든 학생들에 대한 벡터를 만들고 체육복에 대한 정보를 입력한다. 모든 학생에 대해서 조회를한다. 만약 체육복을 2벌 가지고 있는 학생이 있다면, 앞에 ..
Algorithms/Greedy 2021. 7. 15. 05:30