99클럽 코테 스터디 19일차 TIL + 그리디(Greedy)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "구명보트" 문제를 풀었다.
- 주제는 그리디(Greedy)이고, 내가 잘 못하는 알고뤼듬이다.

[나의 코드]

def solution(people, limit):
    answer = 0
    people.sort()
    
    start = 0
    end = len(people) - 1
    
    while start <= end:
        if people[start] + people[end] <= limit:
            start += 1
            end -= 1
        else:
            end -= 1
        answer += 1
        
    return answer

처음에는 아무 생각 없이 for문으로 풀었다. 정렬해서 가벼운 것부터 더해서 확인했다.
그런데 점점 이상함을 느꼈다. '안 되는데?'를 느낀 순간 바로 반례를 찾아보았다.

예를 들어 [40, 50, 50, 60]와 같은 배열을 생각해 보면, 작은 거부터 확인하면 답이 3이 나온다.
근데 답은 2가 나와야 한다. (40, 60), (50, 50) 이렇게 탈 수 있기 때문이다.

그래서 맨 앞과 맨 뒤를 비교해서 풀었다.
[40, 50, 50, 60, 70]이고 limit이 100이라면 이 배열에서 (40, 70)을 비교하면 limit을 넘어가버린다.
이 때는 뒤의 인덱스를 줄인다. 어차피 마지막 인간은 어떻게 해도 못 타니까.

그리고 (40, 60)을 비교하게 되는데, 반례처럼 가장 작은 것과 큰 것을 더해서 최적의 해를 만들 수 있도록 한다. (머리로는 이해가 가지만 말로는 설명이 안 되는 영역이다. 감각으로 익히시길.)
그래서 limit이 넘지 않는다면 둘을 빼기 위해 start와 end를 모두 줄여준다.

[오늘의 회고]
- 그리디는 현재 상황에서 가장 좋은 것만 고르는 것이지 최적의 해를 구한다는 보장은 없다.
- 바로 문제 유형을 떠올리지 못하면 그리디일 확률이 높다고 한다. 진짜 싫다.
- 당근한테 물 주러 가야지. 끝!