알고리즘 기초 - 그리디

반응형

"그리디" 방법이란?

현재의 상황에서 지금 당장 좋은 것만 선택하는 방법입니다.

가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해에 도달할 수 있을지 검토하는 정당성 분석이 가장 중요합니다.

​

대표적인 문제

그리디를 이용해 해결할 수 있는 문제 중 가장 대표적인 문제로는 "1이 될 때까지" 문제가 있습니다.

#어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
#단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

#1. N에서 1을 뺀다.
#2. N을 K로 나눈다.
#입력 예시: 17 4
#출력 예시: 2

def solution(n, k):
    c = 0
    while True:
        if n%k == 0:
            n = n//k
            c +=1
        else:
            n = n-1
            c += 1

        if n == 1:
            break
    return c
print(solution(25,5))

위 방법은 반복문을 이용하여 나누기 연산을 할지, 빼기 연산을 할지 계속해서 검사하는 방법입니다. 아마 그리디 방법을 몰랐다면 위 방법처럼 해결해야 했을 것입니다. 하지만 아래 코드처럼 그리디 방법을 이용하면 반복문을 한 번 거칠 때마다 무조건 나누기 연산을 수행하도록 해 줄수 있습니다. 이 방법은 입력 n이 기하급수적으로 줄어들게 되는 장점이 있습니다.

def solution(n, k):
    c = 0
    while True:
        target = (n//k)*k
        c += (n-target)
        n = target
        if n < k:
            break
        cnt += 1
        n //= k
    c += (n-1)
    return c
print(solution(25,5))

 

두 번째 문제로는 "곱하기 혹은 더하기"가  있습니다.

#각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 
#왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 
#결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 
# 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

#입력 예시: 02984
#출력 예시: 576 

def solution(s):
    result = int(s[0]) # 첫번째 문자를 숫자로 변경
    for i in range(1, len(s)):
        n = int(s[i])
        
        # 두 수 중에서 하나라도 0 혹은 1인 경우, 
        # 곱하기보다는 더하기가 값이 더 크므로 무조건 더하기를 수행하도록 합니다.
        if result <= 1 or n <= 1: 
            result += n
        else:
            result*=n
    return result

print(solution('02984'))

 

 

마지막으로 "모험가 길드" 문제입니다.

#한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데,
#공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 
#모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 
#구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 
#여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

#입력 예시: 5, [2 3 1 2 2]
#출력 예시: 2

def solution(n, m): 
    ## 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는
    # 공포도보다 크거나 같다면 이를 한 그룹으로 설정해 주는 방향으로 코드를 작성합니다.
    m.sort() # 오름차순 정렬
    result, c = 0, 0
    for i in m:
        cnt+=1 # 현재 그룹에 해당 모험가를 포함시킵니다.
        
        # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹을 결성합니다.
        if c>=i: 
            result+=1
            c=0

    return result

print(solution(5, [2, 3, 1, 2, 2]))