dfs
-
[LeetCode] Combination Sum알고리즘 2020. 5. 4. 16:39
문제 Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example..
-
[LeetCode] Word Break II알고리즘 2019. 12. 19. 17:07
문제 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "catsanddo..
-
[LeetCode] Palindrome Partitioning알고리즘 2019. 12. 7. 15:57
문제 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] Approach DFS로 string을 i글자씩 잘라가며 palindrome인지 확인한 후 palindrome이면 자르고 남은 string을 재귀함수를 통해 다시 잘라 확인하여 최종적으로 자른게 모두 palindrome이면 답 배열에 추가한다. Code https://github.com/chi3236/algorithm/blob/master/Leet..
-
[LeetCode] Maximum Depth of Binary Tree알고리즘 2019. 12. 3. 01:54
문제 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3. Approach DFS를 활용한 inorder traversal로 depth를 측정하거나 BFS를 활용한 level order traversal로 depth를 측정하면 된다. Co..
-
[LeetCode] Word Search알고리즘 2019. 11. 19. 17:52
문제 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE"..
-
Graph자료구조 2019. 9. 3. 17:12
Vertex와 Edge로 이루어진 자료구조 G=(V,E) Undirected graph - Vertex를 잇는 Edge에 방향이 없는 그래프. 최대 edge 수 n(n-1)/2 (n은 vertex개수) Directed graph - Vertex를 잇는 Edge에 방향이 있는 그래프. 최대 edge 수 n(n-1) Connected component - 현재 연결성을 유지하면서 더 이상 vertex나 edge를 추가할 수 없는 최대한의 subgraph. connected graph에는 오직 하나의 connected component만이 존재 Cycle - 그래프에서 edge를 통한 순환. cycle은 DFS를 활용해 O(V+E)만에 찾을 수 있음 # 사이클 찾기 그래프 문제를 풀다 보면 '사이클을 찾아라'..