알고리즘31 동적 프로그래밍 - 메모이제이션(Memoization) *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) DYNAMIC PRGRAMMING is.. an optimization technique. dynamic programming = divide and conquer + memoization 언제 Dynamic Programming을 적용할지에 대한 Cheatsheet 1. Can be divided into subproblem? 2. Recursive Solution 3. Are ther repetitive subpr.. 2019. 11. 7. 자바스크립트 검색 알고리즘 3 : Depth First Search *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) 1. Depth First Search(DFS) Breadth First Search(BFS)가 각 level에서 좌 → 우로 돌면서 탐색했다면, Depth First Search(DFS)는 가장 아래쪽 level까지 내려갔다가 끝에 다다르면 가장 가까운 조상으로 거슬러 올라간 뒤 탐색하지 않은 다른 자식 노드, 즉 형제 노드들을 탐색하는 방식이다. 글로는 설명이 어렵고 아래 사진이 이해하기에 직빵이다. DFS의 경우.. 2019. 11. 7. 자바스크립트 검색 알고리즘 2 : Breadth First Search *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) Array, Hash Table, Queue, Stack, Linked List에서 Traversing하는 방법은 앞선 글들에서 정리해보았다. 그런데 Graph와 Tree에서는 Traversing을 어떻게 할 수 있을까? 이 자료구조형에서 Traversing을 하고, 원하는 값을 찾을 때 사용하는 알고리즘이 바로 Breadth First Search(BFS), Depth First Search(DFS)이다. 결론부터 .. 2019. 11. 7. 자바스크립트 검색 알고리즘 1 : Linear Search, Binary Search *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) 앞서 정렬 알고리즘에 대해서 살펴봤다면, 이번에는 모든 노드들을 traversing하면서 검색하는 알고리즘에 대해서 살펴보자. 검색은 실생활에서 아주 많이 사용되는 기능이기 때문에 잘 살펴보자. 1. Linear Search 가장 단순하지만, 동시에 가장 비효율적인 검색 알고리즘이다. 단순히 list를 특정 값을 찾을 때까지 loop over하는 작업이다. 검색을 시작하자마자 찾게 되는 Best Case에서는 O(1).. 2019. 11. 7. 자바스크립트 정렬 알고리즘 9 : 활용 사례 *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) 언제 어떤 정렬 알고리즘을 사용하면 좋을지, 간단한 예시로 알아보자. 아래 대답은 Andrei의 의견이며 정답은 아닐 수 있다. //#1 - Sort 10 schools around your house by distance: insertion sort input된 dataset의 크기가 무척 작기 때문에 Insertion Sort가 가장 빠르고, 공간복잡도도 효율적이다. //#2 - eBay sorts listings.. 2019. 11. 5. 자바스크립트 정렬 알고리즘 8 : Radix Sort, Counting Sort *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) 여태껏 배운 Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort는 모두 comparison, 즉 element들 간의 비교를 통해 정렬을 하는 알고리즘이었다. 이들 정렬 알고리즘의 경우, 시간복잡도에서 최선은 O(n log n)이었는데, 이를 더 개선시킬 수는 없을까? 이를 개선시키는 것은 수학적으로 불가능하다고 한다. 그러나 element 간의 비.. 2019. 11. 5. 자바스크립트 정렬 알고리즘 7 : 언제, 어떤 정렬 알고리즘을 사용해야 할까? *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) # Insertion Sort(삽입 정렬) 1) dataset의 크기가 작을 때 2) dataset이 거의 정렬이 되어 있을 때 # Merge Sort(합병 정렬) 1) dataset이 아주 방대한 크기인데 내 컴퓨터 메모리의 외부에서 정렬을 수행할 수 있을 경우, Merge Sort의 유일한 단점인 공간복잡도 문제가 해결될 수 있으므로 사용하기에 최적인 상황이다. 2) dataset의 정확도가 의심되거나, 적절한 p.. 2019. 11. 4. 자바스크립트 정렬 알고리즘 6 : Quick Sort *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) Quick Sort는 Merge Sort보다 직접 구현하기가 더 복잡하다. Quick Sort 또한 Divide and Conquer 개념을 사용하고, 동시에 Pivoting 개념을 활용한다. Quick Sort는 공간복잡도가 O(log n)으로 Merge Sort의 O(n)보다 메모리 효율성이 높은 알고리즘이다. 하지만 주의할 점은, worst 케이스의 경우 시간복잡도가 O(n^2)가 될 수 있다는 점이다. 특히 어.. 2019. 11. 4. 자바스크립트 정렬 알고리즘 5 : Merge Sort *Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다. *자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :) 앞서 살펴본 Bubble Sort, Selection Sort, Insertion Sort는 시간복잡도가 O(n^2)가 되기 때문에 무척이나 비효율적인 정렬 알고리즘이었다.(특정 조건에서 Insertion Sort는 제외. 자세한 것은 이 글에서 확인할 수 있다.) Merge Sort는 Divide and Conquer 및 recursion을 활용하는 로직이며, 따라서 O(n^2)에서 더 개선된 O(n log n)의 .. 2019. 11. 4. 이전 1 2 3 4 다음
