언제 사용하는가? 최소 공통 조상 알고리즘은 트리에서 두 노드의 최단거리를 찾고 싶을때 사용한다. 시간복잡도는 O(logN)이며, 희소배열을 이해한다면 최소 공통조상은 응용이기 때문에 쉽게 이해 할 수 있다. 희소배열에 대해 알고 싶다면 하단의 링크를 참조하면 된다. https://0bliviat3.tistory.com/79 [자료구조] 희소 배열 (Sparse Table)의 구현(JAVA) 언제 사용하는가 희소배열은 최소 범위 쿼리(Range Minimum Query)의 연산을 수행시 짧은 구현과 빠른 속도로 처리 하고 싶을때 사용하는 자료구조이다. 먼저 최소 범위 쿼리부터 알아보도록 하자. htt 0bliviat3.tistory.com 공통 조상이란? 먼저 최소 공통 조상의 개념부터 정의하고 넘어가도..
언제 사용하는가 희소배열은 최소 범위 쿼리(Range Minimum Query)의 연산을 수행시 짧은 구현과 빠른 속도로 처리 하고 싶을때 사용하는 자료구조이다. 먼저 최소 범위 쿼리부터 알아보도록 하자. https://en.wikipedia.org/wiki/Range_minimum_query Range minimum query - Wikipedia From Wikipedia, the free encyclopedia Minimizing problem in computer programming Range minimum query reduced to the lowest common ancestor problem. In computer science, a range minimum query (RMQ) solv..
언제 사용하는가? 순서가 정해져있는 작업을 차례로 수행해야 할때 그 순서를 정해주기 위해 사용하는 알고리즘이다. 이때 그런 순서가 정해져 있다는건 그래프가 단방향 그래프로 사이클이 없어야 한다. 또 그래프에 따라 여러가지의 순서가 나올수 있다. 특징 1. 현재 그래프가 위상정렬이 가능한지 알 수 있다. (사이클이 발생한다면 위상정렬이 불가능하다.) 2. 위상정렬이 가능하다면 그 정렬된 결과를 알 수 있다. 어떻게 사용하는가? 위상정렬은 다음의 순서로 진행된다. 1. 진입차수가 0인 정점을 찾아 큐에 삽입한다. 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 2.1 꺼낸 원소를 차례대로 저장한다. 3. 간선을 제거한뒤 진입차수가 0인 정점을 큐에 삽입한다. 4. 큐가 비워질때까지 2,3의 과정을 반..
이번 포스팅에서는 최소신장트리를 찾는알고리즘중 간선을 중심으로 생각해 최소신장트리를 구하는 알고리즘인 크루스칼 알고리즘을 다뤄보도록하겠다. 먼저 크루스칼 알고리즘에 앞서 최소 신장 트리의 개념부터 정의하고 넘어가도록 하겠다. 최소 신장 트리란? 먼저 트리는 그래프의 일종으로 순환하지 않는 형태의 그래프를 트리라고 한다. 이때 신장트리 즉 Spanning Tree는 이런 트리의 형태중 최소의 연결만을 갖는 트리를 신장트리라고 한다. 즉 N개의 정점을 갖는 그래프가 있다면 최소의 연결만을 갖도록 하려면 간선의 수는 N - 1개를 갖는 그래프가 될것이고 이를 신장 트리라고 한다. 이런 하나의 그래프에서 이런 신장트리는 여러개가 나올수 있는데 그중에서 간선의 비용을 최소로 갖는 경우를 최소 신장 트리 (Mini..
언제 사용하는가? unoin-find 유니온 파인드 , 분리집합, 서로소 집합, 합집합등 다양한 이름으로 불리는 이 알고리즘은 그래프의 연결관계를 파악할때 아주 효과적인 알고리즘이다. 여러 노드가 존재한다고 가정할때 그중 두개의 노드를 선택해 연결되어 있는가를 확인할때 적용이 가능하다. 다음과 같이 그래프가 있다고 가정해보자. 이때 임의의 노드 1과 4를 골라 연결관계를 파악하고 싶다면 DFS/BFS 등 여러 탐색 알고리즘이 생각날것이다. 그러나 이러한 그래프가 지하철 노선도와 같이 매우 크다라고 가정할때 임의의 두점을 골라 연결관계를 위해 다른 탐색알고리즘을 사용한다면 가능은 하겠으나 시간이 매우 오래걸린단 단점이 있다. 바로 이럴때 유니온파인드 알고리즘을 사용하면 효과적으로 두 노드의 연결관계를 파악..