본문 바로가기

알고리즘/🥇 골드

 (72)
백준 1135 뉴스 전하기 파이썬 풀이 난이도 : 골드2 풀이일 : 2403251 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys def dp(n): # 이전에 검사한 적이 있다면 검사 결과 반환 종료 if time[n] > -1: return time[n] # 해당 노드의 자식이 없다면 0 저장 후 0 반환 종료 if not children[n]: time[n] = 0 return 0 # 모든 자식 노드 방문 소..
백준 1202 보석 도둑 파이썬 풀이 난이도 : 골드2 풀이일 : 2403247 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 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 오답 코드 -> 3% 틀렸습니다. import sys, heapq N, K = list(map(int, sys.stdin.readline().split())) jewels = [] bags = [] value = [] for _ in range(N)..
백준 13904 과제 파이썬 풀이 난이도 : 골드3 풀이일 : 2403192 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys, heapq N = int(sys.stdin.readline()) queue = [] # 마감일 우선 과제 정보 정렬 total = [] # 점수 낮은순 정렬 for _ in range(N): limit, score = map(int, sys.stdin.readline().split()) heapq.heappush(queue..
백준 9466 텀 프로젝트 파이썬 풀이 난이도 : 골드3 풀이일 : 2401281 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys from collections import deque # 사이클 확인 def iscycle(n): # 지목된 학생들 team = dict() team[n] = 0 queue = deque([(n, 0)]) check[n] = True while queue: x, idx = queue.p..
백준 1520 내리막 길 파이썬 풀이 난이도 : 골드3 풀이일 : 2403133 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys sys.setrecursionlimit(10**9) def sol(i, j): # 목적지 도착 시 1 반환 if i == N - 1 and j == M - 1: return 1 # 방문한 적이 있다면 dp[i][j] 반환 if dp[i][j] != -1: return dp[i]..
백준 11437 LCA 파이썬 풀이 난이도 : 골드3 풀이일 : 2403122 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 -> 0% 시간초과 import sys from collections import deque def find(n, m): if parent[n] == m: return print(m) temp = deque([n]) while temp: i = temp.popleft() for ni in..
백준 4803 트리 파이썬 풀이 난이도 : 골드4 풀이일 : 2403085 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 문제 이해 처음에 도대체 왜 테스트케이스 1의 트리가 세 개 인가 이해가 안갔는데, 써보고 나이 이해했다. 아무 노드와도 연결되어 있지 않은 노드는 그 자체로 트리 한 개가 된다는 것을 이해한 후 풀이를 시작했다. 풀이 코드 import sys from collections import de..
백준 3584 가장 가까운 공통 조상 파이썬 풀이, 반례 난이도 : 골드4 풀이일 : 2403052 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 import sys from collections import deque def sol(n, m): # n의 자식들의 자식들을 찾아나가며 m 찾기 queue = deque([n]) while queue: x = queue.popleft() f..
백준 5639 이진 검색 트리 파이썬 풀이 난이도 : 골드5 풀이일 : 2403041 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys # 재귀호출 깊이 제한 설정 sys.setrecursionlimit(10 ** 9) # 후위 순회 재귀 함수 def sol(root, end): # 더 이상 탐색할 노드가 없을 때 if root > end: return # 현재 노드 값 저장 temp = nums[r..
백준 7662 이중 우선순위 큐 파이썬 풀이 난이도 : 골드4 풀이일 : 2402283 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이코드 import sys, heapq T = int(sys.stdin.readline()) for _ in range(T): k = int(sys.stdin.readline()) mini, maxi = [], [] visited = [False] * 1000001 for i in range(k): A,..
백준 11780 플로이드 2 파이썬 풀이 난이도 : 골드2 풀이일 : 2402117 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys, heapq def minicost(num): visited = [int(1e9)] * (n + 1) visited[num] = 0 queue = [] heapq.heappush(queue, [0, num, [num]]) # 비용, 다음 목적지, 거쳐간 도시 # 각 도착지까지..
백준 11404 플로이드 파이썬 풀이 난이도 : 골드4 풀이일 : 2402095 https://www.acmicpc.net/problem/11404 11404번: 플로이드첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐풀이 코드import sys, heapq def minicost(num): # visited 숫자는 최대치로 설정 visited = [int(1e9)] * (n + 1) # visited[num]까지의 비용 0 visited[num] = 0 queue = [] heapq.heappush(queue, [0, num]..
백준 12865 평범한 배낭 파이썬 풀이 난이도 : 골드5 풀이일 : 2402073 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 오답 코드 -> 96% 틀렸습니다 import sys N, K = list(map(int, sys.stdin.readline().split())) info = [] for _ in range(N): W, V = list(map(int, sys...
백준 2467 용액 파이썬 풀이 난이도 : 골드5 풀이일 : 2401254 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys N = int(sys.stdin.readline()) liquid = list(map(int, sys.stdin.readline().split())) front = 0 rear = N - 1 numL = liquid[front] numR = liquid[rear] mini ..
백준 1647 도시 분할 계획 파이썬 풀이 난이도 : 골드4 풀이일 : 2401232 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 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys, heapq # 현재 노드의 부모 탐색 def find(n): if parent[n] != n: parent[n] = find(parent[n]) return parent[n] # 두 노드의 부모 연결 def union(n, m): if n ..
백준 2623 음악프로그램 파이썬 풀이 난이도 : 골드3 풀이일 : 2401221 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) # 본인 이전 가수의 수 previousN = [0 for _ in range(N + 1)] # 본인 이후 가수 ..
백준 1766 문제집 파이썬 풀이 난이도 : 골드2 풀이일 : 2401217 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys, heapq N, M = list(map(int, sys.stdin.readline().split())) # 먼저 거쳐야 하는 문제 수 previous = [0 for _ in range(N + 1)] # 다음에 풀 문제 번호 next = [[] f..
백준 1167 트리의 지름 파이썬 풀이 난이도 : 골드2 풀이일 : 2401206 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys from collections import deque def BFS(n): global start visited = [-1 for _ in range(V + 1)] queue = deque([n]) visited[n] = 0 while queue: now = qu..
백준 1504 특정한 최단 거리 파이썬 풀이, 반례 난이도 : 골드4 풀이일 : 2401195 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 풀이 코드 import sys, heapq def djikstra(start, end): visited = [int(1e9) for _ in range(N + 1)] visited[start] = 0 queue = [] heapq.heappush(queue, [0,..
백준 1967 트리의 지름 파이썬 풀이 난이도 : 골드4 풀이일 : 2401184 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐 1차 시도 오답 import sys from collections import deque def BFS(s): global start visited = [0 for _ in range(n + 1)] queue = deque([s]) while queue: now = queue.popleft..

티스토리툴바