Jinho Tech

기본적인 그리디 알고리즘 문제이다. 

for _ in range(int(input())):
    j, N = map(int, input().split())
    li = []
    for i in range(N):
        r, c = map(int, input().split())
        li.append(r*c)
    li.sort(reverse=True)
    cnt = 0
    while j > 0:
        j -= li[cnt]
        cnt += 1
    print(cnt)

기본적인 우선순위 큐 문제이다.

import heapq

n, m = map(int, input().split())
q = list(map(int, input().split()))
heapq.heapify(q)
for _ in range(m):
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    heapq.heappush(q, a+b)
    heapq.heappush(q, a+b)
print(sum(q))

단순 문자열 문제이다. 1은 앞에서부터, 0은 뒤에서부터 지워주면 된다.

li = list(input())
zero, one = li.count('0')//2, li.count('1')//2
for _ in range(zero):
    li.pop(-li[::-1].index('0')-1)
for _ in range(one):
    li.pop(li.index('1'))
print(''.join(li))

그리디 알고리즘 & BFS 문제이다.

from collections import deque

def bfs(A, B):
    cnt = 1
    queue = deque()
    queue.append((A, cnt))
    while queue:
        node, cnt = queue.popleft()
        if node == B:
            return cnt
        if node*2 <= B:
            queue.append((node*2, cnt+1))
        if int(str(node)+'1') <= B:
            queue.append((int(str(node)+'1'), cnt+1))
    return -1

A, B = map(int, input().split())
print(bfs(A, B))

그리디 알고리즘 & 덱 문제이다.

덱의 맨 처음 값보다 t가 크다면 덱의 맨 뒤에 t를 추가, 그렇지 않다면 덱의 맨 앞에 t를 추가해주면 된다. 

from collections import deque

for _ in range(int(input())):
    N = int(input())
    li = deque(input().split())
    queue = deque(li.popleft())
    while li:
        t = li.popleft()
        if t > queue[0]:
            queue.append(t)
        else:
            queue.appendleft(t)
    print(''.join(queue))

그리디 알고리즘 & 스택 문제이다. 스택을 활용하지 않으면 시간 초과가 나온다. 

제일 큰 수로 만들려면 앞에 있는 작은 수부터 없애버려야 한다는 점이 핵심인 것 같다.

N, K = map(int, input().split())
li = list(input())
k, stack = K, []
for i in range(N):
    while k > 0 and stack and stack[-1] < li[i]:
        stack.pop()
        k -= 1
    stack.append(li[i])
print(''.join(stack[:N-K]))

그리디 알고리즘 문제이다. max(B-A, C-B)-1가 핵심이다. 

while 1:
    try:
        A, B, C = map(int, input().split())
        print(max(B-A, C-B)-1)
    except:
        break

그리디 알고리즘 문제이다. Python3로 제출하니 시간 초과가 나와서 PyPy3로 제출했다.

N = int(input())
li = list(map(int, input().split()))
res = []
for i in range(N-1):
    cnt = 0
    for j in range(i+1, N):
        if li[i] > li[j]:
            cnt += 1
        else:
            break
    res.append(cnt)
print(max(res))

그리디 알고리즘 문제이다. 박스 용량의 합에 박스에 들어간 책 크기의 합을 빼주면 된다 -> sum(box) - in_box

N, M = map(int, input().split())
box = list(map(int, input().split()))
book = list(map(int, input().split()))
i = j = t = in_box = 0
while i < N and j < M:
    if box[i] < t+book[j]:
        t = 0
        i += 1
    else:
        in_box += book[j]
        t += book[j]
        j += 1
print(sum(box)-in_box)    

그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

정렬을 사용하면 쉽게 풀 수 있는 그리드 알고리즘 문제들이 되게 많다.

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/62

jinho-study.tistory.com/111

jinho-study.tistory.com/198

jinho-study.tistory.com/195

jinho-study.tistory.com/301

jinho-study.tistory.com/39

jinho-study.tistory.com/75

jinho-study.tistory.com/36

jinho-study.tistory.com/302

jinho-study.tistory.com/303

jinho-study.tistory.com/304

jinho-study.tistory.com/305

jinho-study.tistory.com/306

https://jinho-study.tistory.com/1101