Algorithm&Data Structure
-
BFS를 이용하여 DAG그래프 인지 판별Algorithm&Data Structure 2023. 6. 11. 16:18
정의 DAG : ( Directed Acyclic Graph) 비순환 그래프 구조 (Ex : Tree) BFS : ( Breadh-First Search) 넓이 우선 탐색 (비순환 그래프에서 Level를 찾을때 주로 사용) Indegree : 부모 노드로 부터 들어오는 간선 개수 Algorithm 각 노드의 indegree를 구한다. indegree가 0 인 노드를 queue에 push한다 해당 노드는 root노드가 된다 BFS로 각 노드를 순회 하면서 방문되 노드의 indegree를 차감 시키고, indegree가 0일때 queue에 push후 카운트를 증가 시킨다. 노드의 순회가 끝난후 카운트의 수가 노드의 수와 같으면 DAG그래 프다
-
Sparse TableAlgorithm&Data Structure 2018. 11. 10. 13:17
Sparse Table Range Qeury를 구할 때 쓰는 자료구조 Range Qeury란 에를 들어 4 6 1 5 7 3 이라는 수열 이 있을때 구간 2 ~ 4 까지 최소 값이 무엇 이냐? 라는 쿼리에 대한 답을 리턴 하는 문제다 Range Qeury를 구하는 방법은 여러 가지가 있다 알고리즘 공간 복잡도 시간 복잡도 Brute Force O(1) O(N) Dynamic Programming O(n^2) O(1) Segment Tree O(N) O(logN) Sparse Table O(NlogN) O(1) 위 표에서 복 수 있듯이 input data가 변하지 않고 쿼리가 빈번하게 일어나는 일나는 상황에서 쓰이는 자료구조이다 Sparse Table을 구하는 방법 주어진 데이터를 Preprocessing..