오늘의 기록 오늘의 기록

분류 전체보기

• Leetcode - 105. Construct Tree from Preorder and Inorder Traversal

  알고리즘/알고리즘 문제 복기 2021. 5. 27. 11:19

  https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Construct Binary Tree from Preorder and Inorder Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Answer Preorder는 Root가 우선해서 순회하는 방식이다 즉 ( Root, Left, Right ) 순으로 순회하고 Inorder는 Root를..

  Read More
• BFS(Breadth-first-search) 넓이 우선 탐색

  알고리즘 2021. 5. 26. 12:19

  정의 BFS란 트리나 그래프 자료구조를 서칭하는데 사용되는 기법이다. 루트노드에서 시작해서 다음노드로 이동하기 전에 현재 깊이의 모든 인접 노드를 탐색하는 방식으로 진행된다. Python Code G는 Graph, v는 이미 방문한 지역을 나타내는 마커라고 할 때 다음과 같이 나타 낼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 marked = [False] * G.size() def bfs(G, v): queue = [v] while len(queue) > 0: v = queue.pop(0) if not marked[v]: visit(v) marked[v] = True for w in G.neighbors(v): if not marked[w]: queue.append(w) cs 활용처 1..

  Read More
• Leet Code - 98. Validate Binary Search Tree

  카테고리 없음 2021. 5. 25. 13:13

  https://leetcode.com/problems/validate-binary-search-tree/ Validate Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 해결 과정 이진검색트리가 유효한 이진검색트리인지 알아보는 문제였다 이진검색트리는 다음을 만족하는 트리를 말한다 왼쪽에 있는 서브트리는 반드시 현재 루트의 값보다 작은 값만 있어야 한다 오른쪽에 있는 서브트리는 반드시 현재 루트의 값보다 큰 값만 있어야 한다 그..

  Read More
• LeetCode - 96. Unique Binary Search Tree

  알고리즘/알고리즘 문제 복기 2021. 5. 18. 12:20

  Unique한 바이너리 서치 트리의 개수를 구하는 문제 처음에는 바이너리 서치 트리에 대해서 생각을 안해서 못풀었었다. 바이너리 서치 트리는 루트보다 큰 값은 오른쪽에 저장하고 작은 값은 왼쪽에 저장하는 방식의 자료구조라고 한다. Answer. Root가 x라면 바이너리 서치 트리의 특성에 따라서 왼쪽에는 x보다 작은 값만 올 수 있고 오른쪽에는 x보다 큰 값만 올 수 있다 만약 N=3이고 루트도 3이라면 왼쪽에는 2이하의 값들만 나오고 오른쪽에는 아무값도 나올 수 없다 즉 g(x)를 루트가 x일때 가질 수 있는 Unique Binary Search의 경우의 수라고 한다면 g(x) = g(m) * g(n)이 된다. 따라서 다음과 같이 정리 할 수 있게 된다. 이를 DP를 이용해 풀어내면 된다. Refer..

  Read More
• LeetCode - 94. Binary Tree Inorder Traversal

  알고리즘/알고리즘 문제 복기 2021. 4. 26. 12:48

  단순한 Tree Traversal 문제 Inorder가 뭔지 까먹었었어서 문제 이해를 못했었다. Tree Traversal 용어 정리 Inorder: Left, Root, Light 순으로 순회 Preorder: Root, Left, RIght 순으로 순회 Postorder: Left, Right, Root 순으로 순회 Answer1. Recursion Answer2. Iteration 되돌아가는 부분을 어찌 해야할지 감이 안잡혔어서 솔루션을 봤다. 솔루션에선 Stack을 활용해서 되돌아가는 방식을 사용했다.

  Read More
• Leet code - 79. Word Search

  알고리즘/알고리즘 문제 복기 2021. 4. 24. 11:35

  leetcode.com/problems/word-search/ Word Search - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 인접한 셀을 탐색해서 목표하는 word가 있는지 확인하는 문제 Answer 접근하는 방법은 다음과 같이 생각했다. 1. 배열에서 처음 word의 character를 찾는다 2. 찾으면 4방향을 체크해서 다음 word의 characrter가 있는지 찾는다. -> 없으면 False 3. 찾은 방향으로 이동한다 4. 해당 워드가 전부 ..

  Read More
• LeetCode - 78. Subsets

  알고리즘/알고리즘 문제 복기 2021. 4. 13. 07:24

  leetcode.com/problems/subsets/ Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Answer 백트래킹을 이용해서 풀었다. 맨처음에 어떻게 풀어야 할지 감이 잘 안잡혔던 것은 백트레킹의 탈출조건인 list.size() == cur_length를 어떻게 줘야 할지 감이 잘 안왔었는데 반복문으로 길이가 0일때부터 주어진 배열의 길이까지의 길이 값을 변수로 넘겨준 뒤 list의 사이즈가 같을 때 리턴하는 방식으로 풀었다.

  Read More
• LeetCode - 75. Sort Colors

  알고리즘/알고리즘 문제 복기 2021. 4. 12. 08:09

  leetcode.com/problems/sort-colors/ Sort Colors - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Answer QuickSort를 이용해서 풀었다 이번에 알아본 QuickSort은 다음과 같이 진행된다. 1. Pivot index를 정한다 2. Pivot index보다 작은 값은 왼쪽으로 옮긴다 3. Pivot index보다 큰 값은 오른쪽으로 옮긴다 4. 위 과정을 반복한다 구현은 Partition이라는 함수를 통해 진행되는..

  Read More