[알고리즘] 그리디 알고리즘 (1)

동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ

 

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

 

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

의미하며, 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

 

출처: https://youtu.be/2zjoKjt97vQ

 

예로 N이 1260원일때,

500원 2개, 100원 2개, 50원 1개, 10원 1개로

최적의 해를 나타낼 수 있게 되는 것이 바로 그리디 알고리즘이다.

 

최적의 해를 나타낼 수 있는 이유는 가장 큰 화폐의 단위인 500원이

100원, 50원, 10원 즉, 작은 단위 화폐들의 배수이기 때문이다.

예로 500원, 400원, 100원이라는 잔돈을 800원의 N으로 나누어주게 되면

500원 1개, 100원 3개라는 값이 나오지만 400원 2개라는 최적의 해도

존재하기 때문에 이처럼 최적의 해가 도출이 가능할 때

문제에서 제시하는 결과를 위해 그리디 알고리즘을 사용할 수 있다.

 

위 문제를 파이썬 코드로 나타내면 다음과 같다.

 

n = 1260
count = 0

array = [500, 100, 50, 10]

for money in array:
	count += n // money
    n %= money
    
print(money)

 

리스트에 들어있는 큰 단위의 화폐부터 차례대로 확인하기 위해

for문으로 구성하고 거스름 돈의 개수를 세어 몫을 출력하고,

나눈 나머지가 앞선 화폐 단위 개수를 사용한 만큼을 빼기 때문에

정상적으로 동전의 개수를 셀 수 있게 된다.

 

해당 문제는 화폐의 종류가 K일때, K만큼을 확인하여 반복하기 때문에

시간 복잡도는 O(K)가 된다.

 

 

✔️ 문제 풀어보기 (1, 2)

 

문제) 1이 될 때까지 (https://youtu.be/2zjoKjt97vQ)

 

해당 문제를 풀기 위해서 처음 고안했던 코드는 다음과 같다.

 

import time

N, K = map(int, input().split())

# 시작
start_time = time.time()
count = 0

while N > 1:
    if N % K == 0:
        N /= K
        count +=1
    else:
        N -= 1
        count +=1

print(count)
# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

다음과 같이 작성하게 되면, N과 K가 만약 조건이 억단위로 크다면

시간 제한에 있어서 효율적이지 않은 코드가 될 수 있다.

한번 답안과 비교해보자.

 

import time

N, K = map(int, input().split())

# 시작
start_time = time.time()
count = 0

while True:
    target = (N // K) * K
    count += (N - target)
    N = target

    if N < K:
        break
    
    count += 1
    N //= K

count += (N - 1)
print(count)
# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

N이 K로 나누어 떨어지는 수가 될 때까지 뺀 값을

count에 더해주고 N은 해당 값으로 바뀌게 된다.

또한, N이 K로 나누어 떨어지면 count는 1이 추가되어야 하므로

1이 더해지게 된다. 만약에 N이 K보다 작을 때, 남은 수가 1보다

큰 수라면 1씩 뺀 값들을 최종적으로 더해주게 된다.

 

처음 이러한 알고리즘 공부를 구체적으로 시작하게 되니

작은 수여서 간단한 식으로 풀 수 있는 문제여도

모범 답안처럼 시간 복잡도를 Log로 바꾸어 풀 수 있는 방법

즉, 최대한 복잡도를 줄여서 조건이 커져도 풀 수 있는 풀이를

생각해낼 수 있도록 고민하고 푸는 연습을 해야할 듯 하다.

 

 

문제) 곱하기 혹은 더하기 (https://youtu.be/2zjoKjt97vQ)

 

해당 문제를 풀기 위해 고안했던 첫 풀이는 다음과 같다.

 

import time

S = str(input())

# 시작
start_time = time.time()
number = list()

for i in range(0, len(S)):
    number.append(int(S[i]))

number.sort()
result = 1

for i in range(0, len(number)):
    if 0 in number:
        if number[i] == 0:
            continue
        else:
            result = (result * number[i])
    else:
        result = (result * number[i])
    
print(result)

# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

생각했던 풀이 방법은 0인 숫자와 0이 아닌 숫자로 나뉠 때 연산하는 것인데,

0인 숫자가 문자열에 있으면 0이 아닌 가장 작은 숫자와 더한 뒤

남은 모든 숫자를 곱하는 것이다. 그리고 0인 숫자가 문자열에 없으면

모든 문자열의 숫자를 곱하는 것이 가장 큰 수라고 생각하였다.

 

하지만, 처음부터 잘못 생각한 것은 왼쪽부터 차례대로 연산을 수행해야하는데

마음대로 정렬을 시켜버린 오류를 범했고

또 하나는.모범 답안을 참고하고 이해하면서 고려하지 못한 것이

1일 때도 1을 제외한 가장 작은 숫자와 더한 뒤 나머지 모든 숫자를

곱하는 것이 가장 큰 수가 되기 때문에 모범 답안을 보면서 공부를 진행했다.

 

import time

# 모범답안
data = input()

# 시작
start_time = time.time()
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)

# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

모범답안에서는 result가 0으로 선언되면 곱해지는 값이

0부터 시작하기 때문에 0번째 값부터 저장을 하게 되고,

1부터 data의 길이까지 1이하의 값 즉, 0과 1은 덧셈을 진행하고

그 외의 숫자들은 곱하는 연산을 진행하는

간단한 계산 식으로 구성되어 있다.

 

알고리즘을 공부하면서 엄청 복잡하게 생각하고 시간 복잡도만

줄이려고 애쓰면서 잘못된 로직을 구상하게 되는데,

문제부터 꼼꼼하게 그리고 천천히 읽고 생각하면서

좋은 아이디어가 구상되고 떠오르면 그때 로직을 구성하는

방향으로 공부하는 것이 좋을 것 같다는 생각이 들었다.

 

다음 글은 그리디 문제 3번 모험가 길드부터,

화이팅 💪