👩🏻‍💻 취준하며 공부한 Greedy 유형 총정리 (Python)

그리디

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

Gold 5~ 3 정도의 문제를 풀 정도라면, 왠만한 기업 코테 수준이라고 한다.

 

👇 그리디 문제 특징

→ 똑같은 걸 두번 했을 때 다시 자기로 돌아온다.  
그말은 즉, 한 번 한거는 다시 하지 않는다. 

GREEDY는 사실 유형이 많지 않고, 감으로 맞추는 경우가 많은 유형이다.

 

아래의 12문제(⭐️ 으로 구분), 2가지 알아 둘 것(✏️ 으로 구분) 을 참고하면

왠만한 그리디 문제에 숙련될 것 이라고 생각한다.

 

---

⭐️ 백준 11399 ATM 문제 : 실버 3

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.)

N = int(input())

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

sum_a = 0

a.sort()
# print(a)

# 0,1,2,3,4
for i in range(N+1):
    for j in range(i):
        sum_a += a[j]

print(sum_a)

 

 

⭐️ 백준 5585 거스름돈 문제 : 브론즈 2

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.)

a = int(input())

#  1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
# 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 

cnt = 0
chg = 1000 - a

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

for i in chgList:
    cnt += (chg//i)
    chg = chg - (i*(chg//i))

print(cnt)

 

 

⭐️ 백준 1439 뒤집기 문제 : 실버5

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.)

a = input()

a_1 = '1'
a_0 = '0'

isSame = False

cnt_1 = 0
cnt_0 = 0

for i in range(len(a)):
    if a[i] == a_1:
        isSame = False
    elif(not isSame):
        cnt_1 +=1
        isSame = True
        
isSame = False        

for i in range(len(a)):
    if a[i] == a_0:
        isSame = False
    elif(not isSame):
        cnt_0 +=1
        isSame = True

if(cnt_1 < cnt_0):
    print(cnt_1)
else:
    print(cnt_0)

 

 

⭐️ 백준 2012 등수 매기기: 실버 3

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.)

# Python3 제출 안되고 pypy만 ok
N = int(input())
nList = []
for i in range(N):
    nList.append(int(input()))
    
# 1 5 3 1 2
nList.sort()
# 1 1 2 3 5

sum_N = 0
for i in range(1,N+1):
    sum_N +=(abs(nList[i-1]-i))
    
print(sum_N)

 

 

⭐️ 백준 1092 배 : 골드 5

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 난이도가 있어서 상세 풀이 및 설명도 있습니다.)

• 박스를 무게 기준으로 내림차순 정렬한 다음, 무거운 것부터 옮기도록 한다.
• 시간복잡도 O(NM)에 문제를 해결할 수 있다. (N: 크레인수, M:박스 수)

N = int(input())
cre = sorted(list(map(int,input().split())), reverse=True)

M = int(input())
boxs = sorted(list(map(int,input().split())), reverse=True)

if cre[0] < boxs[0]:
    print(-1)
else:
    count=0
    while boxs:
        count+=1
        for i in cre:
            if not boxsb :
                break
            else:
                for j in range(len(boxs)):
                    if boxs[j] <= i:
                        boxs.pop(j)
                        break
    print(count)

 

 

⭐️ 백준 2212 센서 : 골드 5

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 난이도가 있어서 상세 풀이 및 설명도 있습니다.)

정렬된 센서를 최대 K개의 영역으로 나누는 것으로 문제를 해결할 수 있다.

따라서  문제의 알고리즘은

1. 각 센서 오름차순 정렬 

2. 각 센서 사이 거리 계산

3. 가장 거리 먼 순서대로 K-1개 연결고리 제거

 

sensor  = int(input())
tower = int(input())

sensorList = list(map(int, input().split()))
sensorList.sort()

if(tower>=sensor):
    print(0)
else:
    distList = []
    for i in range(1,sensor):
        distList.append(sensorList[i]-sensorList[i-1])
    distList.sort()
    
    for j in range(tower-1):
        distList.pop()
    
    print(sum(distList))

 

 

✏️ import heapq

(👇 아래 더보기 클릭 시, 자세한 개념 설명이 나옵니다. 꼭 알아두면 좋습니다.)

트리를 활용한 자료구조

힙은 최대/최소값 검색을 위한 구조 최대값과 최소값을 찾으면O(log n)중 하나로 이해하면 됨

 

depth (트리의 높이) 를 h라고 표기한다면,
n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 **h = log_2{n}**에 가까우므로, 시간 복잡도는 **O(log{n})**

- 참고: 빅오 표기법에서 log{n} 에서의 log의 밑은 10이 아니라, 2입니다.
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미.
	50%의 실행시간을 단축시킬 수 있다는 것을 의미함

✏️ heapq.heapify(힙리스트) : 리스트 자체를 heap 자료구조로 만듬

import heapq

jj = [10,11,9,8,15,16,8,3,1,2]

heapq.heapify(jj)

print(jj)
lenj = len(jj)

for i in range(lenj):
    print(heapq.heappop(jj))

 

✏️ heapq.heappush(힙리스트,data) :힙리스트에 데이터 삽입 / heapq.heappop(힙리스트) : 힙리스트 root pop

import heapq

jj = []

heapq.heappush(jj,4)
heapq.heappush(jj,10)
heapq.heappush(jj,11)
heapq.heappush(jj,2)
heapq.heappush(jj,1)

print(jj)
print("------------")
print(heapq.heappop(jj))
print(heapq.heappop(jj))
print(heapq.heappop(jj))
print(heapq.heappop(jj))
print(heapq.heappop(jj))

ref.

[파이썬] heapq 모듈 사용법

 

 

⭐️ 백준 1461 도서관: 골드 5 (heapq)

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 난이도가 있어서 상세 풀이 및 설명도 있습니다.)

• 음수범위 책과, 양수 범위 책을 나누어 생각
• 두개의 우선순위 큐를 사용하여 해결가능.
• 마지막 책은 다시 0으로 돌아올 필요 없으므로,가장 먼 책이 마지막이 되어야 함.
• 왕복거리 - (가장 먼 책의 편도 거리)

python 코드 작성 시 → 기본적으로 minHeap 이기 때문에, 최대 힙을 구현하기 위해서 모든 값에 - 를 붙인다.

import heapq

N,M = map(int, input().split()) # N,M <=50

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

minusList = []
plustList = []

# 가장 거리가 먼 책 까지 거리(음수 값과 양수 값 중 하나니까...oh..)
largest = max(max(bookList), -min(bookList))

# 최대 힙을 위해 원소를 음수로 수정
for i in bookList:
    if (i>0):
        heapq.heappush(plustList,-i)
    else:
        heapq.heappush(minusList,i)
        
result = 0

while plustList:
    # 한번에 m 개씩 옮길 수 있으므로, m 개씩 빼내기
    result += heapq.heappop(plustList)
    for _ in range(M-1):
        if plustList:
            heapq.heappop(plustList)
            
while minusList:
    # 한번에 m 개씩 옮길 수 있으므로, m 개씩 빼내기
    result += heapq.heappop(minusList)
    for _ in range(M-1):
        if minusList:
            heapq.heappop(minusList)
        
print(-result*2-largest)

 

 

⭐️ 백준 1781 컵라면 : 골드 2 (heapq)

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 난이도가 있어서 상세 풀이 및 설명도 있습니다.)

• 각 문제 '컵라면 수'를 우선순위 큐에 넣고, 데드라인을 초과하면 최소 원소를 제거

import heapq

N = int(input())
listN = []
q =[]

for _ in range(N):
    listN.append(list(map(int,input().split())))
    
listN.sort()

for i in listN:
    a = i[0]
    heapq.heappush(q,i[1])
    
    # 데드라인을 초과하는 경우 최소 원소를 제거
    if a<len(q):
        heapq.heappop(q)
        
print(sum(q))

 

 

⭐️ 프로그래머스 Greedy - 체육복 

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.)

• 여러 풀이방법이 있습니다.

# set 을 활용한 풀이
def solution(n,lost,reserve):
		# set으로 만드는 데, O(배열의 길이)
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
		# sorted  에서 O(klogk)
    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x+1 in l:
            l.remove(x+1)
    return n-len(1)

 

# O(n)
def solution(n,lost,reserve):
    u = [1]*(n+2)
    for i in reserve:
        u[i] +=1
    for i in lost:
        u[i]-=1
    for i in range(1,n+1):
        if u[i-1] == 0 and u[i]==2:
            u[i-1:i+1] =[1,1]
        elif u[i]==1 and u[i+1]==0:
            u[i:i+1] = [1.1]
    return len([x for x in u[1:-1] if x > 0])

 

def solution(n, lost, reserve):
    
    answer = 0
    
    for i in range(1,n+1):
        if i in lost:
            if i in reserve:
                answer+=1
                reserve.remove(i)
            elif i-1 in reserve and i-1 not in lost:
                answer+=1
                reserve.remove(i-1)
            elif (i+1 in reserve and i+1 not in lost):
                answer +=1
                reserve.remove(i+1)
            else:
                pass
        else:
            answer+=1
    
    return answer

 

 

✏️ set

(👇 아래 더보기 클릭 시, 자세한 개념 설명이 나옵니다. 꼭 알아두면 좋습니다.)

set 은 HashTable 로 구현이 되어있기 때문에 key 를 접근하는 시간이 상수시간에 접근 가능.

 

딕셔너리와 다른 점은 value는 없고,

어떤 원소가 이 집합 안에 속해 있는지 없는지만 상관하는 자료구조이다.

( 참고: 딕셔너리는, key 와 value가 mapping 되있음)

 

temp_list =[1,2,3,4,5]
temp_st = set(temp_list)

이때 set() 변환 함수는, O(List의 크기)의 복잡도를 가진다.(선형적이라고 보면 됨.)

 

 

⭐️ 프로그래머스 Greedy -큰수 만들기

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 난이도가 있어서 상세 풀이 및 설명도 있습니다.)

 아래 사진을 참고 하여, 큰수를 만드는 방법은

작은 걸 빼는데, 앞에서 부터 작은걸 뺀다.

 즉, 큰 수가 앞자리에 그리고 작은수가 뒷자리에 놓이면 된다.

풀이를 설명하면 

1. 주어진 숫자로 부터 숫자를 하나씩 모은다.

2. 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 다 빼낸다.

3. 아직 뺄 개수를 채우지 못했으면 맨 끝에서 빼야 한다.

 

 

def solution(number_str, k):
    collected = [] # 하나씩 숫자 모아서 큰 수만드려고 
    # 문자열로도 모을 수는 있겠지만, 문자열은 python에서 immutable한 특징을 가진다.. 그래서 List에 모으는게 좋다~
    for i,num in enumerate(number_str):
           # enumerate를 사용해서 i 에 인덱스를, num 에 해당 값을 담게 했다.
           # 두번째 조건이 첫번째보다 앞에 있으면 안되는 부분을 고려. 
        while(len(collected)>0 and collected[-1]<num and k>0):
            collected.pop()
            k-=1
            if k ==0:
                collected += list(number_str[i:])
                break
        collected.append(num)
        
    collected = collected[:-k] if k>0 else collected
    answer = ''.join(collected)          
               
    return answer

 

 

⭐️ 백준 16676 근우의 다이어리 꾸미기

(👇 아래 더보기 클릭 시, 바로 풀이 답 나옵니다. 쉬운 문제라 별도 설명 없습니다.)

n  = input()
s = ('1'*len(n))

int_n = int(n)
int_s = int(s)

if(len(n) ==1):
    print(1)
elif(int_n >= int_s):
    print(len(n))
else:
    print(len(n)-1)

 

 

⭐️ 백준 2437 저울

(👇 아이디어 설명만 나옵니다. 풀이는 따로 없지만, 아이디어가 중요한 문제입니다.)

🤔Idea 가 너무너무 중요하다.

추의 무게를 담고 있는 리스트를 정렬 한 후, 하나씩 더해가는데, 그 하나씩 더하는 수를 다음 추의 무게와 비교를 한다.

이때, 다음 추가 여태 더했던 추들의 합보다 크면 해당 값은 주어진 N개의 추들로 만들 수 없다...

 

 

 

 

ref. 참고 한번 할 것

+[Python] 순열, 조합, 중복순열, 중복조합(itertools를 활용한 구현)