[Algo] Greedy Algorithm(그리디 알고리즘)

냥냥냥

📌 1. Greedy Algorithm ? 그리디 알고리즘?

 

“A greedy algorithm is an algorithm that shortcuts a full analysis in order to choose quickly an option that appears to work in the situation immediately at hand. They are often used by humans.”
- Kim Stanley Robinson

Greedy 알고리즘, a.k.a 탐욕 알고리즘

이렇게 되면 망함

그리디 알고리즘은 다소 단순하게 미래를 내다보지 않고 당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 목표를 달성하기 위해 매 순간 탐욕적인 선택을 한다. 순간순간 유리한 선택을 하면 되니까 간단하고 빠르다는 장점이 있지만 최적의 답이 보장되지 않는다 → 치명적인 단점이다 (위에 mim처럼 되면 폭망함)

 

📌 2. 언제 Greedy Algorithm을 사용할까?

그럼에도 그리디 알고리즘을 사용하는 경우가 있다. 

1. 문제를 해결하는 다른 알고리즘이 너무 느린 경우 대안으로 사용
2. 최적의 답이 필요없을 때
3. 그런데 Greedy Algorithm이 최적의 답을 보장해주는 경우도 있다
   • 최적 부분 구조 : 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것
   • 탐욕적 선택 속성 : 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택인 경우 
   • 위의 두 속성을 모두 갖췄다면 Greedy Algorithm을 사용해 최적의 답을 찾을 수 있다!

 

📌 3. Greedy Algorithm 활용하기

1) 최대 곱 구하기

가장 쉽고 간단하게 탐욕 알고리즘을 활용해 볼 수 있는 문제

여러 개의 정수를 담은 리스트에서 각 하나씩의 정수를 골라 곱한 결과 중 최대값 구하기

Brute Force 방식으로 모든 경우의 수를 시도해 볼 수도 있지만 느리고 비효율적이다. (시간 초과 나기 딱 좋음)

간단하게 각 리스트에서 가장 큰 값만 선택하면 된다.

# Greedy Algorithm
def max_value(lists):
	# 곱셈 결과를 저장하는 변수
    answer = 1
    
    # 반복문을 통해 리스트를 한 번씩만 순회
    for one_list in list:
    	# 각 리스트의 최대값 곱하기
        answer *= max(one_list)
    
   	return answer

2) 수강 신청

복수의 강의 시간표가 리스트 안에 튜플로 제공될 때 가장 많은 수업을 들을 수 있는 시간표 만들기 

최대한 많은 수업을 들으려고 할 때 생각해 볼 수 있는 몇 가지 선택지가 있다.

 

1. 가장 먼저 시작하는 수업 고르기 → 새벽부터 시작해서 밤에 마치면 다른 모든 수업들을 못 듣게 됨 
2. 겹치는 수업이 가장 적은 수업 고르기 → 테케에 전체적으로 수업이 많이 겹칠 때 겹치는 수업 갯수 자체는 적지만 시간을 많이 차지하면 또 최적의 답이 안 나올 수 있음
3. 가장 짧은 수업 고르기 → 짧긴 해도 겹치는 수업이 와르르라서 다 못듣게 될 수 있음
4. 가장 먼저 끝나는 수업 고르기 → 딱히 반례가 없으므로 이 방법 채택

def select_course(course_list):

    # 수업을 끝나는 순서로 정렬한다
    course_list = sorted(course_list, key=lambda x: x[1])
    # 현재 시간에 대한 변수
    now = course_list[0][1]
    # 가장 먼저 끝나는 수업은 무조건 듣는다
    answer = [course_list[0]]
    
    # 이미 선택한 수업과 안 겹치는 수업 중 가장 빨리 끝나는 수업을 고른다
    for i in range(1, len(course_list)):
        # 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다
        # 그래서 안 겹치는 경우에만 시간표에 넣어준다
        if course_list[i][0] > now:
            answer.append(course_list[i])
            now = course_list[i][1]
        else:
            continue
    
    return answer