blog

https://stackoverflow.com/questions/54992302/pure-functions-does-no-side-effects-imply-always-same-output-given-same-inp Pure Functions: Does "No Side Effects" Imply "Always Same Output, Given Same Input"? The two conditions that define a function as pure are as follows: No side effects (i.e. only changes to local scope are allowed) Always return the same output, given the same input If the firs..

Dynamic Programming (DP) DP는 복잡한 문제를 여러 개의 부분 문제(sub-problems)로 쪼개서 해결하는 알고리즘 패러다임이다. 이때, 이러한 부분 문제들의 해(solution)을 기록하여 중복되는 부분 문제를 여러 번 계산하지 않도록 한다. DP로 풀 수 있는 문제는 다음의 두 가지 속성을 갖는다. (1) Overlapping Subproblems (2) Optimal Substructure Overlapping Subproblems DP는 부분 문제의 해를 결합한다는 점에서 분할 정복(Divide and Conquer)과 비슷하지만, 같은 부분 문제의 해를 여러 번 이용한다는 점에서 분할 정복과 다르다. 따라서 중복된 부분 문제(Overlapping Subproblems)를 ..

# Dijkstra 1. Prim Algorithm과 유사하다. https://thesulks.tistory.com/31 Prim ~ Dijkstra (BOJ1197 최소 스패닝 트리, BOJ1753 최단경로) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를.. thesulks.tistory.com # Bellman-Ford 1. 음수 사이클 (negative cycles) 음수 사이클은 |V|-1번 edge relaxation을 수행한 뒤 한 번 더 edge relaxation을 수행하여 확인할 수..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 최소 스패닝 트리의 가중치가 -2147483648보다 크거나 같고, 2147483647보다 작거나 같은 데 www.acmicpc.net #include #include #include #include using namespace std; int main() { i..

https://stackoverflow.com/questions/26549140/breadth-first-search-time-complexity-analysis Breadth First Search time complexity analysis Time complexity to go over each adjacent edges of a vertex is say O(N), where N is number of adjacent edges. So for V number of vertices time complexity becomes O(V*N) = O(E), where E is the total ... stackoverflow.com

https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf/3332994#3332994 When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would..

https://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container Why is vector not a STL container? Item 18 of Scott Meyers's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library says to avoid vector as it's not an STL container and it doesn't rea... stackoverflow.com https://stackoverflow.com/questions/16738579/is-using-a-vector-of-boolean-..

https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time/19647659 What is pseudopolynomial time? How does it differ from polynomial time? What is pseudopolynomial time? How does it differ from polynomial time? Some algorithms that run in pseudopolynomial time have runtimes like O(nW) (for the 0/1 Knapsack Problem) or O(√n) (for... stackov..