오늘의 기록 오늘의 기록

알고리즘

• 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
• Leet Code - 64. Minimum Path Sum

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

  leetcode.com/problems/minimum-path-sum/ Minimum Path Sum - 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 처음엔 우측 혹은 아래쪽만 체크를하고 작은값으로만 greedy한 방식으로 가면 풀 수 있을거라 생각하고 다음과 같이 수식을 짰었다. dp: MxN 그리드에서 목적지에 도달할 때 합이 최소가 되는 Path dp[x] = 이전 dp[x-1]에서 갈 수 있는 가장 작은 값 그런데 이렇게 수식을 짜보니 당장..

  Read More
• LeetCode - 62. Unique Path

  알고리즘/알고리즘 문제 복기 2021. 4. 2. 08:31

  leetcode.com/problems/unique-paths/ Unique Paths - 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 Answer1. 재귀 맨처음에는 재귀를 이용해서 풀어봤다. m이 가로의 길이고 n이 세로의 길이라 할 때 f(m, n) = f(m-1, n) + f(m, n-1)이라고 수식을 세웠다 그래서 위와같이 코드를 짰는데 시간 초과가 나서 다이나믹 프로그래밍으로 풀었다 Answer2 DP 위와같이 풀었는데 풀긴 했지만 여전히 속도가 그..

  Read More
• LeetCode - 56. Merge Intervals

  알고리즘/알고리즘 문제 복기 2021. 4. 1. 09:15

  leetcode.com/problems/merge-intervals/ Merge Intervals - 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 Answer1 정렬을 하고 난 뒤 c_start = current_start c_end = current_end p_start = previous_start p_end = previous_end로 해서 값을 비교하여 배열에 집어넣었다.

  Read More