💻 준성 개발 일지

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 # 백준 1806번 문제 - 부분합 import sys input = sys.stdin.readline n, s = map(int, input().split()) num = list(map(int, input().split())) target, left, right = 0, 0, 0 min_length = 1e9 while True: # print("left: ", lef..

문제 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 # 백준 11722번 문제 - 가장 긴 감소하는 부분수열 n = int(input()) arr = list(map(int, input().split())) dp = [1] * n for i in range(n): for j in range(1, i): if arr[i] < arr[j]: dp[i] = max(dp..

문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 # 백준 2636번 문제 - 치즈 from collections import deque dx, dy = [0,0,-1,1], [1,-1,0,0] n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] def bfs(): visited = [[0]*m for _ in range(n)] q = deq..

문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 # 백준 1744번 문제 - 수 묶기 n = int(input()) minus_list = [] plus_list = [] one_list = [] answer = 0 for i in range(n): num = int(input()) if num 1: plus_list.append(num) else: one_list.append(num) plus_list.sort(reverse=Tr..

문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 # 백준 1202번 문제 - 보석 도둑 import sys, heapq input = sys.stdin.readline n, k = map(int, input().split()) jewelry = [list(map(int, input().split())) for _ in range(n)] bags = [int(input()) ..

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

문제 https://www.acmicpc.net/problem/11660 풀이 # 백준 11660번 문제 - 구간 합 구하기 5 n, m = map(int, input().split()) graph = [] graph = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * (n+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, n+1): dp[i][j] = dp[i-1][j]+ dp[i][j-1] - dp[i-1][j-1] + graph[i-1][j-1] for i in range(m): x1, y1, x2, y2 = map(int, input().split()) result..

우선순위 큐 (Priority Queue) ✔ 우선순위 큐? 큐와 스택이나 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있는 큐이다. 우선순위 큐에서 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다. 우선순위 큐는 힙(Heap)이라는 자료 구조를 통해 구현이 가능하다. 우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다. 하나의 원소를 우선순위를 지정하여 추가하는 함수 (Push) 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 반환하는 함수 (Pop) ✔ 힙(Heap) 이란? 완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야..

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 # 백준 18111번 문제 - 마인크래프트 import sys input = sys.stdin.readline n, m, b = map(int, input().split()) # 세로, 가로, 블록 개수 graph = [] graph.append(list(map(int, input().split())) for _ in range(m)) answer = int(1e9) g_level =..

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 # 백준 11000번 문제 - 강의실 배정 import sys import heapq input = sys.stdin.readline if __name__ == "__main__": n = int(input()) schedule_list = [list(map(int, input().split())) for _ in range(n)] schedule_list.sort() room_queue = list() heapq.heappush(r..