본문 바로가기

백준

 (25)
[크루스칼] 백준 1647번 '도시 분할 계획' (Python) https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. 모든 노드를 포함하면서 사이클이 존재하지 않고, 최소비용으로 신장트리를 만들어야 하므로 크루스칼 알고리즘 적용 2. 비용순으로 간선 정렬 3. 사이클이 발생하지 않는 경우에만 집합 합치기 4. 최소 신장트리를 구성하는 간선 중에서 가장 비용이 큰 간선 제거 def find_parent(parent, x): if parent[x]!=x: parent[x] ..
[동적계획법] 백준 14501번 '퇴사' (Python) https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 리스트 뒤에서부터 거꾸로 확인 #이취코 답 n = int(input()) t = [] p = [] dp = [0] * (n+1) max_value = 0 for i in range(n): a,b = map(int,input().split()) t.append(a) p.append(b) for i in range(n-1, -1, -1): time = t[i]+i if time
[이분탐색] 백준 2110번 '공유기 설치' (Python) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 처음 최소 거리는 항상 1, 최대 거리는 max-min 2. mid 거리만큼 차례대로 공유기를 설치함. (집이 1,4,8,9이고, mid가 4일 때, 1,8에 공유기 설치 가능) 3. 2개밖에 설치 못하므로 거리-1, 그 반대면 +1 #이취코 답 n,c = list(map(int,input().split())) array = [] for _..
[정렬] 백준 1715번 '카드 정렬하기' (Python) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 항상 가장 작은 크기의 두 카드 묶음을 합치는 알고리즘 계산 2. heapq 사용 3. 결과 값은 두 개 더한 값을 다 더한 값 #이취코 답 import heapq n = int(input()) heap = [] for i in range(n): data = int(input()) heapq.heappush(heap, data) result = 0 while len(heap) ..
[BFS/DFS] 백준 16234번 '인구 이동' (Python) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 0. 해당 나라를 q에 추가하고 union = 연합번호로 변경. 0. 현재 연합 인구수랑 연합 국가 수 변수도 추가 0. q가 빌 때까지 상하좌우 나라 확인. 옆의 나라와 인구차이가 조건에 맞으면 연합에 추가 0. q가 다 끝나면 연합 국가끼리 인구 분배 1. visited 처럼 해당 나라가 아직 처리되지 않았다면(union==-1) process 함수 적용.. 후 연합 번호 증가 ..
[BFS/DFS] 백준 14888번 '연산자 끼워넣기' (Python) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 1. 연산을 할 함수를 만든다. 2. 입력값 수만큼 각 연산으로 바꾸고 조합을 만든다. 3. 1번에서 만든 함수를 반복하여 최댓값, 최솟값을 찾는다. #220328 from itertools import permutations def op(a,b,opp): if opp=='+': return a+b elif opp=='-': return a-..
[BFS] 백준 18405번 '경쟁적 전염' (Python) https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 1. 차례대로 바이러스를 퍼트려야 하므로 deque 사용 2. 바이러스 종류, 시간(s), x, y 값을 q에 담음 3. q가 있을 때, 시간이 지날 때까지 반복 4. q 순서대로 상하좌우 바이러스 증식 #220328 실패 n,k = map(int,input().split()) graph = [] for i in range(n): graph.append(list(ma..
[BFS] 백준 14502번 '연구소' (Python) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 가벽 3개를 세울 수 있는 모든 조합을 구한다. 2. 조합 순서대로 가벽을 세우고 바이러스가 퍼진 후의 안전영역을 구한다. 3. 안전영역을 비교하여 제일 큰 안전영역을 구한다. #220328 n,m = map(int,input().split()) graph = [] zero = [] for i in range(n): graph.append(list(map(int,input().split()))) for ..
LIST

티스토리툴바