본투비곰손

메모이제이션 (직관적일 때 사용) 재귀함수를 이용하여 하향식 계산 방식으로 어려운 문제를 간단하게 해결할 수 있다. 계산 결과를 해시 테이블에 저장하고 재사용 하기 때문에 속도가 빠르지만 메모리를 사용한다. 중복 계산을 하지 않아 속도가 빠름 function fibonacci1(n) { if (n == 0 || n == 1) return n; return fibonacci1(n - 2) + fibonacci1(n - 1); } function fibonacci2(n, memo) { if (n == 0 || n == 1) return n; if (memo[n] == null) { memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return m..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 17. 23:14

버블 정렬 옆 데이터와 비교하면서 자리를 바꾸는 정렬 방법 버블 정렬의 성능 for 문을 2개 사용 하는 O(n²) 장점 이해와 구현이 간단함 단점 성능이 좋지 않음 function BubbleSort(arr) { for (let i = 0; i arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } let arr = [4, 2, 3, 1]; console.log('=====정렬 되기 전 배열====='); console.log(arr); console.log('=====정..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 17. 00:52

재귀 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말한다. 재귀 함수는 기저조건(종료되는 조건)이 반드시 있어야 한다. 기저조건이 없는 재귀함수를 실행하면 메모리 부족으로 함수가 강제 종료 된다. 재귀함수 내에서 자기자신을 호출할 때 이미 이 함수 구현되어 있다고 가정한다. 하향식 계산에 사용된다. 콜스택 함수가 호출되면서 올라가는 메모리 영역 먼저 들어온 데이터가 나중에 나간다. 스택 자료구조를 잘 활용한 대표적인 사례 팩토리얼 - n이 주어졌을때 1부터 n까지 모든 수의 곱을 말한다. 5! 와 같이 작성 한다. 배열의 합 (재귀적으로 구하기 하향식 방법) [1, 2, 3, 4, 5]의 배열의 합을 구할 때 하위문제의 결과는 [1, 2, 3, 4]의 배열의 합이고 이 배열의 합에 5를 더하면 된다..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 14. 22:20

셋(Set) 데이터의 중복을 허용하지 않는 자료 구조 해시테이블을 사용하기 때문에 해시 셋이라고도 한다. 해시 테이블을 사용 하여 해시 셋을 구현 import { HashTable } from './HashTable.mjs'; class HashSet { constructor() { this.hashTable = new HashTable(); } add(data) { if (this.hashTable.get(data) == null) { this.hashTable.set(data, -1); } } isContain(data) { return this.hashTable.get(data) != null; } remove(data) { this.hashTable.remove(data); } clear() { ..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 13. 22:33

해시 테이블이란? 해시 함수를 사용하여 인덱스를 만들어 테이블을 만드는 자료 구조 분류해주는 해시 함수가 중요함 빠른 데이터 읽기, 삽입, 삭제가 가능하다. 메모리를 많이 차지한다. 해시테이블의 구현 양방향 연결 리스트를 활용하여 해시 테이블을 만들 수 있다. import { DoublyLinkedList } from './DoublyLinkedList.mjs'; class HashData { constructor(key, value) { this.key = key; this.value = value; } } // 해시함수의 결과 값이 중복 일 수 있으니 양방향 연결 리스트를 사용한다. class HashTable {//양방향 연결 리스트인 10개의 배열을 만들어 준다. constructor() { th..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 12. 22:31

덱의 개념 데이터의 추가와 삭제를 head와 tail에서 자유롭게 할 수 있다. 양방향 연결 리스트를 사용하여 쉽게 구현할 수 있다. import { DoublyLinkedList } from './DoublyLinkedList.mjs'; class Deque { constructor() { this.list = new DoublyLinkedList(); } printAll() { this.list.printAll(); } addFirst(data) { this.list.insertAt(0, data); } removeFirst() { return this.list.deleteAt(0); } addLast(data) { this.list.insertAt(this.list.count, data); } re..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 11. 23:29

큐의 개념 먼저 들어간 데이터가 먼저 나오는 구조로 Stack와 반대 특성 맨 먼저 들어간 데이터를 삭제하기 위해서 가장 앞(head) 노드부터 순서대로 타고 가야하는 단점(느려짐 O(n)의 성능)이 생기는데 이를 보완하기 위해 tail 이라는 변수를 설정해 준다. tail이라는 변수를 설정한다고 해서 성능이 보완되지는 않는다. tail이 가리키된 Node를 삭제 하더라도 삭제된 Node 앞의 Node를 다시 tail로 설정해줘야 하기 때문 우리가 만든 연결 리스트는 다음 Node만 가리키는 단방향 연결 리스트이기 때문에 tail로 이전 Node를 참조할 수 없다. 현재 노드가 이전 노드를 가리킬 수 있는 이중 연결 리스트로의 수정이 필요하다. 이중 연결 리스트로의 수정으로 각 노드가 이전 노드로 가리킬..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 10. 22:31

스택의 개념 단순한 규칙을 가지고 있는 리스트 먼저 들어간 데이터가 나중에 나온다. 스택 구현 지난 배열에서 작성했던 LinkedList를 사용하면 쉽게 작성 할 수 있다. import { LinkedList } from './LinkedList.mjs'; class Stack { constructor() { this.list = new LinkedList(); } push(data) { this.list.insertAt(0, data); } pop() { try { return this.list.deleteAt(0); } catch (e) { return null; } } peek() { return this.list.getNodeAt(0); } isEmpty() { return this.list.co..

CS전공 지식/2. 자료구조와 알고리즘 2023. 7. 7. 22:31