Research/Data structure & algorithm15 recursion What is recursion Recursion is the fuction that calls itself. This is good tool to solve the big problem with divide and conquer approach. Rules Exit condition : stack overflow can occurs if there is no exit condition Divide-and-conquer approach Pibonacci Basic divide and conquer with $O(n^2)$ time complexity function getNthFibo(n) { if (n 2023. 12. 9. fundamentals of sorting Sorting(정렬)의 본질은 아이템들의 모음에 순서를 매기는 것이다. 정렬 알고리즘의 종류는 비교하는 방식에 따라 나뉜다. 순서를 매기는 관계 2가지 요소 : ab 이중 하나라도 참인 경우(Trichotomy의 법칙) 만약 a < b 이고 b < c이면, a < c이다(Transitivity의 법칙) Sorting 관련 주요 개념 inversion 정렬에서 중요한 개념은 inversion(도치)이다. inversion해야 하는 것이 많을 수록 순서가 더 뒤죽박죽이라는 것이다. 정렬 알고리즘은 inversion을 0로 줄이는 일련의 작업들을 말한다. stability 같은 층위의 요소들의 순서는 그대로 두는 것을 의미한다. 수정 전 : [“hello”, “world”, “we”, “are”, “learn.. 2023. 12. 9. comparison-based sort comparison-based sorting is the way to define comparison with ordering relationship. Selection Sort 가장 크거나 작은 요소를 찾은 뒤, 리스트의 앞이나 뒤로 옮기는 작업을 반복하는 정렬 알고리즘. 직관적이여서 구현이 어렵지 않지만, 시간 복잡도가 O($n^2$)라는 단점이 있다. 공간 복잡도는 O(1)로 메모리 사용량은 적다. 그리고 stable하지 않아서 같은 층위의 요소들의 순서들까지 섞인다. Bubble Sort If there two adjacent elements are out of order, bubble sort will swap them and keep doing this by looping. 시간 복잡도가 O(.. 2023. 12. 9. 시간복잡도와 공간복잡도 코드의 품질을 평가하는 두 가지 기준 코드의 품질을 평가하는 기준은 여러 가지가 있는데, 그중 가독성(Readability)과 확장성(Scalability)이 있습니다. 가독성(Readability)은 협업과 관련되어있습니다. 아직 성능 보다는 빠른 실행력이 중요한 초기 스타트업의 경우 확장성보다 가독성을 우선시 여기는 경우도 있다고 합니다. 확장성(Scalability)는 실제 코드 성능과 관련되어 있습니다. 확장성에 영향을 미치는 요소는 2가지가 있는데 1)시간 복잡도와 2)공간 복잡도입니다. 시간 복잡도는 속도를 말하고, 공간 복잡도는 메모리 사용량을 말합니다. 문제는 시간과 공간 복잡도 모두를 얻을 수 없다는 점입니다. 따라서 비즈니스 상황에 맞게 이 두 요소 사이의 균형을 찾는 것이 중요합니다... 2023. 3. 18. 이전 1 2 3 4 다음