Algorithm ) Greedy

코딩테스트에서 가장 출제 빈도가 높은 문제는 그리디, 구현,  DFS/BFS 를 활용한 탐색 문제라고 한다! 

순서대로 포스팅 할 예정이고, 오늘은 기초 그리디 문제에 대해 다뤄보고자 한다 

 

 

 

🛁 그리디 알고리즘 : 탐욕법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법 

- 일반적으로 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 

- 정당성 분석이 중요 : 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음 

- 하지만, 코딩테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됨

 

 

 

💵대표적인 그리디 알고리즘 문제 ! 거스름돈 

500원, 100원, 50원, 10원짜리 동전이 무한히 존재

-> 손님에게 거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수 ?

(단, 거슬러 줘야 할 돈 N은 항상 10의 배수)

 

 

⚡️문제 해결 아이디어 

- 최적의 해를 가장 빠르게 구하기 위해서 가장 큰 화폐단위 부터 돈을 거슬러 주는 것

- N원을 거슬러 줄 때, 500원으로 거슬러 줄 수 있을 만큼 거슬러 주고, 그 다음 100 50 10 원짜리 동전을 차례대로 거슬러 주기

 

n = 1260
count = 0

# 큰 단위의 화폐부터 차례로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전 세기
    n %= coin

print(count)

 

🥦 정당성 분석 

- 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음

- 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 더올리고 이것이 정당한지 검토할 수 있어야 답을 도출 할 수 있음 

 

🌈 시간 복잡도 분석

- 화폐의 종류가 K 라고 할 때, 소스코드의 시간 복잡도는 O(K)

- 알고리즘의 시간 복잡도는 거슬러줘야하는 금액과는 무관, 화폐의 종류만큼 반복하면 문제해결 

 

 

 

어떤 코딩테스트 문제를 만났을 때 , 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자. 오랜 시간을 고민해도 그리디 알고리즘으로 해결방법을 찾을 수 없다면, 이후에 다루게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민 ! 

 

실제로 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우에는 그리디 알고리즘으로 해결 할 수 없다. 화폐의 단위가 무작위로 주어진 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 

 

 

실전 문제 풀이

 

1️⃣문제 1 : 큰 수의 법칙 

- 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M 번 더하여 가장 큰 수를 만드는 법칙이다

- 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징이다

- 예를 들어 순서대로 2,4,5,4,6 으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정해보자. 

이 경우 특정한 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로 6+6+6+5+6+6+6+5 인 46이 된다. 

- 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주. 두번째 인덱스의 4와 네번째 인덱스의 4는 다르다. 

 

 

📌 입력조건 

- 첫째 줄에 N, M, K 의 자연수가 주어지며, 공백으로 구분

- 둘째 줄에 N개의 자연수가 주어지며, 공백으로 구분. 단 각각의 자연수는 1 이상 10000이하의 수로 주어진다. 

- 입력으로 주어지는 K는 항상 M보다 작거나 같다 

 

📌 출력조건 

- 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

 

 

 

- 문제 해결 아이디어 : 가장 큰 수와 두번째로 큰 수 만 저장하고, 연속으로 최대 k번 더할 수 있으므로 가장 큰수를 k번 더하고 두 번째로 큰수를 1번만 더하는 것을 반복하자! 

# N,M,K 공백으로 구분하여 입력받기 , N개의 수를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort() # 입력받은 수를 정렬
first = data[n - 1] #가장 큰수
second = data[n - 2] #두번째로 큰수

result = 0

while True:
    for i in range(k): # 가장 큰 수를 k번 더하기
        if m == 0: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때 마다 1씩 빼기
    if m == 0:
        break
    result += second # 두번째로 큰 수를 한번만 더하기
    m -= 1 # 더할 때마다 1씩 빼기

print(result)

풀이 1 : 단순하게 푸는 예시 -> M의 수가 커진다면? 시간초과의 가능성이 있으므로, 더 효율적인 풀이 필요

# N,M,K 공백으로 구분하여 입력받기 , N개의 수를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort() # 입력받은 수를 정렬
first = data[n - 1] #가장 큰수
second = data[n - 2] #두번째로 큰수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k+1)) * k # m을 k+1 로 나눈 몫에 k 곱하기
count += m % (k + 1) # 나누어 떨어지지 않는 경우, 나머지 만큼 큰수가 더해진다 

result = 0
result += (count) * first # 가장 큰수 더하기 
result += (m - count) * second # 두번째로 큰수 더하기 

print(result)

풀이 2 : 반복되는 수열에 대해서 파악 -> 가장 큰 수와 두번째로 큰 수가 더해질 때에는 특정한 수열 형태로 일정하게 반복해서 더해지는 경향이 있음 -> 그 길이는 K + 1 

 

💥 M을  K + 1로 나눈 몫이 수열이 반복되는 횟수가 되고, 여기에 K 를 곱해주면 가장 큰 수가 등장하는 횟수가 된다 

만약에 나누어 떨어지지 않는 경우 나머지만큼 가장 큰 수가 더해지므로 이를 더해준다 ! 

결과적으로, 최종 결과 값에 이 횟수 만큼 가장 큰 수를 더해주고 남은 횟수만큼 두번째로 큰 수 를 더해준다 !

 

 

GitHub - Suyeon9911/Algorithm-Study: 알고리즘 공부 레포 🦋