[Algorithm] 1. 그리디

1. 그리디 개념 및 아이디어

 

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

해결법: 최소한의 아이디어를 떠올릴 수 있는 능력

평가: 가장 좋아보이는 것만 반복해도 최적의 해를 구할 수 있는지 검토해야된다.

 

그리디 알고리즘의 문제: 최적의 해를 보장 할 수 없을 때가 많지만 코딩테스트에서는 그리디로 얻은 해가 최적의 해로 설정해놓고 문제를 내기에 그리디 문제라는 것만 알면된다.

 

2. 예제문제

예제 1) 거스름 돈 문제

 

아이디어: 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면된다. => 그래야 돈이 빨리 0으로 수렴되니까

정당성: 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기에 가장 큰 화폐 단위부터 나눠주는게 맞다.

그리디 알고리즘은 최소한의 아이디어와 정당성 분석 필요한 알고리즘!

 

n = 1260

count = 0

array =[500, 100, 50, 10]

for coin in array:

    count += n // coin

    n %= coin

print(count)

 

시간 복잡도: 화폐의 종류 K라고 할 때 O(K) => 종류에만 영향을 받음

 

예제 2) 1이 될 때까지 최소 횟수를 구하는 문제(나누기와 빼기만 가능)

 

아이디어: 최대한 많이 나누기를 수행하면 된다. 왜냐하면 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다. 가능하면 최대한 많이 나누는 작업!

정당성: N이 아무리 큰 수여도 K로 나눈다면 기하급수적으로 빠르게 줄일 수 있다. K가 2이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.

 

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

result = 0

while True:

    target = (n//k)*k

    result += (n-target)

    n = target

    if n<k:

        break

    result += 1

    n //= k

result += (n-1)

print(result)

 

예제3) 곱하기 혹은 더하기해서 마들어질 수 있는 가장 큰수를 구하는 문제

 

아이디어: '+'보다는 'x'가 더 값을 크게 만든다. 다만 두 수 중에서 하나라도 '0'혹은 '1'인 경우에는 곱하기보다는 더하기를 수행하는 것이 효율적이다. 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하며 두수가 모두 2이상인 경우에는 곱하자

 

data = input()

result = int(data[0])

for i in range(1, len(data)):

    num = int(data[i])

    if num<=1 or result <=1:

        result += num

    else:

        result *= num

print(result)

 

 

예제4) 모험가 길드 공포도가 X인 모험가는 반드시 X명이상으로 구성한 모험가 그룹에 참여해야하고 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 문제

아이디어: 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 설정하면 공포도가 오름차순되어있다는 가정 하에 항상 최소한의 모험가의 수가 그룹 결성이되어 최대한 많은 그룹이 형성되게 된다.

 

n = int(input())

data = list(map(int, input().split()))

data.sort()

result = 0

count = 0

for i in data:

    count += 1

    if count >= i:

        result += 1

        count = 0

print(result)