그리디 알고리즘

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

코딩 테스트에서 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

• 3-1 거스름돈

  # 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정. 
  # 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 
  # 단, 거슬러 줘야 할 돈은 항상 10의 배수이다.
  # ----------------------------------
  # 가장 큰 화폐 단위부터 돈을 거슬러 주는 것!
  def change(money):
    tmp = money
    change_dict = {500:0,100:0,50:0,10:0}
    for key,val in change_dict.items():
      value = tmp//key
      if value != 0:
        val=value
        change_dict[key] = val
      tmp %= key
    print(change_dict)
  if __name__ == '__main__':
    money = 1260
    change(money)

  def change(money):
  	coin_types = [500,100,50,10]
  	for coin in coin_types:
  		count += n // coin
  		n %= coin 
  	print(count)
  if __name__ == '__main__':
    money = 1260
    change(money)

  대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 다이나믹 프로그래밍이나 그래프 알고리즘 등ㄹ으로 문제를 해결할 수 있는지를 재차 고민
  
• 3-2 큰 수의 법칙

  # 입력값
  # 5 8 3
  # 2 4 5 4 6
  # 출력값
  # 46
  
  def p3_2():
    n,m,k = map(int,input().split(" "))
    data = list(map(int,input().split(" ")))
    
    data.sort()
    max1=data[n-1]
    max2=data[n-2]

  • 내가 푼 문제 및 단순하게 푼 문제

    	#----------- 내가 푼 문제 -----------
      # 걸리는 시간: 10.310476303100586
      s = 0 #총합
      c = 0
      while m!=0:
        if c!=k:
          s+=max1
    
        else:
          s+=max2
          c=-1
        c+=1
        m-=1
      print(s)
      #----------- 단순하게 푼 문제 -----------
      #걸리는 시간: 2.812513828277588
      result = 0
      while True:
        for i in range(k):
          if m==0:
            break
          result += max1
          m-=1
        if m==0:
          break
        result += max2
        m-=1
      print(result)

  • 반복되는 수열에 대해 파악

    • 가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.
      - 위의 예시에서는 [6,6,6,5]가 반복
      - 수열의 길이 : K+1
      - 수열이 반복하는 횟수 : M을 K+1로 나눈 몫
      - 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수
      - M이 K+1로 나누어 떨어지지 않는 경우도 고려
      - M을 K+1로 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다.
      - 가장 큰 수가 더해지는 횟수
      - int(m/(k+1))k + m%(k+1)
      - 두 번째로 큰 수 더하기
      - (m-count) second

      	#---------------
        # 가장 큰 수가 더해지는 횟수 계산
        # 걸리는 시간: 3.988926410675049
        count = int(m/(k+1))*k
        count += m%(k+1)
      
        result = 0
        result += (count)*max1
        result += (m-count)*max2
        print(result)

• 3-3 숫자 카드 게임 (p.96)

  # 입력값
  # 2 4
  # 7 3 1 8
  # 3 3 3 4
  # 출력값
  # 3
  # 내가 생각한 답안
  def p3_3():
    n,m = map(int,input().split(" "))
    result=0
    for i in range(n):
      data = list(map(int,input().split(" ")))
      min_value = min(data)
      if min_value>result:
       result = min_value
    print(result)

• 3-4 1이 될 때까지

  # 입력값
  # 25 5
  # 출력값
  # 2
  def p3_4():
    n,k = map(int,input().split(" "))
    result = 0
   # 내가 생각한 코드
    while True:
      if n==1:
        break
      if n%k == 0:
        n/=k
      else:
        n-=1
      result+=1
    print(result)
  
  # N의 범위가 10만 이하
  # N이 100억 이상의 큰 수가 되는 경우를 가정했을 때
  	while True:
  	  target = (n//k)*k
  	  result += (n-target)
  	  n = target
  		# n이 k보다 작을 때 반복문 탈출
  	  if n<k:
  	    break
  		# k로 나누기
  	  result+=1
  	  n//=k
  	result += (n-1)
  	print(result)
  

  | 참조: 이것이 취업을 위한 코딩테스트다 with Python