오늘의 기록 오늘의 기록

분류 전체보기

• 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
• Backtracking

  알고리즘 2021. 2. 13. 07:30

  정의 백트래킹은 문제를 Brute force 방법의 일종으로, 문제를 재귀적으로 풀어내서 점진적으로 해결책을 마련하는 방법이다. Example Knight's tour 문제를 보자. N*N의 보드에서 체스말인 나이트가 이 보드를 전부 방문한다고 할 때, 나이트가 방문한 순서를 print하는 문제이다. 푸는 방법에는 두가지가 있는데 하나는 모든 경우의 수를 생성하고 조건을 만족하는지를 check하는 Naive Algorithm 두번째는 Backtracking이다. 1. Naive Approach 모든 경우를 생성하고, 조건에 만족하는지를 체크하는 방법이다. while there are untried tour { generate the next tour if this tour covers all square..

  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
• Leet code - 1. Two Sum

  알고리즘/알고리즘 문제 복기 2021. 2. 6. 19:38

  leetcode.com/problems/two-sum/ Two 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 1. Brute force 언어: C++ 2중 for문을 이용해 풀었다. 단순하게 전체를 훑어서 맞는 값을 찾아내는 방식 2. map 이용 a + b = target b = target - a 인 것을 이용해 배열을 훑는건 똑같지만 map에 값을 담고 map에 target - nums[i]를 뺀 값이 있는지 확인해서(조건을 충족하는 값이 있는지..

  Read More