그리디 알고리즘

* 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은것만 고르는 방법

* 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제 됩니다.

 

 

<문제> 거스름돈 문제

- 카운터에는 거스름돈으로 사용할 500, 100, 50, 10원 짜리 동전이 무한히 존재한다고 가정할때 손님에게 거슬러주어야할 동전의 최소 갯수구하시오. 

거슬러주어야할돈 N , N은 항상 10의 배수

 

1. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐단위부터 거슬러준다.

 

n = 1260 
count = 0

array = [500, 100, 50, 10]

for coin in array :
  count += n // coin	#나누기
  n = n%coin			#나머지

print(count)

 

 

 

 

<문제> 1이 될 때까지

- 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질때만 선택할 수 있습니다.

1. N에서 1을 뺍니다.

2. N을 K로 나눕니다.

- 예를 들어 N이 17, K가 4라고 가정합니다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩닌다. 이는 N을 1로 만드는ㄴ 최소 횟수입니다.

- N과 K가 주어질때 N이 1이 될 때까지의 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요,

N = 25
K = 3

res = 0
while N > 1 :
  if N % K == 0 :
    N = N // K
    res += 1
  else :
    N += -1
    res += 1
print(res)


n = 25
k = 3
while True :
  # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
  target = (n // k) *k #나누어떨어지지않을때 가장 가까운 나누어 떨어지는 수를 찾는다.
  res += (n - target) #그다음 n에서 나누어떨어지는 수를 빼면 나머지가 res로 들어감
  n = target
  
  # N이 K보다 작을때 (더이상 나눌수 없을때 ) 반복문 탈출
  if n < k :
    break
  
  #k로 나누기
  res += 1
  n = n // k

res += (n-1)
print(res)

 

 

 

<문제> 곱하기 혹은 더하기

- 각 자리가 숫자(0부터9)로만 이루어진 문자열 S가 주어졌을때,  왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질수 있는 가장 큰수를 구하는 프로그램을 작성하세요.

던, +보다 x를 먼저 계산하는 일방적인 방식과 달리, 모든 연산은 왼쪽에서 부터 순서대로 이루어진다고 가정합니다.

 

s = "567"

res = 0

for i in range(len(s)) :
  #첫번째 인덱스 담기
  if i == 0 :
    res = int(s[i])
  else :
    # 1보다 작으면 더하기 
    if res <= 1 or int(s[i]) <= 1 :
      res += int(s[i])
    else :
      res *= int(s[i])

print(res)


s = "567"

#첫번째 인덱스 담기
res = int(s[0])
for i in range(1, len(s)) :

  num = int(s[i])
  if num <= 1 or res <= 1 :
    res += num
  else :
    res *= num

print(res)

 

 

 

 

<문제> 모험가 길드

- 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

- 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시  X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했씁니다.

- 동빈이는 최대 몇 개의 모험가 구릅을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을떄 , 여행을 떠날수 있는 그룹의 최댓값을 구하는 프로그램을 작성하세요

n = 5
user = [2,3,1,2,2]

count = 0 #현재그룹에 포함된 모험가의 수
result = 0 #총 그룹의 수
user.sort()

for i in user : 
  count += 1 			#현재 그룹에 모험가를 넣는다
  if count >= i :		#현재 그룹에 있는 유저 수보다 현재 공포도 이상이라면 그룹을 결성한다
    count = 0
    result += 1


print(result)