알고리즘
-
LeetCode - 121. Best Time to Buy and Sell Stock알고리즘/알고리즘 문제 복기 2021. 2. 16. 22:49
leetcode.com/problems/best-time-to-buy-and-sell-stock/ Best Time to Buy and Sell Stock - 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 배열문제이고, 최댓값을 구하는 문제이므로 DP를 활용해서 풀어보기로 했다. state인 dp[x]는 x인덱스의 날에 팔았을 때의 PROFIT의 최댓값 이라고 정의를 했다. PROFIT의 최댓값이 되려면, 이전에 stock을 산 값이 최솟값이여야 Profit 즉..
-
Dynamic Programming알고리즘 2021. 2. 16. 11:17
다이나믹 프로그래밍이란 복잡한 문제를 sub-problem들로 나누고 중복된 계산을 피하기 위해 sub-problem들을 풀어낸 결과를 저장하고 사용하는 것을 말한다. DP의 두가지 속성 Overlapping SubProblem Optimal Substructure Property DP의 두가지 속성 1. Overlapping Subproblem 분할정복에서와 같이 DP는 문제를 sub-problem들로 쪼개고 다시 합치는 방식으로 문제를 풀어나가기 때문에 문제를 쪼갤 수 있다면 DP를 적용 할 수 있다. 2. Optimal SubStructure Property 주어진 문제를 sub-problem에서 최적화된 답을 사용해서 최적화된 답을 얻을 수 있다면 Optimal Substructure Proper..
-
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에 대해 사전지식이 약간이나마 있어서인지 풀 수 있었다. 하지만 트리라던지, 기존의 알고리즘 배웠던 것들을 까먹은 것들이 많아서 다시 복습을..
-
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개의 계단을 올라간다. ..
-
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를 취해주는 것을 볼 수 있다.
-
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 새로운 리스트를 만들고 두개의 리스트의 값을 비교해 값을 순차적으로 집어넣는 과정을 거쳤다. 다음과 같이 재귀함수로도 쓸 수 있다.
-
Leetcode - 20. Vaild Parentheses알고리즘/알고리즘 문제 복기 2021. 2. 13. 11:53
leetcode.com/problems/valid-parentheses/ Answer 괄호의 타당성을 검사하는 전형적인 스택문제였다. '(', '[', '{'가 나오면 stack에서 peek을 진행하여 '(', '{', '['가 나오는지 확인하고 맞다면 pop을 해주고 아니라면 false를 하도록 코드를 짰다. 풀어낸 뒤에 다른 사람의 문제 풀이와 답안을 봤었는데 간결하게 만들기 위해 해시 맵을 이용하는 방법도 있었다.