💻💭🎧🌏

문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 코드 import sys input = sys.stdin.readline def find_parent(x): if parent[x] == x: return x P = find_parent(parent[x]) parent[x] = P return parent[x] def union(x, y): x = find_parent(x) y = find_parent(y)..

문제 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 코드 import heapq import sys input = sys.stdin.readline array = [] for _ in range(n): deadline, ramen = map(int, input().split()) array.append((deadline, ramen)) array.sort() queue = [] for i in array: heapq.heappush(queue,i[1]..

문제 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 코드 import sys input = sys.stdin.readline n = int(input()) array= list(map(int, input.split())) array.sort() target = 1 for i in array: if target < i: break target += i print(target) 풀이 target 이라는 변수에 오름차순으로 정렬한 저울추들을 차례대로 더한다...

문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 코드 import sys n = int(sys.stdin.readline()) alpha = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ') num = [0]*26 #알파벳에 숫자를 할당했는지 여부 check = [0]*10 #숫자를 사용했는지 여부 array = [] #알파벳 문자열을 담음 for i in range(n): array.append(list(sys.stdi..

문제 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 코드 import sys n = int(sys.stdin.readline()) #크레인 수 limit = [[0 for i in range(2)] for j in range(n)] #각 크레인의 무게 제한을 0열에, 각 크레인이 이동시킨 박스의 수를 1열에 넣는 배열 array = list(map(int, sys.stdin.readline().split())) #크레인의 무게..

문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 코드 import sys import heapq n = int(sys.stdin.readline()) heap = [] for i in range(n): heapq.heappush(heap,int(sys.stdin.readline())) total = 0 if n!=1: while len(heap)!=0: a = heapq.heappop(heap) b = heapq.heappo..

문제 https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 코드 import sys N = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) one = min(array) two = 100 # 50 * 2 = 두 면의 최대 합 three = 150 # 50 * 3 = 세 면의 최대 합 if N == 1: # N==1이라면 총 주사위 숫자..

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 코드 import sys import heapq n = int(sys.stdin.readline()) array = [] for i in range(n): array.append(list(map(int, sys.stdin.readline().split()))) array.sort() room = [] heapq.heappush(room,array[0][1]) for i in range(1,n): if array[i][0] < room[0]..

우선순위 큐란? 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용함. 구현 하는 방법 1) 단순히 리스트를 이용하여 구현 2) 힙(heap)을 이용하여 구현 우선 순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이 경우 시간 복잡도는 O(NlogN) 힙(Heap)의 특징 힙은 완전 이진 트리 자료구조의 일종이다. 힙에서는 항상 루트 노드(root node)를 제거한다. 최소 힙(min heap) 루트 노드가 가장 작은 값을 가진다 따라서 값이 작은 데이터가 우선적으로 제거된다. 최대 힙(max he..

큐에 일정한 비율(20%)로 난수를 생성하여 큐에 입력하고, 일정한 비율(10%)로 큐에서 정수를 꺼내는 프로그램을 작성해보자. 생산자가 소비자보다 빠르므로 큐가 포화 상태가 될 가능성이 높아진다. 1. time() 함수를 사용하기 위해서는 time.h 파일을 포함해야함. 2. rand() % 5 == 0 -> 20/100 = 1/5 => 20%의 확률 rand() % 10 == 0 -> 10/100 = 1/10 => 10%의 확률 #include #include #include //=====원형큐 코드 시작===== #define MAX_QUEUE_SIZE 5 typedef int element; typedef struct { // 큐 타입 element data[MAX_QUEUE_SIZE]; int ..