Greedy 알고리즘?
- 어떠한 문제가 주어질 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘
- 탐욕적 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 현재 선택이 이후에 미칠 영향에 대해서 고려하지 않는다
- 문제 출제 폭이 넓다
- 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 창의력을 요구
- 가장 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 같은 기준을 슬며시 제시
- 정렬 알고리즘과 짝을 이루어 자주 출제된다.
그리디 알고리즘의 정당성 ?
- 모든 알고리즘 문제에 적용할 수 없다.
- 탐욕적으로 문제에 접근했을 때 해를 구할 수 있다는 보장이 있을 시 매우 효과적이고 직관적이다.
- 문제 해법을 찾을 때 정당성을 검토해야한다.
- 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당성을 검토해야 문제를 풀 수 있다.
ex) 500,100,50,10원 동전 중 거스름으로 줄 수 있는 동전 수가 가장 적은 경우의 동전수
-> 동전이 모두 10의 배수이기에 가장 큰 동전부터 거슬러주면 최소가 된다는 정당성 확보.
문제1. 큰 수의 법칙
문제 :
- 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 다만, 서로 다른 인덱스에 있는 수는 다른 수로 인식한다.
입력 :
- 첫째 줄에 N(2 <= N <= 1,000), M, K(1 <= K <= M <= 10,000) 자연수가 한 줄에 공백으로 주어진다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분하며 각각의 자연수는 1 <= N <= 10,000이다.
출력 :
큰 수 법칙에 따라 더해진 답을 출력
제한조건 :
시간 제한 1초 | 메모리 제한 128MB
- 기본적인 풀이 : O(n)
# 공백으로 구분되어 있는 한 줄 입력 받기
n,m,k = map(int, input().split())
# 공백으로 구분된 N개의 수로 이루어진 리스트 만들기
numArr = list(map(int, input().split()))
// 내림차순 정렬
numArr.sort(reverse=True)
sum = 0
while True:
for i in range(k): # 가장 큰 수를 K번 더하기
if(m == 0) : break
sum += numArr[0]
m -= 1 // 더할 수 있는 횟수 1씩 줄이기
if(m == 0): break
sum += numArr[1] // 다음으로 큰 수 1번 더하기
m -= 1 // 더할 수 있는 횟수 1씩 줄이기
print(sum)
- 알고리즘 개선 : O(1)
# 공백으로 구분되어 있는 한 줄 입력 받기
n,m,k = map(int, input().split())
# 공백으로 구분된 N개의 수로 이루어진 리스트 만들기
numArr.sort()
first = numArr[-1] # 가장 큰 수
second = numArr[-2] # 다음으로 큰 수
# [가장 큰 수 k + 다음 수 + 1] << 하나의 조합이다
# 가장 큰 수가 총 몇개인지 구하기
count = int(m / (k+1)) * k
count += m % (k + 1)
# 결과 구하기
result = 0
result += (count) * first
result += (m - count) * second
print(result)
배운점
단순하게 문제가 주어졌다고 정렬해서 그리디로 접근하는 것이 아닌 문제에 대해서 그리디를 적용할 수 있는 정당성을 고려해서 알고리즘을 적용해야한다.
'알고리즘&자료구조' 카테고리의 다른 글
Implementation(구현) (0) | 2023.05.12 |
---|