그리디 알고리즘
- 현재 상황에서 가장 좋은 것을 고르는 알고리즘
- 일반적인 그리디 알고리즘 문제는 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구
- 정당성 분석이 필요
정당성 분석이란? 단순히 가장 좋아보이는 것을 선택해도 최적의 해를 구할 수 있는 지 검증하는 과정
💡문제 1. 거스름돈 문제
- 거스름돈을 거슬러 줄 때 동전의 개수가 최소가 되게 거슬러 주고 이 때 동전의 개수 구하는 문제
- 해결 방법 : 큰 단위의 동전부터 가장 작은 단위의 동전까지 순차적으로 동전 카운팅
- 정당성 분석 : 큰 단위의 동전이 작은 단위의 동전의 배수이기 때문에 그리디로 해결 가능
- 문제 해결 코드
def main():
n = int(input())
count =0
coin_types = [500,100,50,10]
for coin in coin_types:
# 거슬러 줄 수 있는 동전의 개수를 높은 단위 순으로 나누어 count++
count += n // coin
# 거슬러 주고 남은 금액처리
n %= coin
print(count)
if __name__ == "__main__":
main()https://github.com/ybkim-dev/algorithms/blob/master/greedy/exchanges.py
💡문제 2. 1이 될 때까지
- 양의 정수 N이 1이 될 때까지 1을 빼거나 나누기 연산의 최소 횟수 구하기
- 해결 방법 : 나누기 연산을 가능한 많이 수행하여 문제 해결
- 정당성 분석 : 나누기 연산이 빼기 연산보다 더 많이 N을 줄일 수 있기 때문에 최소 연산 횟수를 구할 수 있음이 자명함
- 문제 해결 코드
def main():
n, k = map(int, input().split())
count = 0
# n이 커지는 경우에는 시간초과가 날 수 있으므로 빼기 연산의 시간 줄임
while True:
temp = (n // k) * k
count += n - temp
n = temp
if n < k:
# n이 k보다 작으면 후에 빼기 연산만 해주면 됨.
break
# 나누기 연산
n //= k
count += 1
# 1이 될 때까지 나머지 빼기 연산
count += (n-1)
print(count)
if __name__ == "__main__":
main()https://github.com/ybkim-dev/algorithms/blob/master/greedy/1이%20될%20때까지%20with%20short%20time.py
💡문제 3. 곱하기 혹은 더하기
- 곱, 덧셈 연산을 사용해 숫자들에 대해 순차적으로 연산을 수행할 때, 최대값 구하기
- 해결 방법 : 문제 2와 마찬가지로 곱셈 연산을 가능한 많이 수행하여 문제 해결. 단, 두 숫자 중 하나라도 1이하일 경우에는 덧셈 연산 수행
- 정당성 분석 : 곱셈 연산이 덧셈 연산보다 최대값을 생성하는데 유리함이 자명함
- 문제 해결 코드
def main():
# string type의 input 입력 받아 정수형 배열에 담기
input_string = input()
num = []
for i in range(len(input_string)):
num.append(int(input_string[i]))
# 첫, 두번째 인자들이 1이하 혹은 0이라면(음수는 없다고 하므로) + 연산 둘다 1이상의 값이라면 * 연산을 하는 것이 최대
# greedy : 곱하기 연산을 최대로 하게 만들어야 함. 곱하기 연산이 더하기 연산보다 숫자를 키우는데 효과적임이 자명.
first = num[0]
for i in range(1, len(num)):
if first <= 1 or num[i] <= 1:
first += num[i]
else:
first *= num[i]
print(first)
if __name__ == "__main__":
main()https://github.com/ybkim-dev/algorithms/blob/master/greedy/곱하기%20혹은%20더하기.py
💡문제 4. 모험가 길드
- 모험가들의 공포도가 주어지고 공포도의 값에 따라 길드의 수를 정할 수 있을 때 그 수의 최대값 구하기
- 해결 방법 : 모험가들의 공포도를 오름차순 정렬한 후, 공포도의 값과 그룹 내의 모험가의 인원수가 일치할 때 길드 생성하여 카운팅
- 정당성 분석 : 작은 공포도의 모험가는 적은 수로 길드를 생성할 수 있고 공포도를 오름차순 정렬했으므로 최대한 많은 수의 길드를 생성할 수 있음이 자명
- 문제 해결 코드
def main():
num_list = list(map(int, input().split()))
# 오름차순 정렬
num_list.sort()
# 그룹 개수
group_count = 0
# 인원 수
soldier_count = 0
for elem in num_list:
# soldier_count 증가하면서 elem과 값이 일치하면 그룹 생성.
# 오름차순 정렬 후 가능한 많이 그룹을 만들기 위해서는 최소 인원의 생성 조건으로 그룹을 생성해야 함이 자명함.
soldier_count += 1
if soldier_count == elem:
group_count += 1
soldier_count = 0
print(group_count)
if __name__ == "__main__":
main()https://github.com/ybkim-dev/algorithms/blob/master/greedy/모험가%20길드.py
초보 개발자