[Algorithm] 그리디 (Greedy)

bee·2023년 4월 1일
0

Algorithm

목록 보기
3/8
post-thumbnail

그리디 (Greedy)

개념

: 단순 무식하게, 탐욕적으로(현재 상황에서 지금 당장 좋은 것만 고르는 방법) 문제를 푸는 알고리즘


📌 Tip

  • 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.
  • 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 '가장 큰 순서대로', '가장 짧은 순서대로'와 같은 기준을 제시해준다.
  • 정렬 알고리즘과 자주 짝을 이뤄 출제된다.





[기본 예제] 거스름돈

마트 카운터에는 거스름돈으로 사용 가능한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원 일때, 거슬러 줘야 할 동전의 최소 개수를 구하는 프로그램을 작성하시오.


💡 풀이 아이디어
가장 큰 화폐 단위부터 돈을 거슬러준다.

N = int(input()
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types :
	count += (N // coin)
    N %= coin
    
print(count)

1260

6


✓ 이 문제는 화폐의 종류만큼 반복을 수행하므로, 화폐의 종류가 KK개라 할때, 시간 복잡도는 O(K)O(K)가 된다. 즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류 K에 대해서만 영향을 받고, 거슬러 주어야 할 금액 N의 크기와는 무관하다.






실습

실습문제 1. 큰 수의 법칙

학생 A의 큰 수의 법칙은 '다양한 수로 이루어진 크기가 N인 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙'이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속으로 K번을 초과하여 더해질 수 없다. 또한 서로 다른 인덱스에 해당하는 수가 같은 경우 서로 다른 것으로 간주한다. 학생 A의 큰수에 법칙에 따른 결과를 출력하는 프로그램을 작성하시오.

## 내 풀이
n, m, k = map(int, input().split())
n_list = list(map(int, input().split()))

a = m//k # max(n_list)가 K번 더해진 덩어리의 최대 개수
b = m%k # n_list에서 두번쨰로 큰 숫자를 위의 덩어리 사이사이에 배치해야하는 개수

n_list_sorted = sorted(n_list)
n_list_sorted_set = set(n_list_sorted) # 두번째로 큰 수를 골라야하는데, 받은 리스트는 중복을 허용하므로 집합으로 중복 제거 수행
n_set_to_list = list(n_list_sorted_set) # 집합에서 인덱스 접근하려면 다시 리스트나 튜플로 변환해야함

res = (max(n_list)*k)*a + (n_set_to_list[-2]*b)

print(res)

5 8 3
2 4 5 4 6
46


답은 맞는데, 사실 중복을 제거할 필요가 없었다. 문제를 다시 읽어보면, "서로 다른 인덱스에 해당하는 수가 같은 경우 서로 다른 것으로 간주한다."라고 써져있다. 즉, 중복되는 수가 있어도 정렬만 되어있다면 해결 가능한 문제였다.



다시 풀어봄

## 내 풀이 (2)
n, m, k = map(int, input().split()) # n: n_list 원소 개수, m: 더하기 횟수, k: 같은수 연속 더하기 횟수
n_list = list(map(int, input().split()))
answer = 0

n_list = sorted(n_list, reverse = True) # 내림차순 정렬

while m > 0:
    for i in range(k): # 반복문 시작할때마다 k는 복구되어야하므로 while말고 for문 사용
        answer += n_list[0]
        m -= 1
    
    answer += n_list[1]
    m -= 1

print(answer)

5 8 3
2 4 5 4 6
46




💡 풀이 아이디어
반복되는 수열에 대해서 파악하기
여기서 반복되는 수열은 가장 큰수와 두 번째로 큰 수가 묶음으로 반복되는 것이다. 반복되는 수열의 길이는 (k+1)이 된다.
수열이 반복되는 횟수는 m % (k+1)이 된다.
m(k+1)로 나누어 떨어지지 않는 경우에는 m % (k+1)만큼 가장 큰 수가 추가로 더해진다.
즉, 가장 큰 수가 더해지는 횟수는 int(m/(k+1)) * k + m % (k+1)이다.

## 모범답안
n, m, k = map(int, input().split())
n_list = list(map(int, input().split()))

n_list.sort()
first = data[-1] # 가장 큰 수
second = data[-2] # 두 번째로 큰 수

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

result = (first * cnt) + (m - cnt)*second

print(result)

5 8 3
2 4 5 4 6
46






실전문제 2. 숫자 카드 게임

N x M으로 놓인 카드들 중에서 아래 게임 규칙에 맞게 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 프로그램을 작성하시오.
1. 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. 먼저 뽑고자 하는 카드가 포함되어있는 행을 선택한다.
2. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다.


💡풀이 아이디어
각 행에서 가장 숫자가 낮은 카드를 모아 별도의 리스트에 담은 다음, 그 리스트의 최대값을 출력하게 만들었다.

## 내 풀이
n, m = map(int, input().split())
card = [map(int, input().split()) for _ in range(n)]

lowest = []

for i in range(n):
    card_n = sorted(card[i])
    lowest.append(card_n[0])
    
print(max(lowest))

2 4
7 3 1 8
3 3 3 4

3




## 모범답안 (1) - min() 함수 사용
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 4
7 3 1 8
3 3 3 4

3



## 모범답안 (2) - 2중 반복문 사용
n, m = map(int, input().split())

result = 0 

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

print(result)

2 4
7 3 1 8
3 3 3 4

3






실전문제 3. 1이 될 때까지

어떤 수 N이 1이 될 때까지 아래의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 연산 횟수를 구하는 프로그램을 작성하시오.
1. N에서 1을 뺀다.
2. N을 K로 나눈다. (N이 K로 나누어떨어질 때만 사용 가능)


💡 풀이 아이디어
최대한 k로 나눌 수 있을 때 까지 나누고 -1 연산 수행하기

## 내 풀이
n, k = map(int, input().split())
cnt = 0

while n > 1 :
    if n % k == 0:
        n //= k
        cnt += 1
        
    else:
        n -= 1
        cnt += 1

print(cnt)

25 5

2




## 모범답안 (1)
n, k = map(int, input().split())
cnt = 0

# n이 k이상이라면 최대한 k로 계속 나누기
while n >= k:
	# n이 k로 나누어 떨어지지 않을 경우 먼저 1 빼기
	if n % k != 0:
    	n -= 1
        cnt += 1
        
    n //= k
    cnt += 1

# 마지막으로 남은 수에 대해 1 빼기
while n > 1:
	n -= 1
    cnt += 1
    
print(cnt)


## 모범답안 (2)
n, k = map(int, input().split())
cnt = 0

while True:
	# n이 k로 나누어 떨어지는 수가 될 때 까지 1씩 빼기
	target = (n//k) * k
    cnt += (n-target)
    n = target
    
    # n을 더이상 k로 나눌 수 없을 때 : 반복문 탈출
    if n < k :
    	break
        
    # k로 나누기
    cnt += 1
    n //= k
    
# 마지막으로 남은 수에 대해 1씩 빼기
cnt += (n-1)

print(cnt)

사실 모범답안(2)는 온전히 이해하지 못했다. 왜 target이라는 변수를 따로 두어 작업을 추가했는지 모르겠다.(혹시 아시는 분은 댓글 남겨주세요..😭)







🔗 References

이것이 취업을 위한 코딩 테스트다 with 파이썬

profile
벌집처럼 밀도있게 차곡차곡 쌓아나가는중

0개의 댓글