[코딩테스트] 그리디
➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.
✔ 그리디란?
그리디(greedy)는 '탐욕스러운'이라는 뜻으로 나에게 가장 이득이 되는, 최소한의 노력으로 최대한의 결과를 내고자 하는 것을 뜻한다.
따라서 그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만을 고르는 방법이다. 이 방법이 언제나 같은 방법으로 사용되어 최선의 결과를 나을 수 있는지 고민해야한다.
✔ 문제1 : 거스름돈
편의점에서 N원을 구매한 손님에게 500원, 100원, 50원, 10원 동전으로 돈을 거슬러줄때 동전의 최소개수를 구하시오. (단, 동전의 개수는 무한하고, 거슬러 줘야 할 돈 N원 은 항상 10의 배수)
👉 문제해결과정
- 가장 큰 화폐단위부터 거슬러준다.
편의점에서 N원을 구매한 손님에게 500원, 100원, 50원, 10원 동전으로 돈을 거슬러줄때 동전의 최소개수를 구하시오. (단, 동전의 개수는 무한하고, 거슬러 줘야 할 돈 N원 은 항상 10의 배수)
if) 3740원이면
500원 - 7개 (500원으로 줄 수 있는 돈 3500원)
100원 - 2개 (나머지 240원 중에서 100원으로 줄 수 있는 돈 200원)
50원 - 0개 (나머지 40원 중에서 500원으로 줄 수 있는 돈 0원)
10원 - 4개 (나머지 40원 중에서 10원으로 줄 수 있는 돈 40원)
총 7+2+4 = 13개의 동전이 필요하다.
n = 3740 #거스름돈
count = 0 #거스름돈에 사용될 동전의 개수
array = [500, 100, 50, 10]
for coin in array: #array에 있는 원소 하나씩 돌기( 큰 단위부터)
# count = count + (n // coin)
count += n #coin # 거스름돈을 해당 동전단위로 나누었을 때의 몫(동전개수)를 count에 더하기
# n = n % coin
n %= coin #n은 거스름돈을 해당 동전단위로 나누었을 때의 나머지
print(count) #총 몇개의 동전이 필요한지
👉 정당성 분석
동전에서 큰 단위는 항상 작은 단위의 배수임으로 작은 단위의 동전들을 합하였을 때, 큰 단위의 동전들 이외의 해가 나올 수 없다.
👉 시간 복잡도 분석
화폐의 종류 = K 일때, 소스코드이 시간 복잡도는 O(K)이다.
- 빅-오-표기법에서 수행히간은 알고리즘이 수행하는 기본 연산 횟수를 뜻한다.
따라서 시간복잡도는 거스름돈의 크기와 무관하며 동전의 총 개수(종류)에만 영향을 받는다.
✔ 문제2 : 1이 될 때까지
어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다. 과정이 수행되어 N이 1이 되는 최소 횟수를 구한다. (단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N과 K는 자연수이다. )
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
👉 문제해결과정
- N이 최대한 K로 많이 나누어지도록 한다.
- 나누어지지 않을때 1을 뺀다.
어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다. 과정이 수행되어 N이 1이 되는 최소 횟수를 구한다. (단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N과 K는 자연수이다. )
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
if) n=37 , k=5일 때,
5로 나누어떨어지는 n보다 작거나 같은 수는 35이다.
그러면 37-35=2, 1을 2번 빼고
그다음 35 % 5 = 7, 7번 나눈다.
총 2+7 =9번 연산이 필요하다.
n, k = map(int, input().split())
count = 0 #연산 횟수
while True:
target = (n//k) * k #n이 k로 나누어질 수 있는 가장 큰 n의 값을 찾는다(target은 k로 나누어떨어지는 n보다 작거나 같은 수)
#count = count + (n-target)
count += (n-target) #(n-target)은 1을 빼는 횟수
n = count
if n < k : # n이 k보다 작을때 while문 탈출
break
# n을 k로 나누기
count += 1
#n = n // k
n //= k
if n > 1: # n이 1보다 크다면
count++
n--
else:
print(count)
👉 정당성 분석
1을 빼는 것보다 K로 나누는 것이 N의 수가 작아지는 방법이다.
👉 시간 복잡도 분석
while을 사용하게 되면 시간복잡도가 로그값이 나온다.
✔ 문제3 : 곱하기 혹은 더하기
각 자리 숫자가(0~9)로 이루어진 문자열 S 왼쪽부터 오른쪽으로 각 숫자에 'x' 혹은 '+' 연산자를 넣어 가장 큰 수를 만든다. ( 단 모든 연산은 왼쪽에서부터 이루어진다. 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.)
👉 문제해결과정
- 연속해 있는 두 수 중, 하나라도 0또는 1인 경우 -> +
- 그 이외의 경우(두 수가 모두 2 이상일 때)는 -> x
각 자리 숫자가(0~9)로 이루어진 문자열 S 왼쪽부터 오른쪽으로 각 숫자에 'x' 혹은 '+' 연산자를 넣어 가장 큰 수를 만든다. ( 단 모든 연산은 왼쪽에서부터 이루어진다. 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.)
if) 07315 일때
((((0+7)*3)+1)+5)
data = input()
front = int(data[0]) #앞에있는 값
for i in range(1, len(data)):
back = int(data[i]) #뒤에있는 값
if front <=1 or back <=1:
front += back
else:
front *= back
print(front)
👉 정당성 분석
일반적으로 +보다 x가 값을 더 크게 만든다. 하지만 두 수 중, 하나라도 0또는 1인 경우는 +가 값을 더 크게 만든다.
✔ 문제3 : 모험가 길드
각 모험가가 가지고있는 공포도 N이 있다. 각 모험가 그룹는 공포도가 X인 모험가는 반드시 X명 이상 구성되어야한다. 최대 몇개의 모험가 그룹을 만들 수 있는가?( 모든 모험가가 그룹에 들어갈 필요는 없다.)
👉 문제해결과정
- 공포도를 오름차순으로 정렬한다.
- 가장 낮은 공포도 부터 차례대로 확인한다.
- 현재 확인하고 있는 공포도의 크기(수) 만큼 현재 확인하고 있는 공포도를 가진 모험가 존재한다면 이를 그룹으로 묶는다.
각 모험가가 가지고있는 공포도 N이 있다. 각 모험가 그룹는 공포도가 X인 모험가는 반드시 X명 이상 구성되어야한다. 최대 몇개의 모험가 그룹을 만들 수 있는가?( 모든 모험가가 그룹에 들어갈 필요는 없다.)
n = int(input())
data = list(map(int, input().split())) #공포도 리스트
data.sort() #오름차순 정렬
result = 0 #총 그룹의 개수
member = 0 #현재 그룹에 포함된 모험가의 수
for i in data: # 공포도를 낮은 것부터 하나씩 확인
member += 1 #현재 그룹에 해당 모험가를 포함시키기
if member >= i: #i는 공포도, 현재 그룹에 포함된 모험가의 수가 현재 공포도 이상이라면, 그룹 결성
result += 1 #총 그룹의 수 증가시키기
member = 0 #현재 그룹에 포함된 모험가의 수 초기화
print(result)
👉 정당성 분석
그룹수를 최대로 만들려면 가장 작은 단위로 묶어야한다. 따라서 오름차순 정렬 후 , 공포도와 현재 그룹의 멤버수를 비교해야한다.
🌱 결론
그리디 알고리즘에서는 문제 풀이를 위한 최소한의 아이디어로 모든 상황에 적용시켜 최적의 해를 구할 수 있는지, 그리고 이 아이디어가 정당한지 검토한다!
Author And Source
이 문제에 관하여([코딩테스트] 그리디), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soy0830/코테-그리디저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)