greedy

그리디란?

각 단계에서 최적의 해를 선택하는 방식이다. 그러나 각 단계에 최적의 해가 전체의 최적의 해가 되지는 못한다. 그리디의 단점이다.

단적인 예시가 아래 슬라이딩 윈도우로 풀었던(
https://velog.io/@berry_hennie/sliding-window) 카드게임이다.

양쪽의 최대 숫자를 뽑는다고 해서 총합이 최대가 되지는 못한다.

[1,30,3,5,6,7] 카드가 이런 순서일 경우 각 단계에서 최대의 숫자를 뽑는다고 해서 총합이 최대가 되지 못하는 경우이다.

그리디의 예시

1. 버스를 최대로 태울 수 있는 무게 구하기

def solution(weight:list[int], limit:int):

    weight_list = sorted(weight)
    answer = []
    cnt = 0
    for _weight in weight_list:
        if cnt + _weight <=limit:
            answer.append(_weight)
            cnt+=_weight
    print(answer)
    return len(answer)

-> 보통 그리디는 정렬을 기반으로 한다. limit전까지 최소의 무게를 태워 최대를 태울 수 있도록 한다.

2. 선긋기 문제

한번의 선긋기 수직선상에 한점에서 다른점까지 선을 긋는 것이다. 선을 그을때는 이미 선이 있는 위치에서 겹쳐 그릴 수도 있다.
수직선은 0번부터 m번 지점까지 길이를 갖고 있다.
연속적인 선을 긋기 위해서 최소 횟수로 선을 그을 수 있는 방법을 구하시오

def solution(m: int, nums: list[list[int, int]]) -> int:
    sorted_nums = sorted(nums, key=lambda x:x[0])

    current_start = 0
    current_end = 0
    result = []
    while current_end < m:
        current_nums = [elm for elm in sorted_nums if elm[0]<=current_start]
        if not current_nums:
            break

        current_nums_sort = sorted(current_nums, key=lambda x:-x[1])
        result.append(current_nums_sort[0])
        current_start = current_nums_sort[0][1]
        current_end= current_nums_sort[0][1]


    return len(result)