[Pyhton/코테] 그리디(Greedy) 알고리즘

그리디 알고리즘

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

ex) 루트부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶다.

A. 매 상황에서 가장 큰 값 고르기

가장 큰 값을 얻는 경로 (왼), 그리디 알고리즘 적용한 경로 (오)

위의 경우에서도 확인할 수 있듯이 일반적으로 그리디는 최적의 해를 보장할 수 없을 때가 많다. 그러나 코딩테스트에서 출제되는 '그리디 유형'의 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 것이고 이를 알아내는 문제인 것이다.

 

즉 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 그래서 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 다음 두 조건을 만족한다.

1. greedy choice property: 현재 선택이 이후의 선택에 영향을 주지 않음
2. optimal substructure: 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 함

* 출처: 

Greedy Algorithm(그리디 알고리즘) 개념, 추천 문제

그리디와 DP의 차이는 다음과 같다.

• DP: 가능한 모든 방법을 고려한다. 기존의 연산이 재사용되어 연산량을 줄일 수 있다.
• Greedy: 지금 당장의 최적해가 결국 최종적인 최적해로 이어지게 한다. 전체적인 상황 고려보다 매순간 최적해(가장 빠른/느린/..)를 선택한다. 그래서 전역 최적해를 보장하기 쉽지 않다.

* 출처:

[알고리즘] 그리디 vs DP

---

1. 거스름돈 문제

* 문제: 화폐 단위는 큰 단위가 항상 작은 단위의 배수가 되기 때문이다. 만약 거스름돈이 800원이고 동전이 500원, 400원, 100원이라면 500원짜리를 최대한 많이 주는 것이 아니라 400원짜리 2개를 주는 것이 최적의 해가 된다.

n = 1260
count = 0

array = [500, 100, 50, 10]
for coin in array:
  count += n // coin
  n %= coin

print(count)

- 시간 복잡도 분석: 화폐의 종류가 k라고 할 때, 소스코드의 시간복잡도는 O(k)이다.

 

2. 1이 될 때까지

* Solution: 최대한 나누기를 선택한다. N의 값을 줄일 때 1 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있기 때문.

* 정당성 분석: 최대한 많이 나누는 것이 최적의 해를 보장하는가?

• k>=2 이면, k로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.

n,k = map(int, input().split())

count = 0  

while True:
    target = (n//k) *k		# N이 K로 나뉘지 않아도, 가장 가까운 수를 찾을 수 있음
    count += (n-target)     # 1을 빼는 연산 횟수
    n = target
    # n < k 이면 더 이상 나눌 수 없음
    if n < k :
        break
    count += 1
    n //= k
# 남은 수에 대해 1씩 빼는 연산을 몇 번 할 것인지
count += (n-1)
print(count)

N이 매우 커도 반복문을 한 번 통과할 때마다 N이 빠르게 줄어들기 때문에, 시간 복잡도가 log일 수 있는 반복문.

 

* 나다어

• 반복문 대신 숫자 연산으로 얻을 수 없을지 생각해보기
• 몫 연산자는 //
• 두 개 이상 숫자 입력 받기 n,k = map(int, input().split())

3. 곱하기 혹은 더하기

기본 int형을 사용하면 약 21억까지의 수를 만들 수 있다.

* Solution: 대부분의 경우 곱하기가 값을 크게 만든다. 그러나 두 수 중 하나라도 0 혹은 1 인경우 더하기가 효율적이다.

input = input()

result = int(input[0])

for i in range(1, len(input)):
    num = int(input[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)

* 나다어

• 경우의 수가 너무 다양하면 반대로 생각해본다. → 두 수를 곱하는 경우 무조건 더하기보다 클테니, 그게 아닌 경우들(0, 1일 때)만 고려
• 값 입력은 input()
• int(문자열) 하면 숫자로 형변환
• 문자열 길이 구하기: len(문자열)

3. 모험가 길드

* Solution: 오름차순 정렬 후 공포도가 낮은 모험가부터 확인한다. 내림차순으로 정렬했을 때보다 작은 단위부터 그룹을 결성하여 많은 수의 그룹을 만들 수 있다. 꼭 모든 사람이 그룹에 속해서 모험을 떠나야 하는 것은 아니다.

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0
count = 0

for i in data:
    count += 1  # 이번 반복 회차의 data요소를 현재 길드 그룹에 포함시킴
    if count >= i:  # 길드 그룹원 수가 이번 회차의 data요소보다 클 때 -> 모집 끝
        result += 1
        count = 0   # 현재 길드 그룹 초기화

print(result)

* 나다어

• 꼭 주어진 리스트를 건드려야(삭제, 추가..)하는지, count만 하면 되는지 생각해본다. -> 수행 시간과 연관될 듯
  = 주어진 요소 자체를 써야(연산에..) 하는지, count만 하면 되는지
• 리스트 오름차순(작은 수부터) 정렬은 list.sort()
  내림차순 정렬은 list.sort(reverse=True)

---

본 포스팅은 하단의 책과 유튜브 강의를 참고하여 정리한 포스팅입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

https://youtu.be/2zjoKjt97vQ