[99클럽 코테 스터디 17일차 TIL] 프로그래머스 | Greedy 구명보트

17일차 - Greedy

Problem

프로그래머스

 

Sol

limit가 있는 보트에 최대 2명까지 태울때, 주어진 people을 모두 태우기 위해 필요한 최소한의 보트 수를 구하는 문제

 

Greedy Algorithm 

 

전역적 최적해를 찾기 위해 각 단계에서 최선의 지역적 선택을 하는 알고리즘

• 현재 상황에서 가장 최선의 선택을 반복적으로 하는 방식
• 각 단계에서의 가장 좋은 선택 ➡ 전체 문제의 최적 해
  1.  탐욕 선택 속성 Greedy Choice Property
     • 미래 결과를 고려하지 않고 현재 이용 가능한 정보를 기반으로 결정 == 항상 가장 최적이 아닐수도!
  2. 최적 부분 구조 Optimal Substructure
     • 경험적 접근 : 부분 문제를 해결하여 얻은 해가 전체 문제의 최적 해 보장
  3. 대표 예 : Fractional Knapsack Problem(배낭문제), Dijkstra, Kruskal, Coin Change Problem, Huffman Coding
• 장점
  • 간단하고 이해하기 쉬움 , 직관적
  • 빠른 실행시간
  • 최적의 솔루션을 찾기 어려운 경우에도 좋은 근사 솔루션 제공 가능
• 한계/단점
  • 항상 최상의 솔루션을 찾는 것은 아님
  • 순서가 결과에 큰 영향을 미칠 수 있음
  • 국소적 최적화에 중점을 두기 때문에 더 넓은 맥락을 고려해야함
  • Greedy(탐욕스러운)한 선택이 최적의 솔루션으로 이어지지 않는 문제에는 탐욕 알고리즘을 적용할 수 없음(모든 문제에 적용 불가)

 

🌱 참고

Greedy Algorithms - GeeksforGeeks

 

Greedy Algorithm Tutorial - Examples, Application and Practice Problem - GeeksforGeeks

 

 

해결 방법

👀 가장 무거운 사람과 가장 가벼운 사람을 짝지어 구명보트에 태우는 방식으로 접근하였습니다.

1. people의 몸무게 정렬 : 가벼운 몸무게부터 무거운 몸무게까지 오름차순으로 정렬합니다.

2. 양 끝에서 시작 : 가장 가벼운 사람을 가리키는 포인터는 'light', 가장 무거운 사람을 가리키는 포인터는 'heavy'입니다. 초기에 'light'는 0을, 'heavy'는 마지막 인덱스를 가리킵니다.

3. 최대한 많은 사람 태우기 : 'light'와 'heavy'를 더해서 limit을 넘지 않으면 함께 태우고 그렇지 않으면 무거운 사람만 태웁니다. 

4. 포인터 이동 : 두 사람을 모두 태웠다면 'light'와 'heavy'를 각각 +1, -1 해주고, 한 사람만 태웠다면 무거운 사람만 태우기로했기 때문에 'heavy'만 -1 해줍니다.

5. 보트 수 증가 : 보트 수를 증가시켜 필요한 최소 boat 수를 카운트합니다.

6. 반복  : 주어진 people을 모두 태울 때 까지 위의 과정을 반복합니다. 

 

시간복잡도 O(nlogn)

• 몸무게 배열 정렬 O(nlogn)
• 배열 순회 O(n)

---

✔ Answer

def solution(people, limit):
    # 1. 몸무게를 오름차순으로 정렬
    people.sort()
    light = 0
    heavy = len(people) - 1
    boats = 0
    
    # 2. 양 끝에서 시작하여 가장 가벼운 사람과 가장 무거운 사람 태워보기
    while light <= heavy:
        # 3. 최대한 많이 태우기
        
        # 가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있는 경우
        if people[light] + people[heavy] <= limit:
        # 4. 포인터 이동
            light += 1
            
        # 가장 무거운 사람을 태우는 경우
        heavy -= 1
        
        # 5. 보트 하나 사용
        boats += 1
    
    return boats

---

💬 욕심쟁이 알고리즘을 공부하다보니 동적프로그래밍이랑 같이 비교해서 상황에 맞는 알고리즘을 사용하는 것이 필요하다는 것을 알았습니다. 내일 문제를 보고 Greedy 와 DP 비교를 하는 글을 적어보겠습니다! 그리고 다른 분들의 풀이를 보면서 더 다양한 해결 방법을 생각해볼 수 있었습니다.