백준

우선순위큐일반적인 큐(Queue)는 선입 선출의 구조(FIFO, First In First Out)를 가지고 있다.하지만, 우선순위큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 의미한다.   우선순위 큐는,1. 모든 항목에 우선순위가 있다.2. 높은 우선순위를 가진 요소는 낮은 우선순위를 가진 요소보다 먼저 제거된다.3. 두 요소의 우선순위가 같으면 큐의 순서에 따라 제거된다.   우선순위큐는 최소 두 가지 연산을 가지고 있다.하나의 원소를 우선순위를 지정하여 추가하는 함수 push우선순위가 가장 높은 원소를 큐에서 제거하고 반환하는 함수 pop  우선순위큐는 힙(heap)이라는 자료 구조를 이용해 구현한다힙(heap)이란, 완전 이진트리로 부모 노드..

문제 설명- LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제- ex) ACAYKP와 CAPCAK의 LCS는 ACAK입력값1. 문자열12. 문자열2- 알파벳 대문자로만 이루어져 있으며 최대 1000글자 - 예제ACAYKPCAPCAK출력값- 두 문자열의 LCS 길이 - 예제 답 : 4   문제 풀이첫번째 시도 같은 패턴의 길이 중 가장 긴 길이를 출력하라는 줄 알고 잘못 풀었다..!# 단순히 패턴이 겹치는 것 중 긴 패턴을 찾으라는 줄 알고 잘못 품..!text = input()pattern = input()# 최장 길이 countmax_cnt = 0cnt = 0N = len(text)M..

문제 설명필요하다고 생각하는 N개의 물건각 물건은 무게 W와 가치 V최대 K만큼의 무게를 들 수 있다제한시간 2초입력값N K (1N개의 줄에 거쳐 W V (1- 예제4 76 134 83 65 12 출력값배낭에 넣을 수 있는 물건들의 가치합의 최댓값- 예제 답 : 14  일반적으로 dfs로 푸는 방법을 생각할 수 있으나, 제한시간이 2초이고 N이 100개까지 있으므로 시간초과가 나기 쉽다 def dfs(n,sum_w, sum_v) : global max_v # 종료조건 if sum_w > K : if sum_v > max_v : max_v = sum_v return if n == N : if sum_v > max_v : ..

문제설명- 비어있는 공집합 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를 공집합으로 바꾼다.입력값1. 수행해야 하는 연산의 수 M2. M개줄에 걸쳐 수행해야하는 연산이 한 줄에 하나씩 주어진다출력값check 연산이 주어질 때..

문제 설명- 자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 프로그램- A,B,C는 2,147,483,647 이하의 자연수  보기엔 단순해보이지만, 시간 제한이 타이트하고 자연수의 크기가 커서 시간초과가 나기 딱 쉬운 그런 문제 1. ** 연산자 사용import sysinput = sys.stdin.readlineA,B,C = map(int,input().split())ans = A**B%Cprint(ans) ** 연산자- x ** y 형태로 사용- 가장 짧고 간단한 방법으로 거듭제곱을 수행할 수 있음- ** 연산자는 내장 연산자이기 때문에 별도의 import 없이 사용 가능 특징** 의 반환값은 파라미터의 type에 따라 결정됨속도 측면에서 ** 연산자가 일반적으로 더 빠르다. 결과역시 시간초과..