현재 상황에서 가장 좋은 것만 고르는 욕심꾸러기! 정당성 분석이 가장 중요. 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. ex. 동전 거슬러줄 때, 단위가 큰 동전부터 생각해야 하는 이유? 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문. coins = [500, 100, 50, 10] pocket = int(input("얼마있어?\n")) count = 0 answer = {} for coin in coins: count += pocket // coin answer[coin] = pocket // coin pocket %= coin print(answer) import java.util.Scanner; public..

// Time: O(n^2) & Space: O(1) function bubble(arr) { for (let i=0; i= array[j-1] && array[i] < array[j]) { //move number to the right spot array.splice(j,0,array.splice(i,1)[0]); } } } } } } // Time: O(nlogn) & Space: O(n) const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]; function mergeSort (array) { if (array.length === 1) { return array } // Split Array into left and right const length ..

for loop : O(n) recursion : O(2^n) 재귀는 시간복잡도가 기하급수적으로 늘어나기 때문에 큰 자료에는 전혀 적합하지 않다. 하지만 자료가 크지 않고, 데이터에 사용되는 연산이 모두 동일한 경우에는 재귀만큼 가독성이 좋고 간편한 것이 없다. 특히 트리같이 같은 연산을 중복하여 훑는 경우에는 작은 모듈을 반복하듯이 처리할 수 있다. 모든 재귀는 반복문으로 대체할 수 있지만, 재귀만이 갖는 효용성은 Merge Sort, Quick Sort, Tree Traversal, Graph Traversal을 쉽게 처리한다.

재귀함수로 구현 : 일반 for loop로 구현 :

Big O는 Input이 증가함에 따라 연산의 양이 얼마나 더 많이 증가하는지를 나타내는 지표로, 알고리즘의 성능을 나타낸다. O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!) *언제나 절대적이지는 않다. 예를 들어 배열이지만 길이가 정해진 경우에는 상황에 따라 O(n) 알고리즘이 O(1) 알고리즘보다 더 성능이 좋을 수 있다. *JavaScript에서 문자열의 .length는 O(1)이다. *그렇다고 확장성만 따질 것은 아니고, 가독성 또한 좋아야 한다. https://www.bigocheatsheet.com/ Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell ..