Will the Guru

Category: Algorithm

  • Container With Most Water

    Problem https://leetcode.com/problems/container-with-most-water/description/ Solution

  • LRU Cache

    Problem https://leetcode.com/problems/lru-cache/description/ Solution

  • House Robber II

    Problem https://leetcode.com/problems/house-robber-ii/description/ Solution

  •  The Earliest Moment When Everyone Become Friends

    Problem https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/description/ Solution Notes How to sort 2D array in ascending order How to sort 2D array in descending order

  • Redundant Connection

    Problem https://leetcode.com/problems/redundant-connection/ Solution #1. DFS Solution #2. Union Find

  • Number of Connected Components in an Undirected Graph

    Problem https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/ Solution #1. DFS Solution #2. Union Find

  • Graph Valid Tree

    Problem https://leetcode.com/problems/graph-valid-tree/description/ Solution #1. DFS Solution #2. Union-Find Solution #3. Union-Find with boolean type

  • Number of Provinces

    Problem https://leetcode.com/explore/featured/card/graph/618/disjoint-set/3845/ Solution

  • Disjoint Set (Union-Find)

    What is Disjoint Set ? Idea of Union-Find #1. Parent Vertex를 저장하는 배열을 만든다. #2. 각 Edge 를 돌면서 parent vertex를 업데이트한다. (Union) #3. Connectivity 확인 (Find) Quick Find – Improved Idea of Union-Find #1 위에서 서술한 방법에서 조금만 개선하면 더 나은 알고리즘이 될 수 있다. parent vertex 배열을 root…

  • Kahn’s Algorithm – Topological Sorting

    문제들 중, graph 에서 특정 노드를 방문하기 전에 다른 노드를 반드시 방문해야하는 케이스들이 있다. 예를 들어, 수강하고자 하는 강의는 선수강 강의가 있어서 해당 강의를 먼저 들어야 하는등.. 이런 경우 DFS 를 통해 문제를 푸는것도 가능하지만, Kahn’s Algorithm 을 통해 문제를 풀 수 있다! Algorithm 1. inDegree(=incoming path 갯수) 가 0인…