[파이썬] 알고리즘 패러다임 : 그리디 알고리즘 Greedy Algorithm

2023.03.01 코드잇 학습내용

 

🔎 그리디 알고리즘(Greedy Algorithm)

greedy는 탐욕이라는 뜻.

그리디 알고리즘(Greedy Algorithm)은 미래를 내다보지 않고, 당장 눈앞에 보이는 최적의 선택을 하는 방식

그리디 알고리즘은 간단하고 빠르다는 장점이 있으나 순간마다 최적의 선택을 하는 경우 그 순간에 대해서는 최적이지만, 최종적인 답을 만들었을 때에는 그 답이 최적이 아닐 수 있음. 즉, 최적의 답이 보장되지 않는다는 단점이 있음.  

 

📖 그리디 알고리즘을 사용하는 경우

1. 문제를 해결하는 다른 알고리즘이 너무 느려서 사용할 수 없는 수준일 때

2. 애초부터 최적의 답이 필요 없을 때 사용

3. 순간의 최적의 선택이 최종 답에서도 최적의 선택이 되는 경우

 

3번과 같이 그리디 알고리즘이 최적의 답을 구해주는 경우의 조건 2가지

1. 최적 부분 구조(optimal substructure)를 갖추고 있다. → 이는 그리디 알고리즘을 사용하려 할 때의 필수조건

최적 부분 구조를 가지고 있다는 것은 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것

2. 탐욕적 선택 속성 (greedy choice property) → 이는 필수조건은 아니지만 최적의 답을 구하기 위해서는 만족해야 함

각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택인 경우

 

📖 그리디 알고리즘 연습문제

⚙ 최소 개수의 동전으로 돈 거슬러 주기

▼▼▼ 모범 답안 ▼▼▼

 

 

▼▼▼ 내가 작성한 코드 ▼▼▼

차이점 : sorted 대신 sort를 사용하였고, value값을 직접 계산

개선점 : for 문에 sorted(coin_list, reverse=True)를 넣으면 코드 한 줄이 줄어들고, value는 value에서 coin을 나눈 나머지로 %=로 쉽게 작성 가능

 

 

⚙ 한 사람당 카드 하나씩 뽑아서 모두 곱했을 때 가능한 최대곱 구하기

▼▼▼ 모범 답안 ▼▼▼

 

 

▼▼▼ 내가 작성한 코드 ▼▼▼

개선할점 : 코드를 더 보기 좋고 간단하게 줄일 수 있으면 줄이기. max_element는 굳이 필요한 변수가 아님. 바로 대입하여 작성하는 게 더 보기 좋음

 

 

⚙ 가장 적게 내는 경우의 벌금 구하기

▼▼▼ 모범 답안 ▼▼▼

정렬된 리스트를 새롭게 정의한 후 인덱스 순서대로 반복문 진행

 

 

▼▼▼ 내가 작성한 코드 ▼▼▼

차이점 : for 반복문을 인덱스가 아닌 요소로 진행. 대신 i를 변수로 지정하였고, 반복문에서 i += 1이 실행될 수 있게 작성하였음

 

⚙ 가장 많은 수업 담기

▼▼▼ 모범 답안 ▼▼▼

 

① course_list를 튜플의 1번 인덱스를 기준으로 오름차순 정렬

정렬 조건 지정하기
파이썬에서는 sort()와 sorted()를 사용하여 정렬을 할 수 있는데, 인자로 key=lambda x : x[0] 등을 주어 정렬 조건을 지정할 수 있음. 아래의 코드에서 sorted(list, key = lambda x : x[1]는 튜플의 1번 인덱스를 기준으로 정렬한다는 뜻
또한, x : (x[1], x[0]) 이런 식으로 작성하면 우선조건과 차선조건을 지정할 수 있음. 앞에 있는 게 우선조건

 

② 결괏값을 리턴하고자 하는 새로운 리스트를 생성하고 리스트에는 끝나는 시간이 가장 작은 튜플을 넣어 놓음

③ 새로 정렬된 리스트의 각 튜플 요소별로 아래의 조건 확인

 

 

▼▼▼ 내가 작성한 코드 ▼▼▼

차이점 : 모범답안에서는 for반복문을 인덱스 번호가 아닌 요소로 지정하여 사용하였음. 요소를 사용할 경우 더 깔끔한 코드 작성 가능. 또한, 조건식도 더 간단하게 작성할 수 있음.