Total

[2042번] 구간합 구하기 (세그먼트 트리, 리프노드, 값 변경)

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) ..

[11438번] 최소 공통 조상 구하기 (트리, 제곱수 LCA, LCA 시간초과)

11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 분석 최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과) 최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식 karla.tistory.com 풀이 """ 두 노드 쌍 M개 LCA 구하기 노드의 개수 N(2~100,000) N-1줄 트리상 연결된 두 노드 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 ..

최소 공통 조상 빠르게 구하기 (트리, 제곱수 LCA, LCA 시간초과)

최소 공통 조상 빠르게 구하기 서로 깊이를 맞춰주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2ᵏ씩 올라가 비교하는 방식 기존에 자신의 부모 노드만 저장해 놓던 방식에서 2ᵏ번째 위치의 부모 노드까지 저장해 둬야함 원리 1. 부모 노드 저장 리스트 만들기 부모 노드 리스트 정의 : P[K][N] = N번 노드의 2ᵏ 번째 부모의 노드 번호 내 바로 위에 있는 부모 노드뿐만 아니라, 내 자리에서 2ᵏ 칸 위에 있는 부모가 누군지 저장해놔야함 부모 노드 리스트의 점화식 : P[K][N] = P[K-1][P[k-1][N]] 예시) K = 2 N=12 가정 P[2][12] = P[1][P[1][12]] P[2][12] : 12번 노드의 2²번째 부모 = 1 P[1][12] = 12번 노드의..

세그먼트 트리, 인덱스 트리, 구간합

1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 모든 값을 update 해야함 ➔ 느림 데이터의 업데이트가 빈번하게 일어나게 되면 합배열 성능 측면에서 안좋음 ➔ 속도유지를 위해 세그먼트 트리 사용 2. 원리 1) 트리 초기화 하기 ⓪ 샘플데이터 {5, 8, 4, 3, 7, 2, 1, 6} ① 리스트 길이 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듬 2ᵏ≥ N을 만족하는 𝑘의 최솟값을 구한 후 2ᵏ * 2 N=8이므로 2³ ≥ 8 ➔ 2³ * 2 = 16 ② 시작 노드 : 2ᵏ ➔ 2³ = 8 ③ 리프 노드에 원본 ..

트리 (구성 요소, 이진 트리, 세그먼트 트리, 인덱스 트리, 최소공통 조상 LCA)

➊ 특징 노드와 에지로 연결된 그래프의 특수한 형태 그래프의 표현으로도 트리를 표현할 수 있음 순환구조 X, 1개의 루트노드 루트노드를 제외한 노드는 1개의 부모노드를 가짐 트리의 부분 트리 역시 토리의 모든 특징을 따름 그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트) 간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리 karla.tistory.com ➋ 트리의 구성요소 구성요소 설명 노드 데이터의 index와 value를 표현하는 요소 에지 노드와 노드의 연결 관계를 나타내는 선 루트 노드 트리에서 가장 상위에 존재하는 노드 부모 노..

그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트)

간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리즘 벨만-포드 MST 크루스칼 플로이드-워셜 다익스트라 간선 리스트 Edge list 에지 중심으로 그래프를 표현 리스트에 출발 노드, 도착 노드, 가중치 저장하여 가중치가 있는 에지 표현 벨만-포드, 최소 신장 트리 크루스칼 알고리즘 # 벨만 포드 graph = [] for i in range(m): u, v, w = map(int, input().split()) graph.append((u, v, w)) # 크루스칼 from queue import PriorityQueue q = PriorityQue..

[1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드)

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음 N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 더보기 크루스칼 알고리즘 간선 위주의 알고리즘 시작점을 따로 정하지 않고 최소 비용의 간선..

[11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드)

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번 노드를 거쳐 가는 경우를 고려하여 ..

그래프 최단거리 알고리즘 정리 및 비교 (다익스트라, 벨만-포드, 플로이드-워셜)

다익스트라 벨만-포드 플로이드-워셜 시작 노드 (시작점) O O X (모든 노드) 음수 간선 X O O 시간 복잡도 O(ElogV) O(EV) O(V³) 1. 다익스트라 출발 노드와 모든 노드 간의 최단 거리 탐색 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 시간복잡도 : O(ElogV) 문제 유형 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 더보기 2023.03.15 - [Algorithm/그래프] - [1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙) 2023.03.15 - [Algorithm..

[11657번] 타임머신 (그래프, 최단거리, 벨만 포드 알고리즘)

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만 포드 최단 거리를 구하는 알고리즘 음수간선 OK 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 O(VE) 기출 음수사이클이 있는 지 체크하는 문제 → 시간여행, 과거, 웜홀 음수간선, 시작점이 있고 최단거리 구하는 문제 과정 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 모든 에지를 확인해 정답 리스트 업데이트 음수 사이클 유무 확인 : 모든 에지를 한 번씩 다시 사용해 업데..