ComputerScience (48) 썸네일형 리스트형 [프로그래머스] 점프와 순간이동 function solution(n) { var ans = 0; var end = n; var cost = 0; while(end!==0) { if(end%2===1) { end = (end-1)/2 cost++; } else{ end= end/2 } } return cost; } 이진수 변환 n.toString(2)을 활용하면 더 쉽다. Hashing Hashing을 할 때 문제가 되는 것은 중복키이다. 2가지 해결 방법이 있는데 , chaining과 open addressing이다 1. Chaining 중복된 값일 경우, 각 칸을 연결리스트로 구현한다. 2. Open Addressing 중복된 값일 경우, 특정 규칙(linear,quadratic,double hashing 등)에 의해 빈칸이 나올 때까지 칸을 찾는 방법이다. linear probibg의 경우 clustering의 문제가 발생할 수 있기 때문에, quadratic, double hashing 등의 hashing 방벙이 있다. Hashing 성능 분석을 위한 가정 simle uniform hashing assumption 키값들이 확률적으로 Hashing 값에 동등하게 Mapping 된.. [프로그래머스] 소수만들기 function solution(nums) { var len = nums.length var answer =0; for(var i=0;i [프로그래머스]멀쩡한 사각형 내 풀이 : 좌표마다 계산 시간복잡도에서는 선형적이지만, 그래도 직관적인 풀이 같다. 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)이 된다.. [자바스크립트] 연결리스트 구현한 연결리스트의 ADT 1. 삽입 2. 삭제 3. 존재유무 시간복잡도 - 정렬하지 않는 경우 삽입 : O(1) , 삭제 : O(N), 조회 : O(N) - 정렬하는 경우 삽입 : O(N), 삭제 : O(1), 조회 : O(N) function Node(data) { this.data =data; this.next = null; } function LinkedList() { this._length = 0; this._head = new Node('dummy'); this._tail = this._head; this._before = null; this._cur = null; } LinkedList.prototype.append = function(data) { var node =new Node(data.. 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)이다. 이전 1 2 3 4 5 6 다음
