그리디

GoldenDusk·2022년 2월 1일

그리디 알고리즘

알고리즘 공부

목록 보기

1/14

그리디 정리 노션 버전

📚 당장 좋은 것을 선택하는 그리디 알고리즘

단순하지만 강력한 문제 해결 방법
탐욕법 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법의 알고리즘
창의력을 요구, 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 ok
순간 가장 좋아 보이는 것을 선택, 현재의 선택이 나중에 미칠 영향 고려 No!
정렬 알고리즘과 짝을 이뤄서 출제 ⇒ ‘가장 큰 순서대로’와 같은 기준 제시

📝 코테에서 만나게 될 알고리즘 유형

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징 : 그리디
알고리즘 사용 방법을 정확히 알고 있어야 해결 가능 : 정렬, 최단경로 등

📝 예시1 거스름돈

가정) 카운터에 거스름돈으로 사용할 500, 100, 50, 10원짜리 동전이 무한 존재한다고 가정시 손님에게 거슬러 줘야 할 N원일 때, 거슬러 줘야 할 동전의 최소 개수는?(단, 거슬러줘야 할 돈 N은 항상 10의 배수)

A : ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것

가정) 남은돈 N원 : 1260원
500원 짜리 2개를 줌

남은 돈 : 260원
100원짜리 2개를 줌

남은 돈 : 60원
50원짜리 1개를 줌

남은 돈 : 10원
10원짜리 1개를 줌 ⇒ 동전의 최소 개수 : 6개

참고) 파이썬 기호
- ** : 거듭 제곱
- / : 나누기
- // : 나누기 연산 후 소수점 이하의 수를 버리고, 정수 부분의 수만 구함
- % : 나누기 연산 후 몫이 아닌 나머지를 구함

n = 1260 -int(input())
count = 0

# 큰 단위의 화폐로부터 차례대로 확인
coin_types = [500,100,50,10]

for i in coin_types: # 화폐의 종류만큼 반복 수행, **for 변수 in 리스트(또는 튜플, 문자열)**
	count += (n//coin_types[i]) # 화폐로 부터 거슬러 줄 수 있는 동전의 개수 세기
	n %= coin_types[i] 

print(count)

🎁 예시1의 시간복잡도

반복문에서 화폐의 종류만큼 반복하기 때문에 화폐의 종류가 K개라고 가정시 : O(K)
거슬러 주어야 할 돈 N은 찾아볼 수 없음
즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류만 영향, 거슬러 줘야 하는 금액과는 무관

🎋 유사문제

백준 5585번: 거스름돈

N = 1000 - int(input())
count = 0

coin_types = [500, 100, 50, 10, 5, 1]

for i in range(6):
    count += (N//coin_types[i])
    N %= coin_types[i]
    
print(count)

📚 그리디 알고리즘의 정당성

모든 알고리즘의 적용 불가
BUT, 거스름돈 문제에서 ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제 접근시 정확한 답을 찾을 수 있다는 보장이 있을시 효과적, 직관적
해법을 찾을 시 해법이 정당한지 검토

거스름돈 문제를 그리드 문제로 해결 가능한 이유 : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

대부분의 그리디 알고리즘 문제에서 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답 도출 가능
만약, 거스름돈 문제이나 동전(화폐)의 단위처럼 서로 배수 형태가 아니라, 무작위시 해결 불가

💡 TIP) 코딩 테스트시 문제 유형 파악

바로 문제 유형 파악 어려울시, 그리디 알고리즘 의심하고, 문제를 해결할 수 있는 탐욕적인 방법이 존재하는지 고민
방법이 없다면, 이후에 공부할 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제 해결 가능한지 고민

📚 실전문제) 큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징

순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 시, M이 8이고, K가 3이라 가정

특정한 인덱스 수가 연속해서 3번까지만 더해 질 수 있으므로, 큰 수의 법칙에 따라 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 됨(연속되지 않게 중간에 5를 넣고 그 다음 다시 6으로 3번 반복)

단, 서로 다른 인덱스에 해당하는 수가 같은 수 일 경우에는, 서로 다른 것으로 간주한다.

순서대로 3, 4, 3, 4, 3으로 이루어진 배열시, M이 7이고, K가 2라고 가정

큰 수의 법칙에 따라, 4+4(인덱스1인 4)+4+4(인덱스3인 4)+4+4(인덱스 1인 4) + 4 = 28

📚 실전문제

참고) \leq 가 $\leq$

❓ 입력조건

첫째 줄 N( $2\leq N \leq 1000)$ , M $(1\leq M \leq 10,000)$ , K $(1\leq K \leq 10,000)$ 의 자연수가 주어지며, 각 자연수는 공백으로 구분
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분, 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다
입력으로 주어지는 K는 항상 M보다 작거나 같다

❓ 출력조건

첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력

👌 문제해결

일단, 입력값 중에서 가장 큰 수와 두번째로 큰 수만 저장하면 됨
연속으로 더할 수 있는 횟수는 최대 K번이므로 ‘가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산’ 반복
단순하게 푸는 예시
참고 ) 파이썬 문법
1. map
  - 리스트의 요소를 지정된 함수로 처리해주는 함수
  - 형태 : map(함수, 리스트)
2. list
  - 형태 : list(리스트)
3. split 함수
  - 입력값을 두 개 이상으로 구분
  - 각각의 값을 리스트로 나눠줌
  - 공백을 알아서 구분해줌

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort() # 입력받은 수들 정렬
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두 번째로 큰 수

result = 0

while True:
	for i in range(k): # 가장 큰 수를 K번 더하기
		if m == 0 # m이 0이라면 반복문 탈출
			break
		result+ = first
		m = -1 # 더할 때마다 1씩 빼기
		if m == 0 # m이 0이라면 반복문 탈출
			break
		result+ = second # 두 번째로 큰 수 **한 번** 더하기
		m = -1 # 더할 때마다 1씩 빼기

  print(result)

📚 심화문제

가정) M의 크기가 100억 이상 ⇒ 위와 같이 풀 시 시간 초과 판정

👌 문제해결

이처럼, 가장 먼저 반복되는 수열에 대해서 파악
- 아이디어 : 만약 N이 5이고 입력 값을 2, 4, 5, 4, 6을 받았다고 가정하면,
- 여기서 가장 큰 수는 6이고, 두 번째로 큰 수는 5다.
- 이때, M = 8, K =3이면 (6+6+6+5)+(6+6+6+5) = 46이 된다.

수열의 길이 : K+1(두번째 큰 수 1개 더함), 반복되는 횟수 : M/(K+1)

이때, K+1이 나누어 떨어지지 않는 경우도 고려 : M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해짐

가장 큰 수가 더해지는 횟수 : 이를 이용하면 가장 큰 수가 더해지는 횟수를 구한 다음, 이를 이용해 두 번째로 큰 수가 더해지는 횟수도 구할 수 있다. : int((M / (K+1) ) * K + M % (K+1) )

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort() # 입력받은 수들 정렬
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두 번째로 큰 수

# 가장 큰 수가 더해지는 **횟수** 계산
count = int((m/(k+1))*k)
count+ = m%(k+1)

result = 0
result+ =(count) * first # 가장 큰 수 더하기
result+ = (m-count)*second # 두 번째로 큰 수 더하기

print(result)

📚 실전문제) 숫자 카드 게임

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임

단, 게임의 룰을 지키며, 카드를 뽑아야 함

게임의 룰
1. 숫자가 쓰인 카드들이 N $*$ M 형태로 놓여 있다. 이 때, N은 행의 개수를 의미, M은 열의 개수를 의미
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택
3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택시, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략

❓ 입력조건

첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. $(1\leq N, M\leq100)$
둘째 줄부터 N개의 줄에 걸쳐, 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이상 10,000이하의 자연수이다.

❓ 출력조건

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자 출력

👌 문제해결

아이디어 : 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수
min() 함수를 이용하는 답안 예시

# N과 M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
	data = list(map(int, input().split()))
	# 현재 줄에서 '가장 작은 수' 찾기
	min_value = min(data)
	# '가장 작은 수'들 중에서 가장 큰 수 찾기
	result = max(result, min_value)

print(result)

2중 반복문 구조를 이용하여 답안 예시

# N과 M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

result = 0

for i in range(n): 
	data = list(map(int, input().split()))
	# 현재 줄에서 '가장 작은 수' 찾기
	min_value = 10001
	for a in data:
		min_value = min(min_value, a)
	# 가장 적은 수 들 중 가장 큰 수 찾기
	result = max(result, min_value)

print(result)

📚 실전문제) 1이 될 때까지

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

N에서 1을 뺀다.
N을 K로 나눈다.

❓ 입력조건

첫째 줄에 N( $2\leq N \leq 100,000)$ 과 K( $2 \leq K \leq 100,000)$ 가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

❓ 출력조건

첫째 줄이 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 구해라

👌 문제해결

아이디어 : 최대한 많이 나누기

예 : N = 25, K =3 일 경우
- 1단계 : N에서 1빼기(나누어 떨어지지 않기 때문에 2번 불가) ⇒ 24
- 2단계 : N에서 K로 나누기 ⇒ 8
- 3단계 : N에서 1빼기 ⇒ 7
- 4단계 : N에서 1빼기 ⇒ 6
- 5단계 : N에서 K나누기 ⇒ 2
- 6단계 : N에서 1빼기 ⇒ 1
단순하게 풀기

n,k = map(int, input().split())
result = 0

# N이 K이상이라면 계속 나누기
while n>=k:
	# N이 K로 나누어 떨어지지 않는다면 N에서 1빼기
while n % k !=0 :
	n-= 1
	result+ =1
# k로 나누기
n//=k
result+=1

print(result)

수가 커질 때

n,k = map(int, input().split())
result = 0

while True:
	#(N==K로 나누어떨어지는 수)가 될 때까지 1씩 빼기
	target = (n//k) * k
	result+ = (n-target)
	n = target
	# N이 K보다 작을때 반복문 탈출
	if n<k:
	 break
	result+=1
	n//=k

#마지막으로 남은 수에 대하여 1씩 빼기
result+=(n-1)
print(result)

GoldenDusk

내 지식을 기록하여, 다른 사람들과 공유하여 함께 발전하는 사람이 되고 싶다. gitbook에도 정리중 ~

다음 포스트

그리디

알고리즘 공부

📚 당장 좋은 것을 선택하는 그리디 알고리즘

📝 코테에서 만나게 될 알고리즘 유형

📝 예시1 거스름돈

🎁 예시1의 시간복잡도

🎋 유사문제

📚 그리디 알고리즘의 정당성

📚 실전문제) 큰 수의 법칙

📚 실전문제

📚 심화문제

📚 실전문제) 숫자 카드 게임

📚 실전문제) 1이 될 때까지

구현

0개의 댓글