본문 바로가기

BOJ 알고리즘 (패캠)/정렬, 탐색

 (17)
1766번: 문제집 (힙, 위상정렬) - Fastcampus www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net import sys import heapq # 문제 푸는 순서 결정하기 => 위상정렬 (진입차수가 0인 정점을 큐에 추가) def search(N, indgree): res = [] qu = [] for i in range(1, N+1): if indgree[i] == 0: heapq.heappush(qu, i) while qu: node = heapq.heappop(qu) res..
1715번: 카드 정렬하기 (힙) - Fastcampus www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장�� www.acmicpc.net import heapq import sys # 최소값 2개 더하기 => 힙 이용 def search(a): res = 0 heapq.heapify(a) while len(a) >= 2: s = heapq.heappop(a) + heapq.heappop(a) res += s heapq.heappush(a, s) return res N = int(input()) moneys = [int(sys.s..
1927번: 최소 힙 (힙) - Fastcampus www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net import sys import heapq # 최소값 순서로 출력 => 힙 이용 def search(a): res = [] qu = [] for x in a: if x > 0: heapq.heappush(qu, x) else: if qu: res.append(heapq.heappop(qu)) else: res.append(0) return res N = int(input()) nums = [in..
2250번: 트리의 높이와 너비 (트리, 재귀) - Fastcampus www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. �� www.acmicpc.net # 각 레벨의 너비 중 최대값 def in_order(parent, row=1): lc, rc = graph[parent] if lc != -1: in_order(lc, row + 1) global col, maxRow col += 1 minCol[row] = min(minCol[row], col) maxCol[row] = max(maxCol[row], col) maxRow = max(m..
1991번: 트리 순회 (트리, 재귀) - Fastcampus www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net # 전위 순회 (parent, 왼쪽, 오른쪽) def pre_order(parent): lc, rc = graph[parent] global visited visited += parent if lc != ".": pre_order(lc) if rc != ".": pre_order(rc) # 중위 순회 (왼쪽, parent, 오른쪽) def in_order(parent): lc, rc = graph[pare..
1939번: 중량제한 (탐색, 이분탐색, BFS) - Fastcampus www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net import sys from collections import deque # 이동가능한 물품중량 (mid) => 이분탐색 def search(N, SP, EP, start, end): res = 0 while start = weight: qu.append(e) return False N, M = map(int, input().split()) graph = [[] ..
2110번: 공유기 설치 (탐색, 이분탐색) - Fastcampus www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net O(NLogX) = 20만*30 = 600만 import sys # 공유기 사이의 거리 (mid) => 이분탐색 def search(houses, C): res = 0 start, end = 1, houses[-1] - houses[0] while start 2개 def device_cnt(h, d): pos, cnt = 0, 1 for i in range..
1236번: 성 지키기 (탐색) - Fastcampus www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net # 필요한 경비원의 수 # - 모든 행과 열에 경비원이 있어야 한다 # - 경비원이 없는 행의 개수, 경비원이 없는 열의 개수 중 큰값 def search(N, M, MP): g_row = [0] * N g_col = [0] * M for i in range(N): for j in range(M): if MP[i][j] == "X": g_row[i] = 1 g_col[j] = 1 need_g_row ..

티스토리툴바