Python 그리디 알고리즘

코딩테스느에서 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는상황에서만, 그리디 문제로 출제가 된다

최적의 해를 구하기 위해 가장큰 화폐단위부터 돈을 거슬러준다

n = 1260
count = 0

array = [500, 100, 50, 10]

for coin in array:
  count += n // coin
  n %= coin

print(count)

화폐의 종류가 K라면 소스코드의 시간복잡도는 0(K)이다.

N이 K로 나누어지면 나누고 안나누어지면 1은 빼는 작업을 반복한다.

# N과 K를 공백을 기준으로 구분하여 입력 받기
n,k = map(int, input().split())

result = 0;

while True:
  #N이 K로 나누어 떨어지는 수가 될때까지 빼기
  target = (n//k)*k
  result += (n - target)
  n= target
  #N이 K보다 작을때 반복문 탈출
  if n< k:
    break
  #K로 나누기
  result += 1
  n //=k

#마지막으로 남은수에 대하여 1씩 빼기
result += (n-1)
print(result)

연산하는 두수를 비교하여 두수중 하나라도 1이거나 0이면 더하고 아니면 곱하는 프로그램작성

data = input()

#첫번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
  #두 수 중에서 하나라도 '0'혹은 '1'인 경우, 곱하기보다는 더하기
  num = int(data[i])
  if num <= 1 or result <=1:
    result += num
  else:
    result *= num

print(result)

공포도를 오름차순으로 정렬한뒤 앞에서부터 공포도와 그룹을 만드는 수를 비교한다.

member_num = int(input())
fear_score = list(map(int, input().split()))
fear_score.sort()

#총 그룹의 수
result = 0
#현재그룹에 포함된 모험가의 수
count = 0

#공포로들 낮은것부터 하나씩 확인하기
for i in fear_score:
    count += 1 #현재 그룹에 해당모험가 포함시키기
  if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹형성
    result += 1 #총 그룹의 수 증가
    count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result)