그리디 알고리즘

그리디 알고리즘 = 현재 상태에서 선택가능한 수 중 최선의 선택지를 고르다 보면 전체 선택지 중 최선의 선택지가 될 것이다.
= 매 순간 다음 선택지의 최선의 선택만을 고른다.

쉬운 이해

6430원을 쪼갠다고 생각.
5000 - 1개
1000 - 1개
500 - 0개
100 - 4개
10 - 3개

이 알고리즘은 문제점이 존재한다. 순간순간의 최선책이 전체 상황에서의 최선을 보장하지 못한다는 것이다.

핵심 이론

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나는것은 아닌지 검토한다.
3. 해 검사 : 선택한 해 집합이 문제를 해결할 수 있는 선택인지 검사한다.
   !전체 문제를 해결하지 못한다 -> 1로 돌아간다.

사용가능 검토방법

1. 현재의 선택이 미래에 영향을 미치는가? 를 고려한다.
   
   ex) 서울에서 부산까지 이동을 한다고 했을 때 서울에서 대전까지 가는 방법은 대전에서 부산까지 가는 방법에 영향을 미치지 않는다.

2. 부분의 최적 해가 모이면 전체의 최적 해가 되야한다.

3. 정렬을 잘 해야한다가 핵심!

사용 이유

빠르다!

문제풀이

1. 체육복

   풀이 과정

   1. 먼저 잃어버린 사람이 여유분을 가지고 있는지 체크해 잃어버린 사람 배열에서 제거한다.
   2. 여분이 있는 사람의 앖 뒤 사람이 잃어버린 경우 빌려주며 잃어버린 사람 배열에서 제거한다.
   3. 최대 인원에서 잃어버린 사람 배열의 남아있는 수를 빼줘서 리턴

def solution(n, lost, reserve):
    answer = n
    reservecopy = reserve.copy() # 복사본 생성
    lostcopy = lost.copy()    # 복사본 생성
    for value in reservecopy:  # 잃어버린 사람이 여분을 가지고있는 경우 
        if value in lostcopy:
                lost.remove(value)
                reserve.remove(value)
                print(lost)
    lost.sort()
    reserve.sort()
    for value in reserve:  # 여분을 가지고있는 사람이 잃어버린사람을 빌려줄 수 있는 경우 
        min = value -1
        max = value +1
        for n in lost:
            if(n == min):  # 여분 소유자의 앞 사람 체크 
                lost.remove(min)  # 빌려줄 수 있으면 잃어버린 사람 리스트에서 제거 
            elif(n == max):  # 여분 소유자의 뒷 사람 체크 
                lost.remove(max)  # 빌려줄 수 있으면 잃어버린 사람 리스트에서 제거 
    return answer -len(lost) 

트러블 슈팅

   for value in reserve:  
       if value in lost:
               lost.remove(value)
               reserve.remove(value)
               print(lost)

문제상황: 배열의 중간중간 작동을 안하고 넘어가는 경우가 발생
원인 : 리스트를 순회하는 도중에 수정을 하기때문에 문제가 발생했다.
해결 : 복사본을 생성해 순회를 하고 제거는 원본을 제거하는 방식으로 해결

2. 구명보트

   풀이 과정

   1. 정렬
   2. 가장 무거운 사람과 가벼운 사람을 같이 태울수 있는지 확인

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    people = deque(people)   # 오름차순 정렬 후 Que 
    while len(people)>0:    #남은 사람이 없을때 까지 
        if len(people) == 1:
            answer += 1
            people.pop()    # 남은게 1명이라면 바로 pop
        else:
            wsum = people[0] + people[-1]   # 무거운 사람과 가벼운 사람의 무게합이 리미트 보다 크다면 무거운 사람만 먼저 
            if wsum > limit:
                answer += 1
                people.pop()
            else:             
                people.pop()            # 2 사람의 무게합이 리미트 보다 작으면 양쪽 다 pop
                people.popleft()
                answer += 1
    return answer

3. 큰 수 만들기

def solution(number, k):
    answer = ''
    num_list = [int(x) for x in list(number)]         # 숫자 나누기 
    listt = []                         
    num_length = len(number) - k           
    for i in range(len(number)):
        while k > 0 and listt and listt[-1] < num_list[i]: #새로운 값이 더 크면 pop,listt 안 비었고
            listt.pop()
            k -= 1
        if k == 0: 
            listt += num_list[i:]             # 남은 값들 이어주기
            break                             
        listt.append(num_list[i])             # 숫자 추가
    if len(listt) > num_length:               #숫자를 담은 리스트가 정답길이보다 길면 슬라이싱
        listt = listt[:num_length]
    answer = ''.join(map(str,listt))          #리스트들 join함수로 합쳐줌
    return answer