'algorithm' 태그의 글 목록

Dijkstra 다익스트라 ( V + E ) log E

힙을 이용하면 다익스트라의 시간복잡도를 O(N^2) 이 아니라 O( (V+E)logE )에 구현이 가능하다.

C++ STL priority queue 를 이용해서 구현한 Dijkstra algorithm.

Posted by LucidasH

오른쪽 끝에서 부터 1 , 2, ... 이라고 번호를 매겼을 때 ,

C[i,j] 는 위는 1~i , 아래는 1~j 까지 고려했을 때 가능한 경우의 수.

c[i,j] 는 만약 i,j 스위치가 연결 되어있다면

c[i,j] = c[i-1,j-1] * 2;

연결 안되어있다면,

c[i,j] = c[i-1,j] + c[i,j-1] - c[i-1,j-1]; ( 빼 주는 부분은 중복 되어 계산 되기 때문에 한 번 배주는 것. 포함배제의 원리 )

를 완성하면 이제 c[n,n] 부터 backtrace 를 하면서 답을 유추해야 한다.

연결이 되지 않은 경우는 bit 가 1이 될 수 없으므로 j를 하나 감소

만약 연결이 되어있다면, c[i-1,j-1] 을 살펴봐서 갯수를 카운팅 해서 , 결정해나간다.

( 경우의 수를 구한 뒤 그것을 통해 index 를 찾아다는 보편적인 DP 의 방법을 사용하면 된다 )

Posted by LucidasH

Posted by LucidasH