[이코테] 그리디(Greedy) with Python

💡 그리디 알고리즘

• 탐욕법
• 현재 상황에서 가장 좋은 것만 고르는 방법
• 즉, 나중에 미칠 영향에 대해서는 고려하지 않음

 

🔑 코딩테스트 실전 사용법

• ‘사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형’이라는 특징
• 그리디 알고리즘 유형의 문제는 매우 다양해서 암기로 모두 커버 가능하지 않음
• → 많은 문제를 풀어보면서 훈련해야 함
• 그리디 알고리즘의 종류 중 하나인 다익스트라 알고리즘은 그리디 알고리즘이면서도 ‘암기’가 필요한 알고리즘
• 그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로, 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해줌
  • 보통 이러한 기준은 곧 정렬 기준이 되므로, 정렬 알고리즘과 짝을 이뤄 많이 출제됨
• 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 방법인지 검토해야 함
• 코딩테스트 문제에서 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘 의심하기

 

💻 실전 예제

3-1 거스름돈.py

 

solution1

• 문제를 보고 직관적으로 떠오르는 풀이

N = int(input())
change_count = 0
change_count += N // 500
N = N % 500
change_count += N // 100
N = N % 100
change_count += N // 10
print(change_count)

 

solution2

• solution 1에서 반복되는 연산들을 코드로 정리

N = int(input())
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n//coin
    n %= coin

print(count)

• 화폐의 종류만큼 반복문 수행
• 화폐의 종류의 개수 K개에 대해 코드의 시간 복잡도는 O(K)

 

3-2 큰수의법칙.py

 

solution1

n, m, k = map(int, input().split())
li = list(map(int, input().split()))

# 가장 큰 숫자 두 개만 필요
li.sort(reverse=True)
num1 = li[0]
num2 = li[1]

# 반복문
answer = 0
while True:
    for i in range(k):
        if m == 0:
            break
        answer += num1
        m -= 1
    if m == 0:
        break
    answer += num2
    m -= 1

print(answer)

 

solution2

• 예시를 생각해보면서 반복되는 수열의 특징을 파악해냄
• 예시를 직접 들어보면서 관찰하는 태도가 중요!!

n, m, k = map(int, input().split())
li = list(map(int, input().split()))

# 가장 큰 숫자 두 개만 필요
li.sort(reverse=True)
num1 = li[0]
num2 = li[1]

answer = 0
if m == k:
    answer += k * num1
else:
    answer += m//(k+1) * (num1 * k + num2)
    m %= k+1
    if m > 0:
        answer += m%(k+1) * num1

print(answer)

 

solution3

n, m, k = map(int, input().split())
li = list(map(int, input().split()))

# 가장 큰 숫자 두 개만 필요
li.sort(reverse=True)
num1 = li[0]
num2 = li[1]

# 가장 큰 수가 더해지는 횟수
count = (m // (k + 1)) * k
count += m % (k + 1)

answer = 0
answer += count * num1
answer += (m - count) * num2

print(answer)

 

3-3 숫자카드게임.py

 

solution1

• min() , max() 함수 이용

n, m = map(int, input().split())
total_list = []
for i in range(n):
    num_list = list(map(int, input().split()))
    total_list.append(num_list)

min_list = []

for i in range(n):
    min_row = min(total_list[i])
    min_list.append(min_row)

answer = max(min_list)
print(answer)

 

3-4 1이될때까지.py

 

solution1

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

count = 0
while True:
    if n % k == 0: # 나누어 떨어지면
        n = n//k
        count += 1
    else:
        n -= 1
        count += 1
    if n == 1:
        break

print(count)

 

 

🔗 깃허브에도 정리해두었습니다