🐤그리디 알고리즘 개요
- 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
- 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
- 그리디 해법은 정당성 분석이 중요하다.
- 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다. - 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
- 하지만, 코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.
[예시] 거스름돈
당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.
N=1,260일때 예시
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
array = [500,100,50,10]
for coin in array:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
[문제1] 1이 될 때까지
(이코테 그리디 실전문제 4번)
- 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
1. N에서 1을 뺍니다.- 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())
count = 0
while(True):
if N==1:
print(count)
break;
if(N%K != 0 ):
count += 1
N -= 1
else:
count += 1
N //= K🙋🏻♀️내가 푼 코드 설명
N이 K의 배수가 아닐때, count를 1씩 증가하고 N에서 1을 뺐다. 이를 반복하여 N이 K의 배수가 되도록 하고, 최종적으로 N이 1일 될 때 증가한 count값을 출력하면서 while문을 빠져나오도록 하였다.
🙋🏻♀️내가 푼 코드의 문제점
내가 푼 풀이는 책과 유튜브에서 설명하듯이 일일이 1씩 빼어 문제를 해결하는 방식이다. 하지만, N이 100억 이상의 큰 수가 되는 경우 빠르게 동작하기 위해 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식의 소스코드도 고려했어야 한다고 생각한다.
🏆정답코드
n, k = map(int, input().split())
result = 0
while True:
#N이 K로 나누어 떨어지는 수가 될 때까지 빼기
target = (n//k)*k
result += (n - target) #1을 빼는 연산 횟수
n = target
#N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
#K로 나누기
result += 1
n //=k
#마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)
[문제2] 곱하기 혹은 더하기
(이코테 그리디 기출문제 2번)
- 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 'x'혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 상식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
- 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0+2)x9)x8)x4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.
🙋🏻♀️내가 푼 코드
"""
아이디어
주어진 문자열 앞에서부터 +와 x연산을 한후 더 큰 값이 나온걸 통과시킨다.
"""
S_input = input()
#문자를 입력받아 char하나를 int형으로 변환해 리스트에 넣어준다.
S = [int(i) for i in S_input]
result = S[0] #첫 비교대상은 첫번째 인자
for i in range(1,len(S)):
if(result + S[i] <= result * S[i]):
result *= S[i]
else:
result += S[i]
print(result)🙋🏻♀️내가 푼 코드 설명
주어진 문자열을 하나하나 분리후 int형으로 만들어 리스트에 넣어준다.
첫 result를 첫번째 인자로 넣어주고, 앞에서부터 순서대로 +와 x 연산을 진행하여 더 큰 값이 나오는 것을 통과시킨다.
이를 for문을 통해 반복해준다.
🏆정답코드
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)🏆정담 문제 해결 아이디어
- 대부분의 경우 '+'보다는 'x'가 더 값을 크게 만든다.
- 다만 두 수 중에서 하나라도 '0'혹은 '1'인 경우, 곱하기보다는 더하기를 수행하는 것이 효율적이다.
- 따라서, 두 수에 대하여 연산을 수행할 때, 두 수 중 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2이상인 경우에는 곱하면 정답이다.
[문제3] 모험가 길드
(이코테 그리디 기출문제 1번)
- 한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
- 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹게 참여해야 여행을 떠날 수 있도록 규정했다.
- 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. N 명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
- 예를 들어 N=5이고, 각 모험가의 공포도가 다음과 같다고 가정하자
2 3 1 2 2
- 이 경우 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있다.
- 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.
🙋🏻♀️내가 푼 코드 및 정답 코드
"""
공포도를 오름차순 한 후, 그룹을 만들 수 있는 조건에 맞는지 부합하는지 확인한다.
"""
N = int(input())
fears = list(map(int, input().split()))
fears.sort()
result = 0 #총 그룹의 수
count = 0 #현재 그룹에 포함된 모험가의 수
for i in fears: #공포도를 낮은 것부터 하나씩 확인하며
count += 1 # 현재 그룹에 해당 모험가를 포함시키기
if count >= i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1 # 총 그룹의 수 증가시키기
count = 0 #현재 그룹에 포함된 모험가의 수 초기화
print(result)🙋🏻♀️내가 푼 코드의 문제점
"또한, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다." 라는 문장을 신경쓰느라 오히려 해결법을 찾는데 어려움을 겪었던 것 같다. 단순하게 오름차순 정렬 후, 그룹을 만들어 현재 그룹에 포함된 모험가의 수와 들어오는 모험가의 공포도를 비교하여 만든 그룹과 멤버 모두를 고려하여 만듬 그룹의 max치는 같다는걸 생각하지 못했다.
[문제4] 큰 수의 법칙
(이코테 그리디 실전문제 2번)
'''
큰 수의 법칙 : 다양한 수로 이루어진 배열이 있을 때,
주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
(단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 업는 것이 이 법칙의 특징이다.
'''
#배열의 크기 N, 더해지는 횟 수 M, K번 초과해서 연속으로 더할 수 없음.
N,M,K = map(int, input().split())
print(N,M,K)
numbers = list(map(int, input().split()))
#print(numbers)
#정렬하기
numbers.sort(reverse=True) #6 5 4 4 2
result = 0
repeat = M//(K+1)
plus = M%(K+1)
print(repeat,plus)
for i in range(repeat):
for j in range(K):
result += numbers[0]
result += numbers[1]
result += (numbers[0]*plus)
print(result)🙋🏻♀️내가 푼 코드 설명
배열을 정렬하여 가장 큰 수와 두번째로 큰 수를 구한다. 가장 큰 수는 K번 두번째로 큰수는 1번 반복되는데, M//(k+1)번 반복하는 규칙이 있다. 그리고 가장 큰 수가 M%(K+1)번 추가로 더해진다. 이를 코드화한다.
2~3번 풀어본 문제인데 풀때마다 항상 헷갈린다. 문제를 그대로 받아들이고 구현하는 것 뿐만아니라 그 속의 새 규칙을 찾아 풀어보자는 생각 또한 항상 가져야 한다고 느끼게 해준 문제이다.
[문제5] 숫자 카드 게임
(이코테 그리디 실전문제 3번)
N, M = map(int, input().split())
cards = []
row = []
for i in range(N):
row = list(map(int,input().split()))
row.sort()
cards.append(row)
def findBigNum(cards,N):
numMax = cards[0][0]
for i in range(N):
if (cards[i][0] > numMax):
numMax=cards[i][0]
# print(cards[i][0])
return numMax
print(findBigNum(cards,N))🙋🏻♀️내가 푼 코드 설명
각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다.
min(), max()함수를 이용해서 풀 수도 있다.
[문제6] 문자열 뒤집기
(이코테 그리디 기출문제 3번)
S = input()
action0 = 0 # 모두 0으로 바꾸는 경우
action1 = 0 # 모두 1로 바꾸는 경우
# 첫 번째 원소에 대해 처리
if S[0] == '1':
action0 += 1
else:
action1 += 1
# 두 번째 원소부터 검사!
for i in range(len(S)-1):
if S[i] != S[i+1]:
if S[i+1] == '1':
action0 += 1
else:
action1 += 1
print(min(action0, action1))🙋🏻♀️내가 푼 코드 설명
모두 0으로 바뀌는 경우와 모두 1로 바뀌는 경우를 모두 구한 후, min함수를 이용해 더 작은 값을 출력한다.
case1) 000 11 00 -> 000 00 00
case2) 111 00 11 -> 111 11 11
첫 번째 원소가 1일 경우를 먼저 처리해준다. (비교대상이 없기 때문에)
앞에 1이 나오면 모두 0으로 바꾸는 action0이 증가하고,
0이 나오면 모두 1로 바꾸는 action1이 증가한다.
두 번재 원소부터는 다음 원소와 값이 다를 때 1이 오면 (01) action0을 증가시키고 0이 오면(10) action1을 증가시킨다.
이후 action0과 action1중 최소값을 출력한다.
[문제7] 만들 수 없는 금액
(이코테 그리디 기출문제 4번)
N = int(input())
coins = list(map(int,input().split()))
coins.sort()
target = 1
for x in coins:
if target < x:
break
target += x
print(target)🙋🏻♀️내가 푼 코드 설명
주어진 동전 배열을 정렬한후, 작은 동전부터 하나씩 target값과 비교한다.
[문제8] 볼링공 고르기
(이코테 그리디 기출문제 5번)
N, M = map(int,input().split())
bowling = list(map(int, input().split()))
count = 0
for i in range(1,N+1):
if bowling.count(i) >= 2:
a = bowling.count(i)
count += (a*(a-1))/2
print(((N*(N-1))/2)-count)
[문제9] 무지의 먹방 라이브
food_times = [3,1,2]
k=6
for i in range(1,k+1):
index = i%len(food_times)
i_list = []
if index == 0:
index = len(food_times)
if food_times[index-1] == 0:
food_times[index%len(food_times)] -= 1
i_list.append(index%len(food_times)+1)
else:
food_times[index-1] -= 1
i_list.append(index)
# print(food_times)
# print(i_list)
print(i_list[0])