728x90 반응형 Data Structure & Algorithm17 Dynamic Programming _ Memoization 설명 및 적용 #2(숫자형) 2022.10.06 - [Data Structure & Algorithm] - Dynamic Programming _ Memoization 설명 및 적용 #1 위 글에 이어 2번째 시리즈입니다 Cansum 예시 _ 첫번째 게시물의 Dynamic Programming 레시피를 바탕으로 cansum(targetSum, numbers) 주어진 numbers로 targetSum 을 만들 수 있는지 cansum함수를 만들어보겠습니다. (cansum 함수는 targetSum을 만들 수 있는지, 없는지 True/False를 반환해야 합니다) cansum(7,[5,3,4,7])을 기반으로 발생가능한 경우의 수를 tree로 나타냈습니다. 이 케이스를 통해 마지막 노드가 0이 되면 True를 반환하고 그 외의 경우에는 F.. 2022. 10. 9. Dynamic Programming _ Memoization 설명 및 적용 #1 Why ? What is Dynamic Programming? 🧐 피보나치수열 예시 _ const fib = (n) => { if (n { if (n in memo) return memo[n]; if (n { if (m === 1&& n === 1) return 1; if (m === 0 || n === 0) return 0; return gridTraveler(m-1,n) + gridTraveler(m,n-1); }; 하지만 이 코드는 time complexity로 비효율적이라는 단점이 있는데요 어떤 부분이 겹치는지, 효율성이 개선될 수 있는지 보면 사실상 gridTraveler(a,b) = gridTraveler(b,a) 로 계산을 중복으로 할 필요가 없음을 알게됩니다 이 부분에 memoization.. 2022. 10. 6. Big O notation 예시 위주 정리 😎 Time Complexity 계산법 n이 input하는 변수의 사이즈(샘플값)이라고 할 때, 전체 시간 T를 아래와 같이 나타냅니다 T = an + b 1. find the fastest growing term 가장 차수가 큰 항을 찾는다 -> fastest going term is 'an' 2. take out the coefficient 앞에 상수를 제외 한다 -> O(n) 예시) T = cn**2 + dn + e 1. cn**2 2. n**2 -> O(n**2) T = c 1. c 2. 1 -> O(1) O(1) Constant time 예시) def function(array): total = 0 -> O(1) return total -> O(1) T = O(1) + O(1) = c1 + c2.. 2022. 10. 4. Fenwick Tree (Binary Indexed Tree, 이진인덱스 트리) √ 펜윅 트리란? Data structure that supports sum range queries as well as setting values in a static array and getting the value of the *prefix sum up some index efficiently >> 위키백과의 설명을 빌리자면, 요소 업데이트와 접두사의 합계 계산을 효과적으로 수행하도록 하는 트리를 의미합니다 ** 구간합 Prefix sum (Cumulative sum, inclusinve sum, inclusive scan) Prefix sum이 감이 잘 안와서 찾아봤는데요, 일반적으로 생각하면 이런 누계합을 의미하는데요 computer science 알고리즘과 functional programmi.. 2022. 9. 29. Trie (트라이, Digital tree, prefix, Retrieval tree) + 예제 코드 Trie 란? : 탐색트리의 일종으로 동적 집합이나 연관배열을 저장하는데 사용되는 트리 자료 구조 (출처: 위키백과) **문자열, 접두사와 관련된 검색에 매우 유용하게 사용됨 Leetcode의 Trie관련 문제를 통해서 더 자세히 알아봅시다! https://leetcode.com/problems/implement-trie-prefix-tree/ Implement Trie (Prefix 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 예시 답안 풀이).. 2022. 9. 27. Union Find Union Find 란? : Data structure that keeps track of elements which are split into one or more disjoint sets 위키백과의 설명을 빌리자면, Union Find는 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료 구조를 의미합니다. 주요 기능 : Find , Union Find Operation (어떤 set에 속해있는지 판별) : To find which component a particular element belongs to find the root of that component by following the parent nodes until a slef loop is reached(a node w.. 2022. 9. 26. 이전 1 2 3 다음 728x90 반응형
