[이코테 알고리즘] - 그리디

📍 그리디

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
따라서 코딩테스트의 그리디 문제의 경우 무조건 최적의 해가 되도록 출제 된다.

🔎 정당성 분석

거스름돈 문제에서 그리디가 최적의 해를 보장하는 이유는 '동전 중 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위의 동전들을 종합해 다를 해가 나올 수 없기 때문이다'

🔎 시간복잡도 분석

화폐의 종류가 K일 때 소스코드의 시간복잡도는 금액과는 상관없이 O(K)이다.

📌 예제

• 예제 1 ) 1이 될 때까지

# n, k를 입력받아 n=1이 될 때까지 다음 조건을 수행
# 1. n-1
# 2. n/k (단, n이 k로 나누어 떨어져야 함)
# 이때 연산 횟수의 최솟값은?

import sys
input = sys.stdin.readline

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

while True:
    target = (n//k) * k         # k로 나누어 떨어지는 n에 가까운 수를 타겟으로 설정
    result += n - target        # 타겟이 될때까지 -1한 횟수 더함
    n = target                  # n = target 값으로 재설정
    if n < k:                   # n이 k값보다 작아지면
        break
    n //= k
    result += 1

result += (n-1)                 # k보다 작은 n이 1이 될때까지 -1 연산한 횟수 더해
print(result)

• 예제 2 ) 곱하기 or 더하기

# 문자열 S가 주어졌을 때 왼->오 순서대로
# +, x로 만들 수 있는 가장 큰 수 출력

import sys
input = sys.stdin.readline

data = input().rstrip()
result = int(data[0])

for i in range(1, len(data)):       # 인덱스 1부터 보기 시작
    num = int(data[i])              # num에 문자열의 각 자리의 수 대입
    if num <= 1 or result <= 1:     # num값이 1이하거나 result값이 1이하면
        result += num               # 더하고
    else:                           # 그 외에는
        result *= num               # 곱함

print(result)

• 예제 3 ) 모험가 길드

# 문자열 S가 주어졌을 때 왼->오 순서대로
# +, x로 만들 수 있는 가장 큰 수 출력

import sys
input = sys.stdin.readline

data = input().rstrip()
result = int(data[0])

for i in range(1, len(data)):       # 인덱스 1부터 보기 시작
    num = int(data[i])              # num에 문자열의 각 자리의 수 대입
    if num <= 1 or result <= 1:     # num값이 1이하거나 result값이 1이하면
        result += num               # 더하고
    else:                           # 그 외에는
        result *= num               # 곱함

print(result)

🙏 참고

👉 이것이 취업을 위한 코딩테스트다 with 파이썬