본문 바로가기

Algorithm/Basic Concept

 (7)
[Lecture] SCC SCC : Strongly Connected Component Connecte Component는 undirected graph에서 존재한다 SCC는 directed graph에서 임의의 두 정점에 대해 양방향으로 가는 경로가 모두 있을 때, 존재한다 즉, 모든 노드가 양방향으로 reachable한 노드의 최대한 키운(Maximal Subset) 집합이다 //SCC는 사이클이 한 개 이상 겹쳐진 형태를 띤다. 하나의 정점도 SCC가 될 수 있다 [참고] Directed graph : 문제를 해결한 알고리즘이 나왔을 때, 같은 방향으로 undirected graph에도 적용시켜 해결할 수 있다 Undirected graph : undirected graph에서 해결한다고 해서 directed graph가 ..
[Lecture] BCC Biconnected Component (maximal set) Biconnected Graph : 임의의 한 노드를 제거해도 나머지 모든 노드들이 연결되어 있는 그래프이다. 따라서 biconnected graph에는 cv가 존재하지 않는다 (무방향 그래프에서 정의되는 개념이다) Biconnected Component : cv에 의해 끊어진 그래프들의 각 부분을 의미한다 BCC 내의 임의의 두 노드는 완전히 다른 (edge와 node가 겹치지 않는다) 2개 이상의 경로가 존재한다 cv가 있으면, 그래프 전체가 BCC가 아니다(정의와 모순됨) 기본적으로 cycle을 BCC라고 한다 cv가 있었는데, 사라지면 연결이 끊기는 것이므로 BCC상태가 아니다 * cv는 여러 BCC에 걸쳐있다 * cv가 아닌 노드는..
[Lecture] Cut Vertex Cut Vertex 전제 : 전체가 연결된 graph가 있다고 했을 때 (일부분을 봐도 되지만, 여기선 그냥 전체를 전제로 한다) Cut vertex를 버리면, graph가 disconnected graph가 된다 x와 y가 존재한다고 하자 x에서 y로 가는 모든 path가 s(Cut vertex)를 통해서 간다 그래프에서 Cut Vertex를 어떻게 찾을 수 있을까? - 노드를 하나씩 빼보면서 disconnected graph가 되는지 확인한다 각 노드(N)에 대해 DFS를 한다(M+N) = O(N(M+N)) = O(MN) Cut Vertex => cv로 대체한다 Idea1 child가 하나일 땐, parent는 cv가 아니다 왜냐하면, 하나의 노드가 사라진다고 해도, connected graph를 유..
[Lecture] Graph Traversal 특정 노드(x) 하나가 없어지면, 그래프가 끊어질 때, 특정 노드(x)를 구하는 방법은 무엇일까? 방향이 없으면 힘들어진다 다익스트라는 소스에서 가까운 것부터 방향을 만들어가면서 해결한다 보통 방향을 정한 다음에 늘려가면서 구한다 local과 global 정보가 섞여 들어오면서 문제를 풀게된다 다익스트라에선 빨간색이 최종답이었다 위 그림에서 30 입장으로 인접한 노드들을 바라봤을 때, 35,38,40이라는 정보를(local)알 수 있다 global 정보는 파란 것 중에서 가장 작은 것을 뽑는 것이다 global정보가 간단할수록 쉽게 풀린다 다익스트라는 traversal로 볼 수 있다 Traversal어떤 순서에 따라 그래프의 노드를 방문한다 일반적으로, 해당 노드에서 연산을 하면 방문했다고 표현하고, 지..
[Lecture] Greedy Algorithms, Minimum Spanning Tree Greedy Algorithm 답을 찾기 위해 선택을 반복하는 알고리즘들 중 비교적 간단한 방법으로 선택하고, 선택한 후 바꾸지 않는 알고리즘이다 selection sort도 가장 작은 숫자를 맨 앞으로 보내고 뒤돌아보지 않기 때문에 greedy이다 shortest path는 보통 greedy algorithm으로 문제를 해결한다 (edge weight = 비용) 노드가 n개이면, edge는 n-1개이다 shortest path는 결국 edge n-1개를 구하는 문제이다 Greedy Algorithm은 항상 해결 가능한 알고리즘인가? Minimum Spanning Tree 모든 노드를 포함하는(span:덮다) 트리를 찾는데 비용이 최소화되도록(minimum) 하는 것이다 Prim Algorithm 1. ..
[Lecture] Sum, Binary Search, Selection Sort A Simple Code & A Simpler Code 첫번째 그림: 일반적으로 누적합을 구할 수 있는 코드 두번째 그림 : 재귀로 누적합을 구할 수 있는 코드 두번째 그림의 코드가 맞는지 증명해보자 수학적 귀납법 : sum(x)는 1+2+...+x를 항상 리턴한다 base: P(1) 즉, 코드에 1을 넣었을 때 return값은 1이다 따라서 sum(1)이 리턴하는 값은 1임을 알 수 있다 step: 코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴한다 sum(x-1)의 리턴값은 1+2+...(x-1)와 같다고 할 때, sum(x)는 1+2+....+x를 리턴한다는 것을 확인할 수 있다 Binary Search & Recursive Binary Search 시간 복잡도 : O(n) (첫번째 코드..
[Lecture] The Halting Problem, 수학적 귀납법 Halting Problem Q : 프로그램 M과 입력 X가 있을때, M에 입력 X를 주고 수행시키면 종료할 것인가? A : 특수한 경우는 알 수 있으나, 모두 알 수 있다고 확신할 수 없다 돌려봤을 때, 언제 끝날지 모르기 때문에 '무한루프'가 절대로 안끝난다는 것을 확신할 수 없기 때문이다 어떤 프로그램이 종료하는지 알 수 있는 방법이 있을까? D(M,X)은 프로그램 M에 X를 입력했을 때 멈추면(exit) Yes, 멈추지 않으면(loop) No 중 하나를 출력하고 항상 멈추는 프로그램이라고 가정하자 이해하기 쉽도록 exit - yes, loop - no를 사용한다 D라는 프로그램이 있으면, D' ,S 프로그램을 만들 수 있다 D'은 입력값에 의해 종료하면 프로그램을 실행하고, 종료하지 않을 경우 프..

티스토리툴바