오늘의 기록 오늘의 기록

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

• Leetcode - 104. Maximum Depth of Binary Tree

  알고리즘/알고리즘 문제 복기 2021. 2. 14. 17:27

  leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary 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 Answer 처음에 Left Depth, right depth라는걸 새로 만들어서 구현하려고 했어서 좀 헤매긴 했는데 다행히 DFS에 대해 사전지식이 약간이나마 있어서인지 풀 수 있었다. 하지만 트리라던지, 기존의 알고리즘 배웠던 것들을 까먹은 것들이 많아서 다시 복습을..

  Read More
• LeetCode - 70. Climbing Stairs

  알고리즘/알고리즘 문제 복기 2021. 2. 14. 15:21

  leetcode.com/problems/climbing-stairs/ Climbing Stairs - 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 1스텝또는 2스텝으로만 계단을 올라가는 경우의 수를 구하는 문제. 고민을 많이 했었는데 결국 풀어내지 못했고 답지를 봤다. 다이나믹 프로그래밍으로 풀어내는 문제였다. Answer1. Top-down approach 만약 주어진 계단의 수가 5개라고 한다면 내가 할 수 있는 경우의 수는 1. 1개의 계단을 올라간다. ..

  Read More
• LeetCode - 53. Maximum SubArray

  알고리즘/알고리즘 문제 복기 2021. 2. 13. 20:50

  leetcode.com/problems/maximum-subarray/ Answer 배열의 -를 어찌 처리할지 감이 안와서 결국에는 답지를 보게 되었다. 답지에서는 sum의 값이 -일 경우에만 sequence를 리셋하고 계속해서 더하는 방식을 취하고있다. 혹은 다음과 같은 방식으로도 가능하다. Answer2, Dynamic Programming state dp[x]를 '이제까지 sub-array에서 해당 값을 포함한 가장 큰 값'이라고 정의했다. 그럴 경우 2가지 경우가 생기게 되는데 1. 해당 배열 현재 인덱스의 '값'이 가장 큰 값일 경우 2. 이전 배열을 연장한 값이 가장 큰 값일 경우 두가지로 나뉘어서 위의코드 11번 라인에서 두가지의 값을 구하고 max를 취해주는 것을 볼 수 있다.

  Read More
• Leetcode - 21. Merge Two sorted List

  알고리즘/알고리즘 문제 복기 2021. 2. 13. 12:19

  leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - 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 새로운 리스트를 만들고 두개의 리스트의 값을 비교해 값을 순차적으로 집어넣는 과정을 거쳤다. 다음과 같이 재귀함수로도 쓸 수 있다.

  Read More
• Leetcode - 20. Vaild Parentheses

  알고리즘/알고리즘 문제 복기 2021. 2. 13. 11:53

  leetcode.com/problems/valid-parentheses/ Answer 괄호의 타당성을 검사하는 전형적인 스택문제였다. '(', '[', '{'가 나오면 stack에서 peek을 진행하여 '(', '{', '['가 나오는지 확인하고 맞다면 pop을 해주고 아니라면 false를 하도록 코드를 짰다. 풀어낸 뒤에 다른 사람의 문제 풀이와 답안을 봤었는데 간결하게 만들기 위해 해시 맵을 이용하는 방법도 있었다.

  Read More
• Leetcode - 17. Letter Combination of a Phone Number

  알고리즘/알고리즘 문제 복기 2021. 2. 13. 10:48

  leetcode.com/problems/letter-combinations-of-a-phone-number/solution/ Answer 언어: java 해시화까지 하고 푸는 방법의 방향성까지는 생각을 했었는데, 재귀문에 익숙하지 못해 구현하지 못했었고, 다른 코드를 참고해 완성시켰다. 다음과 같은 방식으로 코드들을 조합한다. 위와 같은 과정을 재귀문을 통해서 구현하였다.

  Read More
• Leetcode - 15. 3Sum

  알고리즘/알고리즘 문제 복기 2021. 2. 13. 06:33

  leetcode.com/problems/3sum/ '풀어낼 떄 2Sum을 이용해야겠다'라는 생각을 하고 접근해서 풀어보려고 했지만 중복을 해결하지 못해서 풀어내지 못했었다. Set을 사용해서 Output을 세팅하려 했지만 [-1, 0, 1], [0, -1, 1]은 다른것으로 처리되어 중복은 해결되지 않았다. 결국 Discussion 탭을 보게되었고 다음과 같이 풀이가 있었다. 2Sum의 기법을 사용하는 방법까지는 맞는 방향성이였던 것 같다. 중복을 해결하는 방법으로, 우선 배열을 정렬해 준 다음에, 16번 라인, 17번 라인에서 위와 같이 값이 중복이라면 index값 다음 값으로 넘기는 방식으로 진행하여 중복을 해결해냈다.

  Read More
• Leet code - 2. Add Two Number

  알고리즘/알고리즘 문제 복기 2021. 2. 8. 19:06

  leetcode.com/problems/add-two-numbers/ Add Two Numbers - 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 ..

  Read More