처리해야할 여러가지 일들이 있고, 이들 사이의 선후 관계가 있는 그래프. DAG (Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 조건. 진입 차수(indegree)를 이용한 정렬 탐색큐, 결과큐 사용 O(|V|+|E|) 진입 차수가 0이 아닌 정점이 남아 있으면 사이클이 있는 그래프 //V : 정점집합, E : 간선집합, Q : 탐색큐 //Adj[v] : 정점 v의 인접 정점 리스트 //indegree[v] : v의 진입차수 //resultQ : 정렬된 정점 //각 정점의 진입차수 계산 선행 for (v : V) if (indgree[v] == 0)//간선이 없는(indegree가 0인) 정점을 큐에 모두 넣기 Q.offer(v); resultQ.offer(v); wh..
집합의 공집합을 포함한 모든 부분 집합 크기는 2 ^ n
순열 Permutation 서로 다른 n개의 원소에서 r개를 중복없이 뽑아 순서를 정해 나열하는 경우 nPr = n! / (n-r)! nP0 = 1 , nPn = n! 중복 순열 n개의 원소에서 r개를 순서에 상관있게 뽑는데, 중복을 허락할 때의 경우 n^r 조합 Combination 서로 다른 n개의 원소에서 순서에 상관없이 r개를 뽑는 경우 nCr = nPr / r! nC0 = 1, nCn = 1 nCr = n-1Cr-1 + n-1Cr nCr = nCn-r 중복 조합 조합과 마찬가지로 n개의 원소에서 r개를 순서에 상관없이 뽑는데, 중복을 허락할 때의 경우 nHr = r+(n-1)Cr = n+r-1 C n-1
최소신장트리 (Minimum Spanning Tree) 신장트리 : 모든 정점들은 포함하고 간선은 (정점수-1) 개만 포함하는 트리, 사이클 없음 신장 트리 중에서 간선 가중치의 합이 최소인 신장 트리 ★Kruskal : Union-Find(Disjoint Set) 사용 O(|E|log|V|) Prim : 우선순위큐 사용 O(|E|log|V|) 간선을 기준으로 LinkedList에 담아 정렬 후 Union-Find Union Find by Rank 트리의 높이가 높을 수록 Find Set 수행시간 증가 Union 시 두 집합의 Root 중 Rank 값이 작은 Root를 큰 Root로 변경 Rank 값이 같을 경우에만 랭크 값 증가 public static void unionSet(int a, int b)..
시작점에서 가까운 정점부터 순서대로 방문 Queue O(|V|+|E|) 최단 경로 문제 해결 가중치가 없는 그래프 //V : 정점 집합, E : 간선 집합, Q : 큐 //visit[v] : 방분정보 저장 //Adj[v] : 정점 v의 인점 정접들 집합 //D[] : 시작점부터 각 정점까지 거리 //P[] : 최단 경로 트리 저장 bfs(s) { for (v : V) { D[v] = Max; P[v] = null; } D[s] = 0; P[s] = s; visit[s] = true; Q.offer(s); while(!Q.isEmpty()) { v = Q.poll(); for (인접 정점 u : Adj[v]) { if (visit[u] == false) { D[u] = D[v] + 1; P[u] = v; ..
인접한 간선 모두 방문 더 이상 갈 곳이 없으면 Back Tracking 재귀호출, Stack 그래프의 전체 구조를 파악 O(|V|²) 두 정점이 서로 연결되어 있는가 연결된 부분집합의 개수 세기 위상정렬 사이클 존재여부 //V : 정점 집합, E : 간선 집합 //visit[v] : 방문정보 저장 //Adj[v] : 정점 v의 인접 정점 집합 dfs(v) { visit[v] = true;//방문 처리 for (인접 정점 u : Adj[v]) { if (visit[u] == false)//인접 정점이 방문하지 않았다면 탐색 dfs(u); } }