[이코테] chapter11 그리디 문제

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

 

그리디(greedy) 알고리즘

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

그리디는 최적의 해를 보장할 수 없을 때가 많음
but, 코딩 테스트에서의 대부분의 그리디문제는 탐욕법으로 얻은 해가 최적의 해!

 

정당성 분석 필수!

---

11-1.py 모험가 길드 - ⭐1/3 (❌)

기준도 못잡고, 정당성 분석도 못해서 20분동안 고민하다가 포기한 문제! ㅠㅠ

[교재 풀이]

근데 풀이를 보니까 넘 단순했다..

오름차순으로 공포도 정렬 후 앞에서부터 공포도를 하나씩 확인하며

''현재 그룹에 포함된 모험가의 수"  >=  "현재 확인하고 있는 공포도"

위의 조건을 만족하면 그룹 설정!

문제를 풀다가 'int' object is not subscriptable 에러가 떴다..

이는 "객체가 인덱싱 또는 슬라이싱을 지원하지 않을 때 발생"하는데 내가 실수로 data[i]를 N[i]로 해서 생긴거였다(머쓱)

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

cnt = 0
group = 0

for i in range(N):
    cnt += 1
    if cnt >= data[i]:
        group += 1
        cnt = 0
print(group)

 

 

11-2.py 곱하기 혹은 더하기 - ⭐1/3 (❌18m 38s)

S = list(str(input()))
result = int(S[0])

for i in range(len(S)-1):
    if result == 0:
        result += int(S[i+1])
    else:
        result *= int(S[i+1])

print(result)

처음에는 위처럼 단순하게 '0'이면 더하고, 0이 아니면 곱하는 방법으로 문제를 풀었다.

하지만 몇가지 예외를 찾았다

(예외) '1111' → '4'가 나와야함. but 위의 코드대로라면 1이 나옴.

(예외) '12304' → '36'이 나와야함 but 위의 코드대로라면 10이 나옴.

즉, 1도 고려를 해줘야 한다! 아래는 수정한 코드이다.

S = list(str(input()))
result = int(S[0])

for i in range(len(S)-1):
    if result <= 1 or int(S[i+1]) <= 1:
        result += int(S[i+1])
    else:
        result *= int(S[i+1])

print(result)

 

 

11-3.py 문자열 뒤집기 - ⭐1/3 (⭕11m 51s)

data = input()
cnt = 0
result = 0

for i in range(len(data)-1):
    if data[i] != data[i+1]:
        cnt += 1

if cnt % 2 ==0:
    result = cnt //2
else: result = cnt // 2 + 1

print(result)

교재 풀이보다 간단하게 푼 거 같다!

직접 여러 예제를 만들어서 풀어보니 바뀌는 횟수(cnt)가 짝수면 cnt // 2를, 홀수면 그에 1을 더하면 됐다.

 

 

11-4.py 만들 수 없는 금액 - ⭐1/3 (❌)

이 문제도 11-1처럼 기준도 못잡고, 정당성 분석도 못해서 포기한 문제!

해설을 보니 그리디 알고리즘에 익숙하지 않은 독자라면 문제 해결이 쉽지 않을 수 있다고 경고하고 있다..(내 얘기!)

[교재 풀이]

n = int(input())
coin = list(map(int,input().split()))
coin.sort()
 
target = 1
for i in coin:
  if i > target:
    break
  else:
    print(target, i)
    target+=i
 
print(target)

 

 

11-5.py 볼링공 고르기 - ⭐1/3 (⭕20m 11s)

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

cnt = 0

for i in range(N - 1):
    for j in range(i+1, N):
        if data[i] == data[j]:
            continue
        else:
            cnt += 1
            print(data[i], data[j])
print(cnt)

단순하게 풀고 해설보니까 이중 반복문도 사용안하고 푸는데 신박했다. 생각해보니 나는 M을 사용안하고 풀었다. 최대한 문제에서 입력하는 것들을 다 사용하는 것이 좋을 거 같다.

[교재 풀이]

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

array = [0]*11

for x in data:
    array[x] += 1
print(array)
result = 0
for i in range(1, M + 1):
    N -= array[i]
    result += array[i] * N
print(result)

for x in data:
      array[x] += 1

이 부분 잘 기억해 두자!!

 

 

11-6.py 무지의 먹방라이브 - ⭐1/3 (❌)

[교재 풀이]

import heapq
def solution(food_times, k):
    
    #전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times)<=k:
        return -1
    
    q=[]
    for i in range(len(food_times)):
        #(음식 시간, 음식 번호) 형태로 heapq에 삽입
        heapq.heappush(q, (food_times[i], i+1))
    
    sum_value = 0 #먹기 위해 사용한 시간
    previous = 0 #직전에 다 먹은 음식 시간
    
    length = len(food_times) #남은 음식의 개수
    
    #sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 남은 음식 개수와 k 비교
    #위가 현재 전체 남은 시간(k)보다 커질때까지 반복한다
    while sum_value+((q[0][0]-previous)*length)<=k:
        now=heapq.heappop(q)[0] #현재의 음식 시간
        sum_value += (now-previous)*length 
        length -= 1 #다 먹은 음식 제외
        previous = now #이전 음식 시간 재설정
    
    #남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x:x[1]) #음식의 번호 기준으로 정렬
    return result[(k-sum_value)%length][1] #번호 기준으로, 남은 초수(k-sum_value) 만큼 반복
    answer = -1
    return answer

시간이 적게 걸리는 음식부터 제거해 나가는 방식으로 푼다. 이를 위해 "우선순위 큐"를 사용해 구현한다.

예: [8초, 6초, 4초], k =15 

sum_value = 0 

previous = 0 

q = [(4,3), (6,2), (8,1)]

 

0 + (4-0)*3 = 12 <= 15 

sum_value = 0 + (4-0)*3 =12 

previous = 4 

q = [(6,2), (8,1)]

 

12 + (6-4)*2 = 16 > 15 

q = [(6,2), (8,1)]

 

q = [(8,1), (6,2)]

 

✏️우선순위 큐 - heapq

: 우선순위 큐는 힙(heap) 자료 구조를 통해 구현!

Heap?

완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다.