현재 상황에서 가장 좋은 것만 고르는 욕심꾸러기! 정당성 분석이 가장 중요. 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 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로 구현 :

Binary Search Tree Heap O(1)이 없지만 O(logn)은 가능 탐색은 O(n)이지만 나머지는 O(logn) *min/max는 빠름 정렬되어 있음 삽입이 쉽고 Priority Queue에 이용 크기변화에 유연함