★그리디★탐욕법★구명보트[프로그래머스]

구명보트

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

프로그래머스

from collections import deque

def solution(people, limit):
    answer = 0
    
    people = deque(sorted(people , reverse = True))
#     # print(people)
#     # 50 50 70 80
#     # 1> 50 good --> 50 --> 100 --> break ==> answer+=1
#     # 2> 70 good --> 80 --> bad(people=[80]) ==> answer+=1
#     # 3> 80 good --> answer+=1
    
    while len(people)>1:

        if people[0]+people[-1]<=limit:
            print(people[0]+people[-1])
            people.popleft()
            people.pop()
            answer+=1
        else:
            people.popleft()
            answer+=1
    if people:
        answer+=1
        
    return answer

==> 맨 처음 정렬하고, 맨 끝과 처음꺼 비교해가며 찾아보기

 

==> [80,70,50,50] ==> 마지막엔 결국 [50,50] 만 남는다!!

 

 

탐욕법이란?

 

탐욕법(Greedy algorithm)은 최적해를 구하는데 사용되는 알고리즘 설계 기법 중 하나입니다. 탐욕법은 각 단계에서 가장 좋아보이는 선택을 하는 방식으로 동작합니다.

탐욕법은 매 순간 최적인 선택을 하는 것을 강조하는 접근 방식입니다. 각 단계에서 현재 상황에서 가장 좋은 선택을 하는 것을 반복하여 전체적인 최적해를 찾아냅니다. 이때 각 단계에서 선택한 결과는 이후에 되돌릴 수 없으며, 지역적인 최적해를 선택하므로 항상 전체적인 최적해가 되는 것은 아닙니다.

탐욕법은 다음과 같은 특징을 가지고 있습니다:

1. 탐욕 선택 속성(Greedy-choice property): 각 단계에서의 선택이 지역적으로 최적이어야 합니다.
2. 최적 부분 구조(Optimal substructure): 전체 문제의 최적해는 각 단계의 최적해로 구성되어야 합니다.

탐욕법은 다양한 문제에 적용될 수 있습니다. 예를 들어, 거스름돈 문제, 스케줄링 문제, 그리디 알고리즘을 사용하는 일부 그래프 알고리즘 등이 있습니다.

탐욕법은 간단하고 직관적인 접근 방식이며, 때로는 최적해에 근접한 해를 구하는데 유용합니다. 하지만 항상 최적해를 보장하지 않을 수 있으며, 각 단계에서의 선택이 전체적인 최적해로 이어지지 않는 경우가 있을 수 있습니다. 따라서 탐욕법을 적용할 때에는 문제의 특성을 분석하고, 탐욕법이 항상 최적해를 보장하는지 검토하는 것이 중요합니다.