ComputerScience/Algorithm (21) 썸네일형 리스트형 [프로그래머스]멀쩡한 사각형 내 풀이 : 좌표마다 계산 시간복잡도에서는 선형적이지만, 그래도 직관적인 풀이 같다. function solution(w, h) { var answer = 1; var big = h>w?h:w var small = h>w?w:h var cnt=0; for(var i=0;i 이진트리 Full vs Complete Binary Tree 이진트리에 full 하고 complete binary tree라는 개념이 있다. full binary tree(완전이진트리) 는 모든 level의 Node들이 꽉 차있는 형태이고, complete binary tree는 마지막 level의 노드 중 왼쪽을 순서대로 제외하고 채워져있는 이진트리이다. 일반적으로 이진트리를 구현할 때는 연결리스트를 활용한다. 연결리스트를 택했을 때 Insert, Search, Delete 중, Serach의 시간복잡도는 O(N)이다. 배열이든, 연결리스트이든 시간 복잡도가 O(N)이 되는 구조이다. 따라서 시간 복잡도를 줄이기 위해, 다양한 알고리즘이 나온다. 이진트리의 경우에도, 최악의 경우에는 시간복잡도가 O(N)이 된다.. Non-Comparison Sorting Non-comparison Sort 사전지식을 활용해 정렬 counting sort k 이하의 정수 정렬 dictionary처럼해서 i가 몇번나왔나 센다 stable algorithm radix sort 예를 들어, k 자리 수의 정수들을 정렬하는 경우, 각 자리 수마다 counting sort를 해준다 가능한 이유 : counting sort가 stable algorithm이기 때문이다. //3자리 정수 radix sort var test =Array.from({length: 20}, () => Math.ceil(Math.random() * 899)+100); test=test.map(function(e){return String(e).split('').map(function(a){return Numb.. Hear Sort Heap은 1. Complete Binary Tree 2. Max heap property 혹은 minimum heap property를 만족해야 한다 cf ) Complete Binary Tree란 이진 트리의 맨 마지막 층을 제외하고는 노드가 꽉 차있으며 맨 마지막 층의 경우, 오른쪽 혹은 왼쪽 방향부터 노드가 삽입되어 있다. Heap Sort의 시간 복잡도 : Heap을 n/2번 만들어야됨 -> Heap 만드는데 log(n) 따라서 Heap Sort의 시간 복잡도는 O(N*logN) 이다. Heap을 활용해 우선순위 Queue를 만들기도 한다. Insert할 때의 시간 복잡도는 log(N)이고 Extract할 때는 extract한 후에 heapify를 다시 해줘야되서 시간 복잡도는 log(N)이다. 퀵정렬 최악의 경우가 아닌 Average Case로 Big O notation을 계산한다. 최악의 경우는 O(n^2) : 이미 정렬된 데이터가 들어온 경우 혹은 반대로 정렬된 경우 최선의 경우는 O(N*logN) : 매번 반으로 쪼개지는 경우! var test =Array.from({length: 6}, () => Math.floor(Math.random() * 39)+1); function quicksort(start,end){ if(start===end) { return; } var pointer=start; var pivot=test[end]; for(var j=start;j 이전 1 2 3 다음
