PS/백준

[백준 알고리즘][파이썬/Python] 11279번: 최대 힙

문제 시간 제한 : 1 초 (추가 시간 없음), 메모리 제한 : 256 MB 널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 1. 배열에 자연수 x를 넣는다. 2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다. 출력 입력에서 0이 주어진 ..

[백준 알고리즘][파이썬/Python] 11866번: 요세푸스 문제 0

문제 시간 제한 : 2 초, 메모리 제한 : 512 MB 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 입출력 예 ..

[백준 알고리즘][파이썬/Python] 7568번: 덩치

문제 시간 제한 : 1 초, 메모리 제한 : 128 MB 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55,173)이라면 몸무게는 D가 C보다 더 무겁고, 키는..

[백준 알고리즘][파이썬/Python] 11723번: 집합

문제 시간 제한 : 1.5 초, 메모리 제한 : 4 MB 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1, 2, ..., 20} 으로 바꾼다. empty: S를 공집합으로 바꾼다. 입력 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이..

[백준 알고리즘][파이썬/Python] 1748번: 수 이어 쓰기 1

문제 시간 제한 : 1초, 메모리 제한 : 128 MB 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 1234567891011121314151617181920212223... 이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. 출력 첫째 줄에 새로운 수의 자릿수를 출력한다. 입출력 예 제출 코드 n = int(input()) lst = [9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999] max = 0 len = 0 for idx, val in enumerate(lst): if n < val: max +=..

[백준 알고리즘][파이썬/Python] 1764번: 듣보잡

문제 시간 제한 : 2초, 메모리 제한 : 256 MB 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 입출력 예 제출 코드 import sys n, m = map(int, input().split()) n_lst = set([sys.stdin.r..

[백준 알고리즘][파이썬/Python] 1057번: 토너먼트

문제 시간 제한 : 1초, 메모리 제한 : 128 MB 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를..

[백준 알고리즘][파이썬/Python] 1500번: 최대 곱

문제 시간 제한 : 2초, 메모리 제한 : 128 MB 세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러 개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다. 만약 S=10, K=3이면, 3,3,4는 곱이 36으로 최대이다. 입력 첫째 줄에 두 수 S와 K가 주어진다. K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다. 출력 첫째 줄에 정답을 출력한다. 답은 9223372036854775807보다 작다. 입출력 예 제출 코드 s, k = map(int, input().split()) key = s // k if s % k == 0: print(pow(key, k)) else: result = 1 while..