오늘의 기록 오늘의 기록

알고리즘/알고리즘 문제 복기

• 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
• LeetCode - 49.Group Anagram

  알고리즘/알고리즘 문제 복기 2021. 4. 1. 07:31

  leetcode.com/problems/group-anagrams/ Group Anagrams - 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 Key는 정렬된 스트링을 써서 anagram이 같은지 확인하는 방식 Answer2 각각의 스트링에 26개의 알파벳에 대한 카운트 값의 스트링을 연동시켜서 만약 알파벳의 카운트가 같다면 anagram으로 판별하는 방식

  Read More