🧚‍♂️알고리즘🧚‍♂️ - 그리디 - 그리디

⭐️탐욕 알고리즘(Greedy Algorithm)⭐️

 

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

 

여러 경우 중 하나를 선택해야 할 때마다 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달

(그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없음

-하지만 대체로 그리디 문제들은 최적이 됨)

 

 

그리디 알고리즘 수행 방법
1) 해 선택 (현재 상황에서의 최선해 선택)
2) 적절성 검사 ( 현재 선택된 해가 문제의 제약 조건에 맞는지 검사)
3) 해 검사 ( 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사/아니라면 1로)

---

1 - 백준 11047번 - 실버3

11047번: 동전 0

- 그리디로 풀 수 있음 (이유- 작은 수가 그 다음 큰 수의 배수임- 큰 수를 선택하는 것이 무조건 유리)

from sys import stdin
N, K = map(int, stdin.readline().split())
Nlist =[]
result = 0

for _ in range(N):
    nn = int(stdin.readline())
    Nlist.append(nn)
Nlist.reverse()

for cha in Nlist:
    if (K == 0):
        break
    else:
        result += int( K / cha)
        K = K % cha

print(result)

+ reverse 말고  for(N-1,-1,-1) 가 더 좋았을듯

---

2 - 백준 1715번 - 골드4

1715번: 카드 정렬하기

 

- '먼저 선택된 카드 묶음'의 크기가 작아야 함

1) 카드 개수가 가장 적은 묶음 2개 선택해서 합침
2) 합친 묶음을 전체 카드 묶음에 넣음
3) 카드 묶음이 1개가 될 때까지 1.2 반복

 

"우선순위 큐"를 이용해야 함- 시간복잡도

데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조

우선순위 큐 사용하기 (Python)

from sys import stdin
from queue import PriorityQueue # 큐
N = int(stdin.readline())
qp = PriorityQueue() #큐 생성
result = 0
for _ in range(N):
    nn = int(stdin.readline())
    qp.put(nn) # put()

card1 = 0
card2 = 0
while(qp.qsize() > 1):
    card1 = qp.get() # get()
    card2 = qp.get()
    sum = card1 + card2
    result += sum
    qp.put(sum)

print(result)

---

3 - 백준 1744번 - 골드4

1744번: 수 묶기

- 가능한 한 큰 수끼리 묶어야 결과값이 커짐

1) 1보다 큰 수 / 0 / 1 / 음수  - 네 묶음으로 나눔
2) '1보다 큰 수' 집합을 큰 수 순서로 정렬하여 차례대로 곱해 더함
3) '음수' 집합을 작은 순대로 정렬해 차례대로 곱해 더함 (절댓값이 큰 순) / 원소 수가 홀수일 때 0이 있다면 둘이 곱함
4) 2.3 과정의 값, 1집합 값을 더해 출력
(1을 안 더한 이유 - 곱하는 것보다 1 더하는 것이 더 큼)

 

마찬가지로 우선순위 큐 이용

- 1보다 큰 수' 집합은 큰 수 순서로 정렬해야 하므로 -1을 곱한 값을 넣기 ( 작은수(이러면 사실은 큰 수)가 나오니까)

from sys import stdin
from queue import PriorityQueue # 큐
N = int(stdin.readline())
plusQ = PriorityQueue() #큐 생성
minQ = PriorityQueue()
one = 0
zero = 0

for _ in range(N):
    nn = int(stdin.readline())

    if (nn > 1):
        plusQ.put(nn*-1) # put()
    elif(nn == 1):
        one += 1
    elif(nn == 0):
        zero += 1
    else:
        minQ.put(nn)

result = 0
while( plusQ.qsize() > 1 ):
    num1 = plusQ.get() # get()
    num2 = plusQ.get()
    multi = num1 * num2
    result += multi

if ( plusQ.qsize() == 1 ):
    result += (plusQ.get() * -1) # 다시 -1 곱하는 거 잊지 말

while( minQ.qsize() > 1 ):
    num1 = minQ.get() # get()
    num2 = minQ.get()
    multi = num1 * num2
    result += multi

if ( minQ.qsize() == 1  and zero == 0):
    result += minQ.get()

result += one
print(result)

---

4 - 백준 1931번 - 실버 1

1931번: 회의실 배정

- 종료 시간이 빠른 대로 정리해야 함 (더 많은 회의에 유리)

- 종료 시간보다 그 다음 요소의 시작 시간이 같거나 느리면 종료시간 갱신 및 결과값 +1

from sys import stdin
T = int(stdin.readline())
Nlist = [[0]*2 for _ in range(T)]
for i in range(T):
    A, B = map( int,stdin.readline().split())
    Nlist[i][0] = B
    Nlist[i][1] = A
Nlist.sort()

end = -1
result = 0

for i in range(T):
    if end <= Nlist[i][1]:
        end = Nlist[i][0]
        result += 1

print(result)

---

5 - 백준 1541번 - 실버 2

1541번: 잃어버린 괄호

- 큰 수를 만들어 음수로 만들면 됨 -> 더하기로 연결된 부분들을 다 괄호치기

- "-"를 기준으로 나누어서 묶음들 계산!

from sys import stdin
NList = list(map(str, stdin.readline().split("-"))) #"-"로 나누기

def funcfunc(pluslist): 
    rere= pluslist.split("+") # + 기준 나누기
    result = 0
    for cha in rere:
        result += int(cha)
    return result

for i in range(len(NList)):
    if i == 0:
        result = funcfunc(NList[i])
    else:
        result -= funcfunc(NList[i])

print(result)

split()의 혁명.. 자료형주의!

[python] 파이썬 split 함수 정리 및 에제 (문자열 쪼개기)

리스트로 나옴~

---

+

단계별 풀기 진행하다가 생긴 의문에 대한 답변

그렇군! 함수를 이렇게 시간복잡도를 줄이는데 이용할 수 있군