반응형 컴퓨터 사이언스/알고리즘 관련 정리사항4 [알고리즘 공부] 디닉 알고리즘(Dinic's Algorithm) Max flow를 구하는 데 있어, PS에서 쓸 수 있는 알고리즘 중 가장 빠르다고 한다. O(V^2 * E)의 시간복잡도를 가진다. 설명은 아래에. 1. BFS로 유랑이 남은 간선을 기준으로 src에서 dst 노드까지 최단 거리를 구한다.(이를 level graph라고 함) --> BFS라서 O(E)에 가능하다. 선형 시간! 2. DFS로 level graph에서 blocking flow를 흘려주면서 더 이상 못 보낼 때까지 반복한다. --> 생각하기 좀 어려웠는데 한 번 flow를 흘려줄 때마다 bottleneck은 막혀버리니까 최소한 edge하나는 막혀버림. 그리고 edge가 막힐 때 dead end(가다가 막혀버리는 vertex)를 최대 V번 만날 수 있으므로, 많아야 VE번 증가경로.. 2019. 10. 15. [VS Code] 디버깅 설정, Intellisense 관련 오류 백준을 하면서 300문제 가량을 눈디버깅과 수많은 cout으로 풀던 나.. 친구가 너는 외 디버깅 안헤? 라고 물어보자 ?? PS할 때는 디버깅은 눈이나 cout으로 간단하게 하는 거 아녔어?? 라고 대답해버렸다. 그러나 VS Code.. 디버깅.. 넘나리 편한 것.. 친구가 쓰는 걸 보고 나도 쓰려고 마음먹었는데 오류가 나는 것이 아닌가..!!! 그리고.. 나는 거의 텍스트 에디터처럼 vs code를 쓰고 있었는데 Intellisense 설정이 된다고 한다..? 근데 왜 나는 깔아도 안되는 거지..? ㅠㅠ 아무튼 이런 두 가지 오류 때문에 혼자서 시간을 낭비하다 결국 해결했다. 나같은 불쌍한 사람들이 나오지 않게 이런 글을 올려놓을테다. 1) Unable to Start debuggin.. 2019. 10. 10. [알고리즘 공부] 트리의 구현과 순회 트리 계층적 관계를 표현하는 자료구조. 특정한 조건을 지키도록 구성한 트리를 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업도 더 빠르게 할 수 있다. 트리의 용어 중 꼭 알아야 하는 내용 리프(Leaf) 노드 : 자식이 하나도 없는, 즉 트리에서 가장 하단에 위치하는 노드들을 의미한다. BST에서 리프노드의 수는 전체 노드가 2^k개면 2^(k-1)이다. 트리의 깊이(Depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 깊이라 함. 트리의 높이(Height)는 가장 깊숙히 있는 노드의 깊이를 의미한다. 트리의 재귀적 속성 : 한 노드와 그의 자손들을 모으면 그들도 하나의 트리가 된다.(Subtree) 즉, 모든 트리는 루트와 루트 밑에 있는 subtree들의 집합이다. 트리.. 2019. 7. 6. c++ binary_search 1. binary_search(starting point, ending point, value);특정 value가 어떤 container안에 있는 지 없는 지 bool 값으로 return함 // 백준 10815번 문제(숫자카드) 2. equal_range(starting point, ending point, value);특정 value가 어떤 container안에 몇 개 들어가있는지에 대한 정보를 제공 : pair로 lower_bound와 upper_bound를 return사용 예시 : auto a = equal_range(numbers.begin(),numbers.end(), value); // 백준 10816번 문제 (숫자카드 2) 2018. 11. 10. 이전 1 다음 반응형