[코딩테스트 스터디] 1주차 - 그리디 알고리즘

그리디(Greedy), 탐욕법

현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 기준에 따라 좋은 것을 선택하는 알고리즘
• 문제에서 ‘가장 큰/작은 순서대로’ 등의 기준을 제시
• 주로 정렬 알고리즘과 짝을 이루어 출제
• 문제를 풀 때 먼저 탐욕적인 해결법이 존재하는지 고려
• 최적의 해를 찾기 위한 정당성 검토 필요
• 다익스트라, 크루스칼 알고리즘 등이 속함

---

예제 1 - 거스름돈

• 문제: 거슬러 줘야 할 돈이 N원일 때 필요한 동전의 최소 개수 (거스름돈: 500/100/50/10)
• 풀이: 가장 큰 화폐 단위부터 돈을 거슬러주기
  • 화폐 종류(K개)만큼 반복 수행 ⇒ O(K)
• 비고: 화폐 단위가 작은 단위의 배수일 때 성립 ⇒ 정당성 검토 필요

n = 1260 # 잔돈
count = 0

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

for coin in coin_types:
  count += n // coin # 해당 화폐로 거슬러줄 수 있는 동전 개수
  n %= coin # 남은 거스름돈

print(count)

실전 1 - 큰 수의 법칙

• 문제: 배열(크기=N)에 주어진 수들을 M번 더하여 가장 큰 수를 만들어라
  • 단, 배열의 특정 인덱스에 있는 수가 연속해서 K번까지만 더해질 수 있음 (수는 같아도 인덱스가 다르면 서로 다름)
  • K ≤ M
  • ex) [2,4,5,4,6], M=8, K=3 ⇒ 6+6+6+5+6+6+6+5 = 46
• 풀이 1: 가장 큰 수를 K번, 다음으로 큰 수를 1번, ...(반복)
• 비고: M의 크기가 100억 이상으로 커지면 시간 초과

n, m, k = map(int, input().split())
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):
    if m == 0:
      break
    result += first # 가장 큰 수를 k번 더하기
    m -= 1 # 더해야 할 횟수 1 차감
  if m == 0: # m=0이면 반복문 탈출
    break
  result += second # 두번째로 큰 수를 1번 더하기
  m -= 1 # 더해야 할 횟수 1 차감
  
print(result)

• 풀이 2: 반복되는 수열 파악
  • 수열의 길이: (K+1)
  • 수열의 반복 횟수: M을 (K+1)로 나눈 몫
    • 나누어 떨어지지 않을 때: 그 나머지만큼 가장 큰 수가 더해짐
  • ex) (6+6+6+5) + (6+6+6+5) ⇒ 수열 길이는 K+1 = 3+1 = 4, 수열 반복 횟수는 M//(K+1) = 8//4 = 2
  • 가장 큰 수가 더해지는 횟수(count): int(M/(K+1)) * K + M%(K+1)
  • 두 번째로 큰 수가 더해지는 횟수: M - count

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

실전 2 - 숫자 카드 게임

• 문제: N * M 크기의 카드 중 룰에 맞게 카드를 뽑기
  1. 뽑으려는 카드가 포함된 행 선택
  2. 선택된 행 중 가장 숫자가 낮은 카드를 뽑아야 함
  3. 예) 3 1 2 / 4 1 4 / 2 2 2 ⇒ 3행 선택 ⇒ 2 선택
• 풀이: 각 행마다 가장 작은 수를 찾음 ⇒ 그 중 가장 큰 수
  • 각 행마다 가장 작은 수를 min_value에 저장
  • max 함수로 result와 비교하여 최댓값만 저장
• 비고: 각 숫자는 1 이상 10,000 이하

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)

실전 3 - 1이 될 때까지

• 문제: 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행하려고 한다. 수행해야 하는 최소 횟수는?
  1. N에서 1 빼기
  2. N을 K로 나누기 (나누어 떨어질 때만)
  • 조건: 2 ≤ n ≤ k ≤ 100,000
• 풀이: N이 K로 나누어 떨어질 때까지 1을 빼기(1번) → N을 K로 나누기(2번) → …
• 비고: N이 클 수록 K로 나눴을 때 더 많이 감소 ⇒ K로 최대한 많이 나눌 수 있는 것이 최적의 해를 보장

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

# n이 k 이상이라면 반복 수행
while n >= k:
  # n이 나누어 떨어질 때까지 1을 빼기 (1번)
  while n % k != 0:
    n -= 1
    result += 1
  # n을 k로 나누기(2번)
  n //= k
  result += 1

# n이 k 미만이 되면 n=1이 될 때까지 1을 빼기
while n > 1:
  n -= 1
  result += 1

print(result)

• 풀이 2: 1씩 빼지 않고, N이 K로 나누어 떨어지는 수가 되도록 효율적으로 한번에 빼는 방법

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

while True:
  # n이 k로 나누어 떨어지는 수가 될 때까지 1을 빼기 (1번)
  target = (n // k) * k # (n을 k로 나눈 몫) * k
  result += (n - target)
  n = target
  # n이 k보다 작아지면(나눌 수 없을 때) 반복문 탈출
  if n < k:
    break
  # n을 k로 나누기(2번)
  n //= k
  result += 1

# n이 k 미만이 되면 n=1이 될 때까지 1을 빼기
result += (n - 1)
print(result)

---

실전 문제

#03 문자열 뒤집기

• 문제: 0과 1로 이루어진 문자열 s(≤100만)의 모든 숫자를 같게 만들려면, 연속된 하나 이상의 숫자를 최소 몇 번 뒤집는가?
• 풀이: 연속된 0의 집단과 연속된 1의 집단 중 더 작은 집단의 개수
• 예시: s = 1000101
  • 1의 집단(3개) > 0의 집단(2개) ⇒ 답은 2번
  • count[0]: 0의 집단
  • count[1]: 1의 집단
  • 숫자가 바뀌는 순간 집단의 개수로 하나 체크

import sys
input = lambda : sys.stdin.readline().strip()

# 풀이 1
str = input()
count = [0, 0]

temp = str[0]
count[int(temp)] += 1
for s in str:
    if s == temp:
        continue
    else:
        count[int(s)] += 1
        temp = s

print(min(count))

# 풀이 2 (해설지)
data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

# 첫 번째 원소에 대해서 처리
if data[0] == '1':
    count0 += 1
else:
    count1 += 1

# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i + 1] == '1':
            count0 += 1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

#04 만들 수 없는 금액

• 문제: N개의 동전으로 만들 수 없는 양의 정수 중 최솟값
• 풀이:
  • 확인하려 하는 금액 = target
  • 배열 오름차순 정렬, 작은 화폐부터 순차적으로 추가해가며 확인
  • target만큼 만들 수 있다면 target 값을 증가
  • target만큼 만들 수 없다면 target 값이 정답
  • 핵심: 새로 확인하려는 배열 값이 target보다 크면 target 금액만큼 만들 수 없다!
• 예시: [1,2,3,8]
  1. target = 1로 설정
  2. 1원을 만들 수 있음 (1원이 있으므로) ⇒ target = 1+1 = 2로 설정
  3. 2원을 만들 수 있음 (2원이 있으므로) ⇒ target = 2+2 = 4로 설정 (=1,2,3원까지 모두 가능)
  4. 4원을 만들 수 있음 (3원이 있으므로) ⇒ target = 4+3 = 7로 설정 (=4,5,6원까지 모두 가능)
  5. 7원을 만들 수 없음 (8원이 추가되어도 불가) ⇒ 정답은 7

n = int(input())  # 동전의 개수
coins = list(map(int, input().split()))  # 화폐 리스트
coins.sort()  # 오름차순 정렬

target = 1  # 확인하고 싶은 금액

for coin in coins:
    # 추가된 금액이 target보다 크면 절대 못 만듦, 반복 종료
    if target < coin:
        break
    target += coin  # 새로 추가되는 화폐만큼 더해 target 변경

print(target)

#05 볼링공 고르기

• 문제: 1번부터 N번까지 N개의 볼링공마다 1부터 M까지 무게가 존재할 때, 서로 무게가 다른 볼링공을 고르는 경우의 수는?
• 풀이:
  1. 배열 i번째 원소와 i+1번째 원소가 서로 다르면 경우의 수에 포함
  2. 무게를 오름차순 정렬 ⇒ A 기준으로 1~M인 공을 선택할 경우의 수 = (무게가 1~M인 공의 개수) * (B가 선택하는 경우의 수)
     1. 1부터 10까지 무게를 담는 리스트에 각 무게의 개수를 카운트하여 보관한다.
     2. 1부터 M까지 A가 선택할 수 있는 경우의 수를 더한다.

n, m = map(int, input().split())
data = list(map(int, input().split()))

weight = [0] * 11
result = 0

"""
첫 번째 풀이: 시간 복잡도가 O(n^2)
for i in range(len(data)):
    for j in range(i+1, len(data)):
        if data[i] != data[j]:
            result += 1
"""

for w in data:
    weight[w] += 1

for i in range(len(data)):
    result += weight[i] * sum(weight[i+1:])

"""
답안 예시
for i in range(1, m + 1):
    n -= array[i]
    result += array[i] * n
"""
print(result)

#06 무지의 먹방 라이브

• 문제: 회전판에 먹어야 할 N개의 음식이 있다. 각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다.  K초가 되는 시점에서 먹고 있어야 할 음식 번호는 무엇인가?
  • 1번 음식부터 2, 3, ... , N, 1, 2, ... 순서로 먹는다.
  • 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식(남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식)을 섭취한다.
  • 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
• 풀이: 시간이 적게 걸리는 음식부터 제거 (우선순위 큐 활용)
  • 어차피 제일 적게 걸리는 음식부터 다 먹게 되어있다.
  • 우선순위 큐에 (음식 시간, 음식 번호) 형태로 삽입한다.
  • (남은 음식의 개수) * (n번 음식을 먹는 시간)을 빼준다.
  • 이 때 남은 시간보다 커지면 빼지 않고, 다음으로 먹어야 할 음식의 번호를 출력한다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    
    priority_queue<pair<int, int>> priority_food_times;
    
    
    long long sum = 0;
    long long before = 0;
    
    for(int i= 0; i < food_times.size(); i++){
        sum += food_times[i];
        priority_food_times.push({-food_times[i], i+1});
    }
    
    // 더 이상 먹어야 할 음식이 없는 경우
    if(sum <= k){
        return -1;
    }
    
    while((-priority_food_times.top().first - before) * priority_food_times.size() <= k){
        k -= (-priority_food_times.top().first - before) * priority_food_times.size();
        before = -priority_food_times.top().first;
        priority_food_times.pop();
    }
    
    vector<pair<int, int>> times;
    
    while(!priority_food_times.empty()){
        times.push_back({priority_food_times.top().second, -priority_food_times.top().first});
        priority_food_times.pop();
    }
    
    sort(times.begin(), times.end());
    
    answer = times[k % times.size()].first;
    
    return answer;
}