해나의 컴공생존기

1. SCC (Strongly Connected Compnent) 방향 그래프에서 임의의 두 정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 점은 같은 SCC에 속해 있다고 한다. 즉 SCC는 모든 노드가 양방향으로 Reachable한 노드의 Maximal Subset 이다. 쉽게 말하자면 x→y가 있고 y→x가 있다면 strongly conneced하다고 한다. 사이클이 이의 가장 간단한 형태이다. 여기서 Maximal 과 Maximam의 차이를 조금 짚고 넘어갈 필요가 있응 것 같다. Maximal 은 한국어로 번역하면 극대라고 할 수 있다. 그 상황에서 가장 큰 값으로 이해하자. Maximam은 전체에서 가장 큰 것을 의미한다. DFS Tree에서 여러 트리가 있을 때 하나의 트리에는 여러가..

1. Cut Vertex Cut Vertex (절단점)는 제거할 경우 그래프가 끊어지게 되는 노드를 의미한다. 각 노드마다 노드를 지우고 그래프가 끊어졌는지를 확인하면 O(n (m+n))의 시간이 걸리게 된다. 하지만 DFS를 돌리고 DFS Tree를 생성하면 O(m+n)만에 절단점을 찾을 수 있다. 1.2. root Cut Vertex root 노드는 child가 2개 이상이라면 무조건 cut vertex이다. 증명해보자! 1) child가 0개인 경우 루트 노드밖에 없으므로 성립 2) child가 1개인 경우 사진과 같이 root노드가 없어도 자식노드들 끼리 다 연결되어있다. 3) child가 2개 이상일 경우 루트노드에 1번 서브트리와 2번 서브트리가 있다고 가정해보자. 1번 서브트리에는 어딘가에 ..

1. Recursive DFS RDFS 는 시작노드로부터 인접한 노드로 방문하는데, 앞 노드가 방문되지 않았으면 그 노드에서 또 재귀적으로 호출한다. 각 노드들이 RDFS의 인자가 되는 것은 한번 뿐이므로 시간 복잡도는 O(m+n)이 걸린다. 1.1 DFS tree DFS에서 전진한 edges로만 생성한 결과를 DFS Tree라 한다. 시작 노드가 루트이고, 전진하면서 방문한 노드들을 자식으로 하나씩 갖게 된다. 1.2 edge 종류 Tree Edges: DFS Tree에 들어간 모든 엣지들 Forward Edges: 조상에서 자손으로 연결되는 엣지 중 트리에 포함되지 않는 엣지들 Back edges: 자손에서 자기보다 조상들 중 하나로 연결되는 엣지 (DFS 과정에서 이미 방문한 노드로 향하는 엣지) ..

Equivalence Relation 정의 관계의 정의 Given a set A, a Relation on A is any subset of AxA Ex) A = {1, 2, 3, 4}, R = {(1,3), (3,4), (1,1), (2,2)} We write 1R3 to mean (1,3) ∈ R An extreme example Relation '

Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Stack 구현 Stack Pointer는 값이 다음에 들어올 자리를 뜻한다. Stack Code int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int Push() { Stack[SP] = x; SP++; } int Pop() { SP--; return Stack[SP]; }​ # 미로찾기 이런 미로 문제를 해결하는 알고리즘 중에 DFS 와 BFS가 있다. 오늘은 DFS로 미로를 찾는 과정을 알아볼..