[자료구조] 그리디

 

🚩 그리디 

---

 

| 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘 

 

| 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는 알고리즘 

 

 

🐾 그리디 알고리즘 문제는 주로 정렬 알고리즘과 짝을 이루어 출제된다. 

 

 

🐾 기초 파이썬 연산자 기억하기 

 

• /  :  나누기
• % : 나머지
• //  : 몫
• ** : 거듭제곱

 

 

| 그리디 알고리즘이 모든 알고리즘 문제에 적용 가능한 것은 아니다. 그리디 알고리즘은 '최적의 해' 를 찾을 수 없을 가능성이 높지만, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있다면 매우 효과적이고 직관적으로 적용할 수 있는 방법이다. 

 

| 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 생각하고, 그의 정당성을 검토해야 답을 도출할 수 있다. 

 

 

 

 

1️⃣ 실전 유형 문제 : 큰 수의 법칙 

---

 

| KEY IDEA : 입력값 중 가장 큰 수와 두 번째로 큰 수만 저장하여 제한된 K 번 반복수 만큼 가장 큰 수를 더해나가고, K 번을 채우면 두 번째 큰 수를 더한 다음 가장 큰 수를 더해가는 과정을 반복해 나아간다. 

 

 

| 문제에서 활용될 변수 생성하기 

 

n, m, k = map(int, input().split()) 
# n : 데이터 개수 
# m : 더할 숫자 개수 
# k : 반복 제한 개수 

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

data.sort() # 입력받은 데이터 정렬 
first = data[n-1]  # 첫번째로 큰 수 
second = data[n-2] # 두번째로 큰 수 

result = 0 # 더한 결과를 담을 변수

 

 

| 구현 

 

while True : 

  # 🚩 가장 큰 수를 K 번 더하기
  for i in range(k) : 

    if m == 0 : 
      break # 더하기 횟수가 다 끝나면 반복문을 종료하게 된다. 
    
    result += first 
    m -= 1 # 횟수 1씩 감소 시키기 

  # k번 만큼 다 돌고 난 후, 

  if m == 0 : 
    break  # 더하기 횟수가 다 끝나면 반복문을 종료하게 된다.  
  
  # 🚩 두 번째로 큰 수를 한번 더하기 
  result += second 
  m -=1 # 횟수 1씩 감소 시키기 


print(result)

 

5 8 3
2 4 5 4 6
46

 

 

| M : 더해지는 횟수가 100억 이상 커진다면 

 

• 가장 큰 수와 두번째로 큰 수의 등장 구조가 반복되는 수열이라는 특징을 이용해,  '가장 큰 수가 더해지는 횟수' 를 미리 계산하고 지정하여 while 문으로 인한 연산 증가를 줄일 수 있다. 

 

• 가령 M=8 이고 K=2 이며, 가장 큰 수가 6이고 두 번째로 큰 수가 5일때

 

(6+6+5) + (6+6+5) + (6+6) 

 

덧셈구조가 2번 반복되고 남은 더하기 횟수만큼 가장 큰 수가 더해진다. 이때 가장 큰 수인 6은 총 6번 더해졌다. 이를 m,k 로 수식화하면 다음과 같다.

 

int(m/(k+1))*k + m%(k+1)

 

n, m, k = map(int, input().split()) 
# n : 데이터 개수 
# m : 더할 숫자 개수 
# k : 반복 제한 개수 

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️⃣ 실전 유형 문제 : 숫자 카드 게임

---

 

| KEY IDEA : 2차원 행렬에서, 각 행에서 가장 작은 수를 찾고 그 중에서 가장 큰수를 찾으면 된다. 

 

 

🐾 2차원 행렬 초기화 예시 (참고) 

 

 

 

| min() 함수를 사용하는 예시 

 

 

n,m = map(int, input().split()) # n : 행, m : 열

result = []

for i in range(n) : # 행의 개수만큼 반복 

  # 각 행을 입력받아
  data = map(int, input().split()) 

  # 각 행에서 가장 작은 수 찾기 
  result.append(min(data))



print(max(result)) # 각 행에서 뽑은 작은 수들 중 가장 큰 수 찾기

 

 

 

 

 

3️⃣ 실전 유형 문제 : 1이 될때 까지 최소 횟수 

---

 

| KEY IDEA :  횟수의 최소값 → 최대한 많이 나누기 ⭐  

 

(1) N 이 K 의 배수가 될 때까지 1 빼기 

(2) N 을 K 로 나누기 

 

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

while n>=k : # n 이 k 이상이라면 계속 나누기 

  # 나누어 떨어지지 않는다면 나누어 떨어질 때까지 1을 빼기 
  while n%k !=0 : 
    n-=1 
    count+=1 
  
  # k 로 나누기 
  n //= k 
  count += 1 


# 마지막으로 남은 수에 대해 1씩 빼기 
while n>1 : 
  n-=1 
  count += 1 

print(count)