다이나믹 프로그래밍은 어려워도 방향이 존재함
(왼쪽에서 오른쪽으로 푼다던지, 값이 작아지는 쪽으로 푼다던지 ... 이런식으로 방향 정할 수 있음)
근데 그래프는 방향이 있나? -> 없음
프로그램을 짠다고 했을 때 근처만 본다. -> 짜는게 굉장히 어려움
저번에 배운 다익스트라나 MST에서는 방향을 정할 수 있었다.
다익스트라 : 소스에서 거리가 작은 것 부터(미리 정해지는게 아니라 계산하다보면 순서가 정해지는 것) -> 그래서 어려움
MST/프림 : 소스에서 가까운 거 부터
MST/크루스칼 : 엣지weight가 작은 거 부터
다익스트라든, 프림이든, 크루스칼이든 local에서(즉, 가까운 근처에서 뭘 하는 거)뭘 하는 걸로 풀어야함
일단 저번에 배운 다익스트라를 보자
다시 원래 그림으로 돌아가서...
그래프를 돌아다니면서 global한 view를 수집하고
그 정보가 복잡하면 시간이 오래 걸리고, 간단하면 빨리 풀리는 알고리즘이 나올거임(문제마다 다름, 이런 흐름으로 간다는 뜻)
Traversal이 뭘까
전체적인 구조
- 그래프를 돌아다닌다. (돌아다닌다의 뜻 : 내가 지금 보고 있는 노드와 엣지가 있는거임(전체정보를 수집하는 것))
- 그래프에 있는 노드들을 어떤 순서로 방문을 해서 같은 노드를 여러번 지나갈 수도, 무언가 계산을 하는 것
전체를 돈 다음에 어떤 자료구조가 생김 -> 보통은 트리가 생김
이 트리에서 유용한 정보를 뽑아서 어떤 문제를 풀 수 있음
Any-Order Traversal
- 어떤 노드s에서 시작함(Box에 넣음)
루프돔(Box가 비어있지 않는 동안)
- Box에서 꺼냄(구체적으로 무엇을 꺼내냐에 따라 알고리즘 달라짐)
다익스트라는 Box에 파란애들 들어있고, 파란애들 중 값이 제일 작은 걸 꺼냄
- 노드가 마킹이 안되어 있으면(마킹이 되었다는 건 이미 작업을 했다는 것 여기선 visit을 작업을 한다로 해석, 보통은 작업 한번만 함) 작업을 한다.
- 무언가 계산을 한다.
- 모든 인접한 노드를 박스에 넣는다.(여러번 들어갈 수 있음)
This Solves Reachability
Reachability
S에서 T까지 갈 수 있는 길이 있냐?
다익스트라로 풀 수 있음
-> 다익스트라 돌려서 shortest path길이가 무한대가 아니면 갈 수 있음
Any order Traversal을 하면 길이 있는지 없는지 알 수 있다.
-> T가 마킹되어 있으면 길이 있는거임
Proof
1. 길이 있으면 마크를 한다와, 2.길이 없으면 마크를 안한다를 증명해야됨
- 증명
2.증명
마크가 되는 모든 노드는 길이 있고, 수학적 귀납법으로 마크가 된다는 거는 보일 수 있다.
길이 있는 노드가 넣어서 마크가 되는 것
수학적 귀납법으로 마크가 되는 노드는 길이 있다는 것을 보일 수 있다.
길이 있는 경우만 정확히 마크한다는 것을 증명한게 됨
Connected Component
연결된 덩어리(더 이상 키울 수 없는 노드의 집합 maximal이라고함(maximum은 global하게 제일 큰거, maximal은 local하게 제일 키울 수 있는 것
고등학교때 최대(maximum), 극대(maximal) 이랑 같은 거임)
시간은 얼마나 걸릴까?
노드개수 n개, 엣지개수 m개
Start at a Node s(Put s into Box) -> 상수 시간
While Box is not Empty -> 1)이 작업은 몇번 할 까? : 2m
Take one Node from Box 2m(알고리즘에 따라 다름)
if Node not marked
Mark Node -> n번 O(1)
Do computation on Node -> n번 * O(1)
위 두개는 노드마다 한 번씩 밖에 안돔
Put Every Adjacent Node into Box
-> 노드마다 붙어있는 엣지 개수 마다 다를 거임
이 횟수하고 1)횟수하고 뭔가 깊은 관계 있어보임
이 횟수를 전체 알고리즘 도는 동안 다 합한 거랑 1)횟수하고 똑같을 거임
그래서 작업한 횟수 다 더하면 얼마일까?
2m
전체시간 : 시간이 일정하지 않은 로직이 있다. -> Take one Node from Box(Box에서 뭘 꺼내냐에 따라 시간이 걸리는 게 다름)
다익스트라 관점에서 볼때
While Box is not Empty -> m번
Mark Node,Do computation on Node(내꺼 업데이트 하고, 주변을 때려박음(한번할때마다 상수시간) -> n번
근데 Take one Node from Box -> 우선순위 큐에서 제일 작은 걸 꺼내니깐 logm
전체 시간 : mlogm
이런식으로 시간을 분석할 수 있음
시간이 달라지는 부분
Put Every Adjacent Node into Box
Take one Node from Box
Box로 Event Queue라는 걸 쓸 때도 있음
Event Queue
감염이 멈출 때 까지 몇초가 걸릴것인가?
느리게 푸는 방법
nm이라고 하면 nm시간 걸쳐서 쭉 다 보고, 감염이 될 칸은 감염을 시키고 다시보고 다시보기를 반복
총 시간 : nm * 감염이 멈출때까지의 시간
어떻게 하면 더 빨리?
최종감염 상태를 구하는 걸로 생각하면 조금 더 쉽게 접근 가능
전체 시간 : nm + nm(늘어나는 최대 횟수) = 2nm(훨씬 빠름)
감염이 새로 생길 때 큐에 넣고 꺼내서 감염 시키고 주변을 보는 것 뿐
-> 칸 하나당 상수시간을 쓰게 됨(감염될 수 있는 칸은 최대 nm개임)
그래서 이 방법이 아니라 처음 소개한 방법대로 하면
최대 nm개 늘어나서
최악의 경우에는 nm*nm = (nm)^2이 걸릴 수도 있음
What kind of Box
- stack을 쓰면 -> DFS라고 부름
Box에 stack을 쓰면 방금 넣은게 나옴
뒤에 있는 놈이 나를 Box에 넣고, 뒤에 놈도 넣은게 있을 거임 나도 Box에 여러개 넣은게 있음 -> 내가 넣은걸 먼저 빼게 됨
뒤에 놈 입장에서는 내가 할일을 다하고 자기한테 주는게 됨
(그렇게 되면 멀리 가게 됨(depth))
그래서 DFS가 됨 - Queue를 쓰면 -> BFS가 됨
내가 박스에 집어넣고, 뒤에 놈이 집어 넣은게 있을 텐데 뒤에 놈이 먼저 집어 넣은게 먼저 빠짐 나한테 왔어도 내가 집어 넣은 건 뒤에 놈이 집어 넣은 게 다 끝나야 내 차례가 옴
-> 뒤에 놈의 가까운 것 부터 끝나게 됨(넓어진다고 해서 BFS)
다익스트라하고 똑같은 거
BFS를 하면 shortest path찾음
언제? -> edge weight가 전부 1일 때((엣지 개수 기준으로)가까운거부터 가는 거니깐) - Priority Queue를 쓰면
edge weight를 가지고 꺼내면 -> Prim
소스에서 나까지의 거리를 집어넣고 PQ쓰면 -> Dijkstra
아무 function이나 할 수 있으면 -> A*
A*
바둑 생각
나의 판 상태에서 검은 돌 넣을 수 있는 방법 많을 거임 -> 그게 다 노드임
사람은 감으로 여기 놓으면 좋은 자리/ 안좋은 자리 판별
판모양을 보고 좋은 모양인지 안 좋은 모양인지 계산할 수 있는 함수가 있다면 그 함수가 제일 좋은 거를 큐에서 꺼내는 것 -> A*
Recursive DFS
DFS를 Recursive로 구현하기도 함
RDFS(Node s)
-Mark Node s
- Set pre(s) -> 노드에 번호를 붙이는 방법(진입한 순서)
- For every adjacent node t
if t is not marked RDFS(t) - Set Post(s) -> 노드에 번호를 붙이는 방법(떠난 순서)
인접한 모든 노드에 대해서 mark가 안되어 있으면 재귀호출 하는 거임
-> 똑같이 DFS되는 거임
every adjacent node t not marked
call RDFS(t)
이렇게 되면 어떻게 될까?
1)모든 노드에 대해서 마킹이 안되어 있으면 RDFS부른다.
2)모든 마크 안된 노드에 대해서 RDFS부른다.
똑같은 말 아닌가? -> 다름
부르기 직전에 확인해야 함
아주 큰 차이가 있음
1)의 경우
2)의 경우
2처럼 하면 RDFS(1) 부르면 2번 마킹이 되어 있음
-> 두 번 부르게 됨, 미리보면 3번.... (DFS랑 달라지게 됨)
마킹이 되어 있는 건 안불러야 하는데..... 이건 그대로 RDFS(2)를 실행시켜버림
그래서 1)처럼 부르기 직전 마킹되어있는지 봐야함
Pre(s), Post(s)예시
그 전에 DFS의 결과는 한 가지가 아님을 기억!
Simulate Recursive with Any-Order
- Start at a Node s(put s into Stack)
- While Stack is not Empty
- Take one Node p from Stack- If Node not Marked
- Mark Node
- Do computation on Node
- Put Every Adjacent Node q into Stack
- Mark Node
- If Node not Marked
위 부분은 스택을 명시적으로 써서 만드는 것
아까 Recursive도 스택을 씀(콜 스택(재귀 호출 할 때 스택이 쌓임))
DFS를 하고 나면 Tree가 만들어짐(루트가 있는 트리)
콜을 아래쪽으로 한 거(전진했다고 얘기하자)
Bipartite Graph Detection
그래프가 Bipartite인지 확인
엣지가 아예없어도 bipartite그래프임
모든 엣지가 cross로만 잇도록 나눌 수 있는 방법이 하나라도 존재하면 Bipartite그래프임
DFS트리 구한 다음 Backedge중에 같은 그룹(L,R)끼리 잇는 거 있으면 Bipartite아님!
