알고리즘90 후속 노드 그래프 (Successor graph), 희소테이블 모든 정점에 대해 인접한 정점이 단 하나인 그래프로, 함수형 그래프(functional graph)라고도 부른다. succ(x)의 형태로 후속 노드 그래프의 모든 간선을 표현할 수 있기 때문. 후속 노드 그래프는 하나 이상의 컴포넌트로 구성돼 있고, 각각의 컴포넌트는 사이클 '하나'와 그 사이클로 가는 경로로 구성되어 있다. (그래프의 끝에 사이클이 단 하나 달린 형태) 트리구조와 유사하다.(트리에서 루트노드가 자식중 어딘가 가리키고 있다면 후속노드 그래프가 된다. -- 그건 더이상 트리가 아님) 희소테이블 p[u][k]에 이 구조를 담아 푸는 문제가 대부분 - 정점 u에서 k번 이동한 후의 정점을 log시간에 구하기 기본문제 : https://cses.fi/problemset/task/1750 널리쓰이.. 2020. 1. 29. codeforces 563 div2 D - Ehab and the Expected XOR Problem (XOR, prefix xor) https://codeforces.com/contest/1174/problem/D xor문제는 기발한게 많은 것 같다. subsegment란, 맨 앞 혹은 맨 뒤 요소를 포함한 subarray이다. n과 x를 입력받아서 숫자 배열을 하나 만든다 ( ai < (1 2020. 1. 29. BOJ 1854 - K번째 최단경로 찾기(다익스트라) https://www.acmicpc.net/problem/1854 다익스트라 알고리즘을 완전 이해해야 풀 수 있었던 문제. 가중치가 항상 양수이므로 다익스트라 사용 한 도시를 여러번 방문할 수 있다. 이 조건을 명시하지 않아서 조금 어색하게 느껴졌던 것 같다. https://cses.fi/problemset/result/312681/ 유사문제 단방향 가중치 그래프가 주어진다. 1번도시에서 출발하여 i번째 도시로 갈 때 k번째 최단 길이를 찾아라. (중복허용 ex) 2번도시로 가는 길이가 1 3 3 5 이고 k==3이면 답은 3이다.) 우선 나이브하게 접근해보면 dist[i] : 1번도시에서 출발하여 i번째 도시로 가는데 길이를 모두 저장. 위 경우, dist[i]는 pq혹은 set으로 구현할 수 있다. .. 2020. 1. 25. 사이클 검출 ㅁ 양방향 그래프 https://cses.fi/problemset/task/1669 prv배열과 사이클의 끝점, 시작점을 잘 캐치하면 된다. 양방향 그래프가 주어질 때 사이클이 없으면 IMPOSSIBLE출력, 있으면 아무 사이클이나 사이클을 이루는 정점의 크기와 정점번호들 순서대로 출력 const int MAX = 1e5 + 2; int n, m, prv[MAX], st, en; vector adj[MAX]; bool vst[MAX], fin[MAX]; void dfs(int curr, int pr=0) { vst[curr] = true; for (int next : adj[curr]) { if (!vst[next]) { prv[next] = curr; dfs(next,curr); } //다음 정점이 방.. 2020. 1. 23. 이전 1 2 3 4 5 6 ··· 23 다음