[프로그래머스]Lv2.구명보트

본 페이지는 C++ 독학을 위해 작성한 포스트입니다 풀이과정도 포함되어있지만 문법공부에 대한 비중이 있습니다.
(+  Java언어 내용도 포함되어있을 수 있습니다. )

 

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

1.문제설명

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

제한사항
무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

점점 문제가 길어진다

2. 문제해결 접근

• 두명의 인원을 태우고자 (체중의 합)할 때, 가장 많은 수를 구하기 위해서는 평균값을 구해야 한다.
• sort정렬을 이용해, 가장 작은 수와 가장 큰 값의 합이 연산되도록 로직을 구성한다.
• 반복문으로 인수로 주어진 인원의 모두가 계산될 수 있도록한다
• 조건문으로 최저체중+최고체중은 보트 무게제한보다 작아야한다.
• 무게제한보다 큰 경우가 생길 수 있으므로, 이럴때 최고무게인원만 바뀌는 로직을 구현한다.

 

3. C++ 답안

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    // 최저 중량 인원을 지정하기 위한 변수
    int head = 0;
    // 최고 중량 인원을 지정하기 위한 변수
    int tail = people.size()-1;
        
    // 사람 몸무게 오름차순 정렬
    sort(people.begin(), people.end());
    
    // 오름차순 정렬 확인
    // for (int j = 0; j < people.size(); j++)
    //     {
    //         cout<< people[j];
    //     }
    while( tail >=head )
    {
        // people 최저무게와 최고무게의 합이
        // 무게제한보다 작을때만
        if( people[head] + people[tail] <= limit ){
            head++;
            tail--;
        }else{  // 최저중량 사람과 최고중량 사람의 합이 limit보다 클때
            tail--;
        }
        //조건에 만족하므로, 구명보트의 카운트가 올라간다
        answer++;
    }
    
    
    
    return answer;
}

 조건문이 해당하지 않았을 때 , 조건을 변경하는 방법이 다소 생소했기에 고민의 시간이 길었으며 이에 대한 생각을 할 수 있었던 좋은 문제였던 것 같다.

---

 

4. 관련 문법, 자료 구조 

탐욕법(Greedy)

탐욕법 알고리즘의 개념은 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다.

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로,여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답겁사 : 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택절차로 돌아가 위의 과정을 반복한다

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용할 수 있다.

 

 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬