and & 둘다 1일때만 참 9 : 01001(앞에 0은 생략함 뒤에도 마찬가지) 5 : 00101 9&5 : 1 or | 둘 중 하나만 1이어도 참 9 : 01001 5 : 00101 9|5 : 01101 => 1+4+8=13 xor ^ 하나만 1일때 참 9 : 01001 5 : 00101 9^5 : 01100 => 12 not ~ 모든 비트를 뒤집는다. 9 : (000000000000000000000~~)01001 ~9 : (11111111111111111~~)10110 =>-10 왼쪽 이동 1 : 00100 =>4 위의 예에서 오른쪽 이동은 9를 2로 나눈다.(정수 나눗셈) 오른쪽 이동 후 0으로 채우기 >>> 부호 비트가 이동한 후에 0ㅇ로 변한다. 이로 인해 결과는 음이 아닌 숫자가 된다. 오른..
동적 프로그래밍의 규칙 동적 프로그래밍은 재계산을 피하기 위해 이미 계산된 값들을 저장하고 해당 값들을 사용하는 방법이다. 이 방법은 중복 부분 문제들이 존재하고 최적 부분 구조가 존재하는 문제에만 적용할 수 있다. 중복 부분 문제 동적 프로그래밍은 보통 부분 분제의 해결책을 해시 테이블과 배열, 행렬에 저장하며, 이러한 방식을 메모제이션memozation이라고 부른다. 이러한 예를 피보나치 수열의 재귀 메소드에서 찾아볼 수 있다. 시간 복잡도를 O(2^n)에서 O(n)으로 줄일 수 있다. var cache = {}; function fiboBest(n) { if (n
그래프
무지향성 그래프 간선간에 방향이 없는 그래프 간선과 정점 추가하기 //간선을 저장하기 위한 객체 function UndirectedGraph() { this.edges = {}; } //정점(노드) UndirectedGraph.prototype.addVertex = function(vertex) { this.edges[vertex] = {}; } //가중치가 있는 간선을 추가하기 위해서는 this.edges 객체의 양쪽 정점을 사용해 가중치를 저장 UndirectedGraph.prototype.addEdge = function(vertex1, vertex2, weight) { if (weight == undefined) { weight = 0; } this.edges[vertex1][vertex2] = ..
힙
힙은 트리와 비슷한 자료 구조의 일종으로, 최대 힙의 경우 부모가 자식보다 크고 최소 힙의 경우 부모가 자식보다 작다. 이러한 힙의 특성은 자료를 정렬하는 데 유용하다. 다른 자료 구조와 달리 힙은 자식에 대한 포인터를 갖는 대신에 배열을 사용해 자료를 저장한다. 배열에서 힙 노드의 자식 위치(인덱스)를 쉽게 계산할 수 있다. 힙을 사용하면 부모와 자식 간의 관계를 쉽게 정의할 수 있기 때문이다. 이진 힙 배열 인덱스 구조 일반적인 힙 클래스 function Heap() { this.items = []; } Heap.prototype.swap = function (index1, index2) { var temp = this.items[index1]; this.items[index1] = this.item..
이진트리 function BinaryTree() { this._root = null; } 선순위 순회 : 루트, 왼쪽, 오른쪽순 BinaryTree.prototype.traversePreOrder = function () { traverseInOrderHelper(this._root); function traverseInOrderHelper(node) { if (!node) return; console.log(node.value); traverseInOrderHelper(node.left); traverseInOrderHelper(node.right); } }; 중순위 순회 : 왼쪽, 루트, 오른쪽 순 BinaryTree.prototype.traverseInOrder = function() { trave..
캐싱은 자료를 임시 메모리에 저장하는 과정으로 추후에 해당 자료가 다시 필요할 때 쉽게 해당 자료를 얻을 수 있다. 캐시 설계는 주로 두 가지 요소를 고려한다. 1. 시간적 지역성 : 최근에 접근한 메모리 위치를 다시 접근할 가능성이 높다. 2. 공간적 지역성 : 최근에 접근한 메모리 위치 주변의 위치를 다시 접근할 가능성이 높다. LFU(최소 빈도 사용) 캐싱 LFU 캐싱은 운영체제가 메모리를 관리하기 위해 사용하는 캐싱 알고리즘이다. 운영체제는 어떤 블록이 메모리에서 참조된 횟수를 관리한다. 설계상 캐시가 자신의 한계를 초과하는 경우 운영체제는 가장 참조 빈도가 낮은 항목을 삭제한다. 직관적인 접근법처럼 보이지만 메모리의 항목이 단시간에 반복적으로 참조된 다음 이후에 접근을 하지 않는 경우 이상적인 ..
단일 연결 리스트 연결 리스트 자료 구조는 각 노드(항목)가 다음 노드에 대한 참조를 갖는 자료 구조다. 단일 연결 리스트의 노드 function SinglyLinkedListNode(data) { this.data = data; this.next = null; } 단일 연결 리스트 예제의 기본이 되는 코드 function SinglyLinkedList() { this.head = null; this.size = 0; } SinglyLinkedList.prototype.isEmpty = function() { return this.size == 0; } 삽입 SinglyLinkedList.prototype.insert = function (value) { if (this.head === null) { /..
스택(stack) 스택은 자료 구조의 일종으로, 마지막에 삽입된 항목만을 제거하고 접근할 수 있다. 후입선출LIFO, last in first out 속도가 빠르다는 점이 장점. 찾기와 삽입이 상수 시간인 O(1) 자바스크립트에서 배열에는 스택 클래스를 정의한 pop과 push라는 메소드가 있다. 기본 뼈대 코드 function Stack(array) { this.array = []; if (array) this.array = array; } Stack.prototype.getBuffer = function() { return this.array.slice(); } Stack.prototype.isEmpty = function() { return this.array.length == 0; } //inst..