2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 1. 트리 초기화하기 ➔ setTree(idx) 트리 크기(treeSize) = 2^(K+1) ..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 시작점 X 모든 노드간에 최단 경로 탐색 시간복잡도 O(V³) 안좋음 ➡️ 노드의 개수 100~200까지 사용 가능 문제 유형 시작점이 없고 모든 도시간의 최단거리, 모든 도시 100개 이하 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 원리 리스트를 선언하고 초기화하기 최단 거리 리스트에 그래프 데이터 저장하기 점화식으로 리스트 업데이트하기 더보기 [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 ..

1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 분석 최단 경로를 표현하는 리스트를 k개의 row를 갖는 2차원 리스트의 형태로 변경 기존 다익스트라 로직에서, k번째 노드를 찾기 위해서는 노드를 여러번 사용하기 때문에 visited 로직 삭제 다익스트라 로직 수정 코드 1. 최단 거리 리스트를 1차원이 아닌 k개의 row를 갖는 2차원 리스트로 선언 distance = array = [[INF] * k for _ in range(n+1)] q = [(..

다익스트라 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 기출 : 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 우선순위 큐 파이썬 우선순위 큐, 힙 우선순위 큐(Priority Queue) 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나 karla.tistory.com 풀이 (PriorityQueue) import sys from queue import Priori..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 항상 유일한 값으로 정렬되지 않음 ex) 롤 아이템, 수강신청 풀이 from collections import deque """ 위상정렬 : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 모든 건물을 짓는데 걸리는 최소 시간 여러 개의 건물을 동시에 지을 수 있음 N개의 건물을 지을 때 각 건물을 짓기 위해 필요한 최소 시간 출력 건물의 종류 수 n(1~500) 각 건물을 짓..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 분석 1 ≤ M ≤ N ≤ 1,000,000 이므로 일반적인 소수 구하기 방식으로 풀면 시간 초과 발생 ➔ 에라토스테네스 채 N의 제곱근까지만 탐색하는 이유 N의 제곱근이 n일 때 N=a*b를 만족하는 a b 전부 다 n보다 클 수 없음 N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가짐 에라토스테네스의 체로 n이하의 수의 배수를 모두 제거하면 1부터 N사이의 소수를 구할 수 있음 N=16, n=4 a, b= (1,16),(2,8),(4,4)(8,2),(16,1) N보다 작..