![]()
https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 해석 이 문제는 다익스트라 문제로 맥세권과 스세권을 만족하는 집중 가장 최단거리를 가진 집을 구하는 문제이다. 이때 맥도날드와 스타벅스의 위치에는 집이 존재하지 않고, 한 정점에 맥도날드와 스타벅스가 동시에 존재할 수 있다. 코드 import heapq input = __import__('sys').stdin.readline # Input..
![]()
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 분석 분류 그래프 이론, 다익스트라 문제 설명 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 ..
https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net 문제분석 수열을 입력받고 이를 비 내림차순으로 정렬해서 수열을 만든다. 그런 다음 정수를 두 개 입력받는다. 수열에서 입력받은 정수 인덱스에 해당하는 값들의 누적 합을 구해서 출력하면 된다. 코드 from itertools import accumulate input = __import__('sys').stdin.readline n, q = map(int, input().split()) a = sorted([*map(int, input().split())]) p_sum = list(accu..
![]()
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해석 이 문제는 바이러스인 2가 상하좌우로 퍼지는데 이를 벽 3개를 생성하여 가장 많은 안전 영역의 크기를 구하는 문제이다. 코드 from collections import deque input = __import__('sys').stdin.readline # Input n, m = map(int, input().split()) arr = [] makeWall = [] for _ in range(n): ..
https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제분석 분류 DP, 그래프, 트리, bfs-dfs, 트리에서의 DP 문제 설명 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는..
https://velog.io/@jay6768/BOJ-Python-1874-스택-수열 Intro 스택을 만들어서 수를 저장하고, 그 스택에서 수를 뽑아내어 주어진 오름차순 수열을 만드는 문제이다. 못 만들면 "NO"를 출력한다. 처음에 문제를 이해하는데 시간이 정말 오래 걸렸다. 스택을 이용해 수열을 만든다는 게 무슨 뜻인지, push와 pop 연산을 언제 수행해야 하는지 한참 고민한 끝에 답을 찾았다. Solution 문제에서 1부터 n까지의 수를 스택에 넣는다고 했다. 그러므로 반복문을 돌며 스택에 수를 1씩 추가한다. 또한 주어진 수열과 같은 수열을 만들어야 하므로, 주어진 수열의 0번째 수와 만들어놓은 스택의 마지막 수를 비교하며 연산을 선택한다. 이때 한 번이라도 주어진 수열의 0번째 수가 스택..
![]()
https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해석 최소 힙, 최대 힙 과 비슷한 문제로 힙을 사용하는 문제이다. 입력으로 정수를 입력받고, 이를 배열에 넣는다. 만약 입력된 수가 0이라면 배열에서 가장 작은 절대값을 가진 수를 출력한다. 만약 배열에 수가 존재하지 않으면 0을 출력한다. 코드 import heapq input = __import__('sys').stdin.readline n = int(input()..
https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제분석 정수를 입력 받고 이를 배열에 저장받은 다음 0을 입력 받았을 때, 배열에서 절댓값이 가장 작은 값을 pop 하면 되는 문제이다. 단, 0을 입력받았을 때, 배열에 아무것도 없을 경우에는 그냥 0을 출력해야 한다. 입력 되는 정수는 절댓값이 2^31보다 보다 작으며 N은 1보다 크고 100000보다 작은 자연수이다. 또한, 절댓값이 같은 경우 더 작은 값을 출력한다...
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 문제 분석 분류 자료 구조(data_structures), 덱(deque) 문제 설명 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N..
https://www.acmicpc.net/problem/2535 2535번: 아시아 정보올림피아드 첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사 www.acmicpc.net 문제분석 나라별 최대 메달 수가 두 개라는 점에 유의해야한다. 정렬을 한 뒤에 앞서 말한 조건에 유의하여 메달을 부여해야 풀 수 있는 문제이다. 정렬은 점수 순으로 정렬을 하고 먼저 2개의 메달을 메달을 부여한 뒤에 한 나라에 2개 이상의 메달이 부여되었는지를 확인한 뒤에 나머지 1개의 메달을 수여하여야 문제를 제대로 풀 수 있다 코드 input = __import__('s..
![]()
https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 문제 해석 간단히 수첩 2에 적혀 놓은 정수가 수첩 1에 적혀 있는지 찾는 문제이다. 코드 input = __import__('sys').stdin.readline t = int(input()) for k in range(t): n = int(input()) arr = list(map(int, input().split())) m = int(input()) isIn = list(map(int, input..
https://velog.io/@jay6768/BOJ-Python-2805-나무-자르기 백준 2805번 나무 자르기 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net Intro 기본적인 이분 탐색 문제. 목재절단기의 적합한 높이를 이분 탐색으로 범위를 좁혀가며 찾아야 한다. Solution 찾고자 하는 높이가 될 숫자를 임의로 정한다. 반복할 때마다 범위를 줄여가며 숫자를 다시 정한다. (mid) 해당 높이로 나무를 모두 자른다. 땅 밑으로 나무를 자를 수는 없다. (h)..
