[알고리즘] Greedy Algorithm (탐욕알고리즘, 백준 문제모음)

📌 탐욕적 알고리즘 Greedy Algorithm

탐욕적 알고리즘(Greedy Algorithm)은 동적 프로그래밍(Dynamic Programming) 얘기를 빼놓고서는 할 수 없다. 동적 프로그래밍은 나중에 또 하겠지만 간단히 설명하자면 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결방법을 결합해 최종 문제를 해결하는 방법이다. 즉, 동적프로그래밍은 사실상 문제를 해결하는 모든 방법을 탐색하므로 정확하지만 속도가 느릴 수 밖에 없다.

동적 프로그래밍의 느린 속도를 보완하고자 등장한 개념이 탐욕적 알고리즘이다. 탐욕적(Greedy), 말 그대로 현재 상황에서 당장 좋은 것만을 고르는 방법이다. 그 순간에 최적이라고 생각하는 결정을 한다. (미래를 전혀 고려하지 않음) 덕분에 그리디 알고리즘은 지역 최적해(local optima) 개념과 같이 쓰인다. 하지만 빠르게 결정할 수 있다는 장점이 있다.

 

어쨌거나 탐욕적 알고리즘과 동적프로그래밍(DP)은 반대되는 개념이지만 서로 보완하는 관계에 있다.

 

그리디 유형의 가장 대표적인 거스름돈 계산 문제를 생각해보자. 거슬러 줘야 할 동전의 최소 개수를 구하는 문제로, 가장 큰 화폐 단위부터 돈을 거슬러 준다는 아이디어가 핵심이다.

n = 1260
count = 0

# 큰 단위 화폐부터 차례대로
coin_types = [500, 100, 50, 10]

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

print(count)

시간복잡도는 화폐의 종류가 K개 일 때 K번만큼 반복해야 하므로 O(K)이다.

 

그리디 알고리즘이 모든 문제에 적용할 수 있는 건 아니므로 이 알고리즘의 정당성에 대해 고민해봐야 한다. 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다. 이런 경우에는 위에서 말했듯 동적프로그래밍(DP) 기법을 사용해야 한다.

 

[ 큰 수의 법칙 ]

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

가장 큰 수를 K번, 두번째로 큰 수를 1번 더하는 연산을 반복하면 되는 간단한 문제였다.

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

arr.sort()
first = arr[-1]
second = arr[-2]

answer = first * k * (m // k) + second * (m % k)
print(answer)

[ 숫자 카드 게임 ]

N * M 형태의 숫자 카드 들 중 행을 먼저 선택하고, 그 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다고 할 때, 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 해야한다. 즉, 각 행마다 가장 작은 수를 찾고 그 수들 중 가장 큰 수를 찾으면 된다.

n, m = map(int, input().split())
answer = 0
for _ in range(n):
    data = list(map(int, input().split()))
    answer = max(answer, min(data))
print(answer)

[ 1이 될 때까지 ]

어떤 수 N이 1이 될 때까지 다음의 두 연산 중 하나를 반복적으로 선택해 수행한다. (두번째 연산은 N이 K로 나누어 떨어질 때만)

1. N에서 1을 뺀다

2. N을 K로 나눈다

# sol1: N이 K의 배수가 될 때까지 반복해 1을 빼거나, K의 배수가 되면 K로 나누기
n, k = map(int, input().split())
count = 0
while n > 0:
    if n == 1:
        break
    if n % k:
        n -= 1
    else:
        n //= k
    count += 1
print(count)

# sol2: N이 K의 배수가 될 때까지의 수를 한번에 빼는 것 (반복문 실행횟수를 줄여줌)
n, k = map(int, input().split())
count = 0
while n > 0:
    if n == 1:
        break
    target = n % k
    count += target
    n -= target
    n //= k
    count += 1
print(count)

---

탐욕적 알고리즘은 활동선택문제(TSP), 분할 가능한 배낭 문제, 거스름돈 문제 등에서 쓰이는데 예시는 몇 번 봤었기 때문에 스킵하고 바로 백준 문제를 풀었다. 스터디에서 풀기로 한 백준 4문제를 풀고 구글링하다 찾은 백준 문제모음을 차근차근 풀어보려한다. 문제 푼 건 아래 링크로 첨부해두겠다. (파란 글씨 클릭하면 링크로 이동)

 

그리디 문제풀이 (1) : C++

• 11047번 : 동전 0
• 4796번 : 캠핑
• 13305번 : 주유소
• 16435번 : 스네이크버드

그리디 문제풀이 (2) : C++

• 11399번 : ATM
• 2217번 : 로프
• 13458번 : 시험감독

그리디 문제풀이 (3) : Python

이코테 챕터3 그리디 파트 예제+연습문제 풀이

• 만들 수 없는 금액 (K 대회 기출)
• 볼링공 고르기 (2019 SW 마에스트로 입학 테스트)
• 무지의 먹방 라이브 (2019 카카오 신입 공채)

 

---

 

🔗 나중에 다시 볼만한 링크모음

이 글은 '이것이 코딩 테스트다 with 파이썬(나동빈)' 책 내용과 수록 문제를 참고했습니다. (문제가 된다면 삭제하겠습니다!)

covenant.tistory.com/131

www.youtube.com/watch?v=2zjoKjt97vQ