[알고리즘] ch03. 그리디 알고리즘(Greedy Algorithm)

<이것이 코딩테스트다 with 파이썬> 책 내용을 바탕으로 작성된 글입니다.

 

 

그리디 알고리즘이란?

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

그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 때문에 그리디 알고리즘은 최적해를 구하는 데 근사하는 방법이기도 하다.

탐욕적 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

탐욕 알고리즘을 적용하려면 문제가 다음 2가지 조건을 성립하여야 한다.

• 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

거스름돈 문제에 그리디 알고리즘의 문제 해결 과정을 적용

1. 선택 절차: 거스름돈의 동전 개수를 최소로 하기 위해 가장 비싼 동전부터 선택한다.
2. 적절성 검사: 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 다음으로 비싼 동전을 선택한다. 
3. 해답 검사: 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.

 

92p 큰 수의 법칙 

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

array.sort()

sum = 0
count = 0
for _ in range(m):
	if (count == 0):
		sum += array[n-1]
		count += 1
	elif (count % k != 0):
		sum += array[n - 1]
		count += 1
	else:
		sum += array[n -2]
		count += 1
    
print(sum)

96p 숫자 카드 게임

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

min_value = 0
for _ in range(n):
	array = list(map(int, input().split()))
	array.sort()
	if (min_value < array[0]):
		min_value = array[0]

print(min_value)

99p 1이 될때까지

#1이 될 때까지
n, k = map(int, input().split())

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