[알고리즘]그리디

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

🧤 그리디(탐욕법)이란?

⇒ 나머지 경우의 수를 다 제쳐두고 가장 최선의 방법 한개만 파고 들어서 문제를 푸는 방법이다. 예를 들면 최소동전 문제가 있다. (ex. 동전으로 1400을 만들때 동전을 가장 적게 쓰는 경우의 수 찾기)

⇒ 매 순간 가장 좋아보이는 방법을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

💡 그리디문제는 이 문제가 그리디인가? 반례가 있는것은 아닐까? 라는 고민하는 것이 가장 어렵다고 한다. 그래서 끊임없이 이 문제를 그리디로 풀 수 있는지, 반례가 있을지 없을지 고민하는것이 정상이라고 한다.

 

그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

대표적인 문제 유형이 "거스름돈을 동전으로 나눠줄 수 있는 경우의 수" 인데, 이와 같은 경우 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘이 가장 적합하다고 본다.

 

다음은 그리디 알고리즘 예제이다.(난이도 하)

정답 👇🏻👇🏻👇🏻

#큰수의 법칙
n, m, k= map(int,input().split())

number = list(map(int, input().split()))
number.sort(reverse=True) #내림차순

result =0

if number[0] == number[1]:
    result = number[0]*m
else:
    value = m//(k+1)
    remain = m%(k+1)
    result = value*(number[0]*k + number[1])+(number[0]*remain)

print(result)

위 문제는 반복되는 수열에 대해서 판단하면 이후 로직이 쉽게 짜여진다.

 

 

정답 👇🏻👇🏻👇🏻

#숫자 카드 게임
n, m = map(int, input().split())

rows = n
cols = m
arr = [[0 for j in range(cols)] for i in range(rows)]

for _ in range(n):
    number = list(map(int,input().split()))
    for i in range(m):
        arr[_][i]=number[i]


result = [0]*n
for i in range(n):
    mi = min(arr[i])
    result[i] = mi


print(max(result))

#숫자 카드 게임 (더 좋은 풀이)
n,m = map(int, input().split())

result = 0

for i in range(n):
    data = list(map(int, input().split())) #2차원 배열에 저장할 필요없이 바로바로 비교하기
    min_data = min(data)
    result = max(result, min_data)

print(result)

#숫자 카드 게임(반복문 이용)

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

result = 0


for i in range(n):
    data = list(map(int, input().split()))
    min_data = 100010911
    for a in data:
        min_data= min(min_data, a)
    result = max(result, min_data)

print(result)

이 문제를 푸는 아이디어는 바로 '각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰수'를 찾는 것이다.

 

 

정답 👇🏻👇🏻👇🏻

#1이 될때까지

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

cnt =0
while n!=1:
    if (n % k)==0:
        n = n/k
        cnt += 1
    else :
        n = n-1
        cnt += 1


print(cnt)