그리디 알고리즘

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 방법이다.

그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 아래와 그림과 같이 매 선택에서 최적의 선택을 했을때, 전체 결과의 최적이 되지 못하는 경우는 그리디 알고리즘을 사용하지 않는다.

https://besjournals.onlinelibrary .wiley .com/doi/full/10.1111/1365-2656.12963

 

문제 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,k = map(int,input().split())

result = 0

while True:
    if n < k :
        break
    else:
        result += n%k +1
        n //= k

result += n-1


print(result)

 

문제 2

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '*' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하라. 단, +보다 *를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정하라.
• 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) * 9) * 8) * 4) = 576이다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.

input_list = map(int,input().split())

result = 0

for i in input_list:
    if (result>=2)&(i>=2):
        result *= i
    else:
        result += i
print(result)

 

문제 3

• 한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
• 모험가 길드장인 동비니는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
• 동비니는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. N명의 모험가에 대한 정보가 줘졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하라.

input_list = list(map(int,input().split()))

input_list.sort()

result = 0

team=[]
while len(input_list)>0:
    fear = input_list.pop(0)
    team.append(fear)
    if len(team)>=team[-1]:
        result+=1
        team=[]
    else :
        pass
print(result)

 

문제 출처 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2