IT-garden

문제

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.

어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.

그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

입력

첫 번째 줄에 자연수 N이 주어진다.(N ≤ 1,000,000)

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍
수학

정답

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

n=int(input())
m=[0]*1000001
m[1]=1
m[2]=2

for i in range(3,n+1):
    m[i]=(m[i-2] + m[i-1]) % 15746

print(m[n])

사용할 수 있는 타일 종류 : '1'과 '00'입니다.

N = 1 이면 1
N = 2 이면 11 00
N = 3 이면 111 100 001
N = 4 이면 1111 1100 1001 0011 0000
N = 5 이면 11111 00111 10011 11001 11100 10000 00001 00100
N = 6 이면 111111 001111 100111 110011 111001 111100 110000 100100 001001 001100 000011 100001 000000

N = 1 이면 1개, N = 2 이면 2개, N = 3 이면 3개, N = 4 이면 5개, N = 5 이면 8개, N = 6 이면 13개

즉, 피보나치 수열의 규칙을 따릅니다.

F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2)

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

문제

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

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