본문 바로가기

알고리즘90

BOJ 15586 - Moo tube ( 오프라인 쿼리, 유니온 파인드 ) https://www.acmicpc.net/problem/15586 왜 정답률이 65퍼인지 궁금한 문제 자연수 가중치가 있는 트리가 주어진다. 정점 u~v경로 상의 가중 치 중 가장 작은 값을 usado(u,v)라고 한다. 최대 1e5개의 쿼리 (ki, vi)가 주어진다. vi와 연결된 정점 중 유사도가 ki이상인 정점의 수를 구하라. V^2에 풀수있지만 TLE. 아예 다른방법으로 접근해야 한다. 임의의 정점에 대해 유사도 ki이상인 정점을 구하려면 가중치가 ki이상인 간선들만 필요하다. ->가중치가 ki 이상인 간선들로만 이뤄진 스패닝 트리를 두고 생각하면 편해진다. 쿼리를 ki에 대해 내림차순으로 정렬하고 간선도 가중치 기준으로 내림차순 정렬한다. 쿼리를 순차로 보면서, ki이상의 가중치를 가진 간선.. 2020. 2. 19.
DFS트리에서 간선의 종류, 사이클 검출 ㅁ방향그래프 dfs를 수행하면 그래프의 모든 간선을 한 번씩은 만나게 된다. 그래프에서 어떤 점에서 dfs를 수행하면 트리가 만들어지는데, 트리를 중심으로 그래프의 모든 간선의 종류를 구분해보면 1. 트리간선 dfs트리를 이루는 간선 2. 순방향 간선 스패닝 트리의 선조에서 자손으로 연결되지만 트리간선이 아닌 간선 3. 역방향 간선 트리의 자손에서 선조로 연결되는 간선. 당연히 트리간선에 포함 안됨. 그래프의 사이클유무 판단할때 사용하는 간선. ( 이 간선이 존재하면 그래프에 사이클 존재 ) 4. 교차간선 그 외의 모든 간선. 선조-자손관계가 아닌 정점들 간 연결된 간선. vector adj[MAX]; int vst[MAX]; //방문순서 기록. -1이면 방문안된것. bool fin[MAX]; int c.. 2020. 2. 13.
오일러 경로 '한붓그리기' 로 모든 간선을 칠한다면 그게 바로 오일러 경로 오일러 경로가 존재하려면 1. 출발점=도착점인 경우 (오일러 서킷) 양방향: 모든 정점의 차수가 짝수면 된다. 단방향: 모든 정점의 indegree==outdegree 2. 출발점 != 도착점인 경우 (오일러 트레일) 양방향: 출발점과 도착점의 차수는 홀수고 나머지 정점의 차수는 짝수면 된다. 단방향: outdegree[i]==indegree[i]+1인 점(시작점) 단 한개, indegree[i]==outdegree[i]+1인 점(도착점) 단 한개 존재. 컴포넌트가 여러 개인 경우 당연히 오일러 서킷이 존재하지 않을 거라고 생각할 수 있지만, 컴포넌트의 정점이 하나인 경우 간선이 존재하지 않는다는 점을 유념해야 한다. -> 모든 간선이 하나의.. 2020. 2. 12.
이진 탐색 트리, 트립 보통 c++의 set이나 map을 이진탐색트리로 구현한다. (avl트리나 레드블랙 트리) 하지만 set이나 map은 k번째로 큰 원소가 무엇인지 알 수없다. 이런 기능을 가능하게 하는 구조로 '트립'이 있다. stl에서 사용하는 구조보단 느리지만 확률적으로 최악의 경우 로그시간에 동작한다. 노드에 값 외에 우선순위를 추가로 갖는다. 우선순위는 생성시 랜덤하게 부여된다. 트립은 다음 두가지 속성 (bs tree + heap)을 만족해서 treap이라고 부른다. 1. 모든 노드에 대해 왼쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 작고, 오른쪽 서브트리에 있는 노드들의 원소는 해당 노드의 원소보다 크다. 2. 모든 노드의 우선순위는 각자의 자식 노드보다 크거나 같다. typedef long lo.. 2020. 2. 10.

티스토리툴바