IT-garden

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            ab, c= heapq.heappop(h)
            print(c)
        else:
            print(0)
    else:
        heapq.heappush(h, (abs(i),i))

heapq에 값을 (abs(i), i)로 저장합니다.

abs(i)를 통해 절대값이 작은 것부터 heapq에 넣어서 절대값이 작은 것이 앞에 올 수 있게 합니다.

i는 그대로 넣어서 절대값이 같더라도 i가 작은 것이 앞에 올 수 있게 합니다.

백준 알고리즘 11286번 : www.acmicpc.net/problem/11286

문제

널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            print(-heapq.heappop(h))
        else:
            print(0)
    else:
        heapq.heappush(h, -i)

최소힙과 반대로 -를 넣고 출력합니다.

백준 알고리즘 11279번 : www.acmicpc.net/problem/11279

문제

널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력과 출력

알고리즘 분류

힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[int(input()) for i in range(n)]

h=[]

for i in a:
    if i == 0:
        if h:
            print(heapq.heappop(h))
        else:
            print(0)
    else:
        heapq.heappush(h, i)

백준 알고리즘 1927번 : www.acmicpc.net/problem/1927

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘
힙

정답

import heapq
import sys
input = lambda : sys.stdin.readline().strip()

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

a=[]

for i in range(n):
    m,v=map(int,input().split())
    heapq.heappush(a, [m,v])

b=[int(input()) for i in range(k)]
b.sort()

c=0
p=[]

for i in range(k):
    capa=b[i] # 현재 가방에 담을 수 있는 무게

    while a and capa >= a[0][0]: # 가방에 담을 수 있는 a에 있는 모든 보석
        [m,v]=heapq.heappop(a) 
        heapq.heappush(p, -v) # 값을 -로 넣기, 최대힙 만들기 

    if p: # 넣을 수 있는 보석이 있는 경우
        c -= heapq.heappop(p)
    elif not a: # 가방에 넣을 수 있는 보석이 없는 경우
        break

print(c)

heapq이용 : heapq는 이진 트리의 최소힙 자료구조 제공합니다.

**백준에서 import queue가 안되서 PriorityQueue를 사용하면 런타임 에러가 납니다.

1. 각 보석의 정보 m과 v를 heapq에 담습니다. 이진 트리는 m이 작은 것부터 최소힙으로 구성됩니다.
2. 가방에 담을 수 있는 최대 무게들을 입력받아 오름차순으로 정렬합니다.
3. 각 가방에 대해 담을 수 있는 보석을 검사하기 위한 for문을 실행합니다.
4. heapq a가 있고 a에 있는 최소 무게(a[0][0])보다 가방(capa)이 더 큰 경우 while문을 수행합니다.
4-1. heapq a에서 가장 작은 값을 받아 heapq p에 -v를 넣습니다. (최대힙으로 만드는 것)
4-2. heapq a에서 하나씩 빼서 while 조건을 만족시키면 계속 while문을 실행합니다.
5. 가방에 들어갈 수 있는 보석이 담긴 heapq p가 있다면 heapq p의 가장 작은 값을 출력해 c에 더합니다.(최종으로 가방에 넣는 것)
(heapq p에 넣을 때 가방의 가치를 -로 넣었기 때문에 가장 가치가 큰 값이 -로 나옵니다.
그래서 c에서 빼줍니다.)
6. 가방의 개수만큼 for문을 반복하여 보석의 최대 가격을 구합니다.

백준 알고리즘 1202번 : https://www.acmicpc.net/problem/1202

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제 입력과 출력

알고리즘 분류

이분 탐색 

정답

n=int(input())
k=int(input())
 
low=1
high=k

while low <= high:
    mid = (low + high)//2
    count = 0
    for i in range (1, n+1):
        count = count + min(mid//i, n)
 
    if count < k:
        low = mid + 1
    else:
        high = mid - 1
print(low)

백준 알고리즘 1300번 : https://www.acmicpc.net/problem/1300

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

예제 입력과 출력

알고리즘 분류

덱

정답

import sys
input = lambda : sys.stdin.readline().strip()

t=int(input())

for i in range(t):
    p=input()
    n=int(input())
    de=input()[1:-1].split(',')
    p=p.replace('RR','') 
   
    r=0
    f,b=0,0
    
    for j in p:
        if j == 'R':
            r += 1
        elif j == 'D':
            if r % 2 == 0:
                f += 1
            else:
                b += 1

    if f + b <= n:
        de=de[f:n-b]

        if r % 2 == 1:
            print('['+','.join(de[::-1])+']')
        else:
            print('['+','.join(de)+']')
    else:
        print('error')

1. p, n, de를 입력받습니다.
2. p에서는 R이 연속으로 2번 나오면 두번 뒤집는 것인데 두번 뒤집는 것은 원래대로와 같기 때문에 ''으로 제거합니다.
3. de에서는 '['와 ']'를 제거하기 위해 slice를 이용하고 split으로 ','을 기준으로 자릅니다.
4. r은 R의 개수, f는 앞에서부터 버려야 하는 요소의 개수, b는 뒤에서부터 버려야 하는 요소의 개수입니다.
5. r이 홀수이면 뒤에서부터 빼야 하기 때문에 b에 1을 더하고 r이 짝수이면 앞에서부터 빼야 하기 때문에 f에 1을 더합니다.
6. f와 b의 개수에 따라 de에서 자르고 r이 홀수이면 뒤집어서 출력하고 짝수이면 그대로 출력합니다.

백준 알고리즘 5430번 : https://www.acmicpc.net/problem/5430