[알고리즘] 그리디 알고리즘

 

그리디 알고리즘

• 현재 상황에서 가장 좋은 방법을 구한다
• 위의 결과가 맞는지 정당성분석이 중요
• 일반적인 상황은 최적의 해를 보장할수없지만 코테에서는 그런식으로 풀리도록 출제됨
  
  
• ex. 거스름돈 문제(가장 큰 화폐단위부터 돈을 거슬러준다)
  동전의 큰 단위가 항상 작은단위의 배수가 되므로 그리디알고리즘을 사용하게됨
  우선 문제풀이를 위한 최소한의 아이디어를 떠올리고 정당한지 검토해야함
  
  
• ex. 주어진 숫자 두개중 첫번째가 1이될때까지 연산 최대 횟수구하기
  첫번째가 2이상이기만 하면 두번째로 나누는 것이 낫다
  주어진 숫자중 두번째로 최대한 많이 나누면 됨(2이상의 수로 나누고, 그다음 1을빼는 작업을 반복)
  
  
• ex. 곱하기 혹은 더하기
  0~9 숫자로 이루어진 문자열 s
  왼쪽에서 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자사이에 x혹은 +연산자를 넣어
  결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램.

import sys

S = sys.stdin.readline().rstrip()
sum = int(S[0])

for i in range(1, len(S)):
    # num이라는 새로운 변수를 만들어 sum과 분리되어 계산함
    # 0이나 1인경우 무조건 더하기로 하기(곱하기보단 더하기가 더 큰수가 나와서)
    # sum도 S의 요소중 하나기 때문에 1 아래로 설정해 더해주었다
    num = int(S[i])
    if num <=1 or sum <=1:
        sum += num
    else:    
        sum *= num

print(sum)

 

• 모험가가 N명 있고, 공포도가 X인 모험가는 X명이상 그룹을 짜야함
• 최대 그룹 수를 구하시오

import sys

n = int(sys.stdin.readline().rstrip())
l = list(map(int, sys.stdin.readline().split()))
l.sort()

cnt = 0 #명수
sum = 0 #총 그룹수

#i는 공포 기준값(인원체크)
for i in l:
    cnt +=1 #첫번째 참가자
    if cnt >= i: #인원넉넉. 공포수만큼 넉넉히 있음.
        sum += 1
        cnt = 0 #그룹 빠져나갔으니 초기화
       
print(sum)