그리디 알고리즘(탐욕법)

 

 

요즘 프로그래머스나 백준 같은 알고리즘을 풀어볼 수 있는 사이트에서 알고리즘 문제들을 하나씩 풀어보고 있다. 방학동안 한 스타트업에서 IT Admin 계약직으로 일하게 돼 업무가 바쁘지 않은 동안은 내 공부를 할 수 있었는데, 이 시간에 어떤 걸 공부하면 좋을까 생각하다 알고리즘 문제를 풀어보게 됐다. 맞은 문제는 다른 사람들의 코드를 보며 더 간결한, 빠르게 작동하는 방식도 있다는 점을 배웠고, 아무리 생각해도 어떤 방법으로 풀어야 할 지 모르겠는 문제들도 있었다... 물론 이런 경우 구글링하면 대부분 나오긴 했으나 이해가..안되는.. 경우도 있었다..ㅎㅎ 

 

알고리즘 문제에도 유형이 존재한다는 것을 알게 됐고, 유형별로 공부를 해야겠단 생각을 했다. 알고리즘 문제를 풀어보며 느낀 것은 어떤 방식으로 풀어야겠다는 건 알겠으나 막상 그 생각을 코드로 옮기는 게 쉽지 않다는 것이다. 순열과 조합 문제로 풀 수 있는 문제도 있었는데, 코드로 어떻게 나타내야 할 지 모르겠어서 포기했던 문제도 생각이 난다. 그래서 수학 문제처럼 유형별로 정리하고 외워야할 부분이 있다면 외우고, 코드로 나타낼 수 있어야 겠다는 생각을 하게 됐다.

 

마침 유튜브 '동빈나'님의 채널에서 코딩테스트에서 사용할 수 있는 유형별 알고리즘 풀이들을 설명하는 영상이 있어 정리하면서 공부하고자 한다.

당분간 정리될 문제 및 코드의 출처는 유튜브 동빈나님의 채널(https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw).

 

그리디 알고리즘

정의: 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지를 정당성 분석을 통해 검토한다. 상당수 그리디 문제는 탐욕법으로 얻은 해가 최적의 해라는 것을 추론할 수 있어야 풀리도록 출제된다. 다음은 그리디 알고리즘을 활용할 수 있는 대표적인 문제들

 

 

• <거스름 돈>
• 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때, 손님에게 거슬러 주어야 할 돈은 N원이며, 이 때 거슬러줘야 할 동전의 최소 개수를 구하는 프로그램을 작성하라. 단, N은 항상 10의 배수이다

위 문제에서 최적의 해를 빠르게 구하기 위해서는 가장 큰 단위부터 돈을 거슬러 주면 된다. 500원으로 거슬러 줄 수 있는 만큼 거슬러 주고 이후 100,50,10 단위의 동전으로 거슬러 주면 된다. 이 때 가장 큰 단위부터 돈을 거슬러 주는게 최적의 해를 보장하는 이유(정당성)는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를들어 동전 단위가 500,100,50,10이 아닌 500,400,100 인 상황에서 800원을 거슬러 줘야 한다면? 500원 1개, 100원 3개 보단 400원 2개를 거슬러 주는게 최소 개수의 동전을 사용한 경우가 된다. 문제 해결 과정을 코드로 나타내보면 이렇다.

n = 1260 # 거슬러줘야 할 금액
count = 0 # 동전의 개수 카운팅

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

for coin in array:
    count += n //coin # 해당 동전의 금액으로 거슬러 줄 수 있는 동전의 개수
    n %= coin # 위의 동전의 개수를 사용해 거슬러 주고 남은 금액
    
print(count) # 몇 개의 동전을 사용했는 지 확인

 

• <1이 될 때까지>
• 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
  • 1. N에서 1을 뺀다.
  • 2. N을 K로 나눈다.
• 예를 들어 N이 17, K가 4인 경우, 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 되고 이는 N을 1로 만드는 최소 횟수이다.
• N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하라.

위의 문제는 N에 대하여 최대한 많이 나눌 수록 과정이 줄어든다. 가능한 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을지 생각해보면 N이 아무리 큰 수여도, K로 계속 나눈다면 수행 횟수를 기하급수적으로 빠르게 줄일 수 있다. 즉 K가 2 이상이면 N을 K로 나누는 것이 1을 빼는 것보다 항상 적은 수행 과정을 거친다.

n, k = map(int, input().split()) # n과 k가 나란히 주어질 때
cnt = 0 # 몇 번 수행했는지 확인


while n > 1: # N이 1 이하면 반복을 멈춤
    if n % k == 0: # n이 k로 나누어 떨어지는 경우
        n = n // k # n은 n을 k로 나눈 몫
        cnt += 1 # 수행 횟수 1추가
    else : # n이 k로 나누어 떨어지지 않는 경우
        n = n -1 # n에서 1 빼기
        cnt += 1 # 수행 횟수 1 추가

print(cnt)

위의 코드는 문제를 먼저 보고 작성한 코드다. n이 1이 될 때까지 반복문을 돌며 n을 작게 만들기 때문에 n이 클수록 실행시간이 오래 걸릴 것이다. 아래는 동빈나님이 작성하신 코드인데, 나누는 과정이 필요한 횟수를 target으로 설정해 실행시간을 크게 줄일 수 있다.

n, k = ap(int, input(),split()) # n, k 입력 받기
cnt = 0

while True:
    tartget = (n//k)*k # n을 k의 배수로 만들기 위한 target 값을 지정
    cnt += (n - target) # k의 배수인 target을 n에서 빼 n에서 1씩 빼는 경우의 수를 더함
    n = target # k의 배수인 target을 n에 대입
    if n < k:
    	break # n이 k보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    cnt += 1
    n //= k
    
cnt += (n-1) # 마지막으로 남은 수에 1씩 빼기
print(cnt)

문제를 빠르게 풀 수 있게 적용된 알고리즘 이기 때문에 target 설정을 한다는 생각을 못했다. 그리고 앞으로도 내가 이걸 생각할 수 있을까...? 싶기도하다. 다양한 예를 적용시켜 완벽하게 이해하고 머릿속에 주입시켜야겠다.

 

 

• <곱하기 혹은 더하기>
• 각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성해라. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이뤄진다고 가정한다.
• 예를들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0+2) x 9) x 8) x 4) = 576 이다.

위의 문제는 대부분의 경우 '+'보다는 'x'가 더 값을 크게 만든다. 다만 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기를 수행하는 것이 효율적이다. 따라서 두 수에 대해 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하는 것이 정답이다.

 

s = input()


if int(s[0]) == 0 or int(s[1]) == 0: # 처음 두 수중 하나라도 0인 경우
    sum = int(s[0]) + int(s[1]) # 두 수를 더함
else: # 처음 두 수가 0이 아닌 경우
    sum = int(s[0]) * int(s[1]) # 두 수를 곱함

for i in range(2, len(s)): # 문자열 3번째 수부터 탐색
    if int(s[i]) <= 1: # 문자열 해당 인덱스가 1 이하인 경우
        sum += int(s[i]) # 더해줌
    else:
        sum *= int(s[i]) # 곱해줌

print(sum)

 

s = input()

result = int(s[0]) # 첫 번째 문자를 숫자로 변경하여 대입

for i in range(1, len(s)):
    num = int(s[i]) # 두 수 중에서 하나라도 0 혹은 1인 경우 더하기 수행
    if num <=1 or result <= 1:
    	result += num
    else:
    	result *= num
        
print(result)

두 코드도 마찬가지로 내가 작성한 코드와 예시 답안으로 작성된 코드. 해결방식은 똑같았으나 확실히 밑에 코드가 간결하고 보기 좋다.