개발/자료구조
[알고리즘] 동적 프로그래밍
1. 동적프로그래밍 문제를 더 작은 조각으로 나눈 다음에 앞에 위치한 조각을 기억하는것을 통해서 해야하는 작업의 양을 줄이는 방식으로 문제를 푸는 접근법이다. 사용 조건 최적 부분구조가 존재하는지, 반복되는 하위 문제가 있는지를 확인하고 사용할 수 있다. 문제에 어떤방식으로든 중첩되는 하위 문제들이 있어야 한다. 이 말은 한문제를 더 작은 문제들로 나눌수 있고 그 조각들중 일부가 재활용이 가능하다는 말이다. 최적부분 구조 하위 문제의 최적 해답을 통해서 더 큰 범주의 문제의 최적 해답을 구성할 수 있는 경우 해당 문제가 최적 부분 구조를 가진다고 한다. 예시) 피보나치 수열은 5번째의 수를 찾기 위해 4번째수와 3번째수를 이용한다. 2. 피보나치 function fib(n) { if (n
[자료구조] 다익스트라 알고리즘 (길찾기)
1. 다익스트라 알고리즘 다익스트라의 이름을 딴 알고리즘으로 그래프의 두 정점사이에 존재하는 최단경로를 찾는 알고리즘이다. 그래프를 가로지르면서 순회하고 우선순위큐를 사용한다. gps, 네트워크 라우팅, 전염병 등등 많은 부분에서 씅니다. 2. 우선순위큐 class PriorityQueue { constructor() { this.values = []; } enqueue(val, priority) { this.values.push({ val, priority }); this.sort(); } dequeue() { return this.values.shift(); } sort() { this.values.sort((a, b) => a.priority - b.priority); } } 3. 다익스트라 알고리..
[자료구조] 그래프
1. 그래프란? 그래프란 노드와 연결이 있는 집합체를 말한다. 트리, 연결리스트 등 대부분의 자료구조는 그래프로 이루어져있다고 해도 무방하다. vertex(정점) : 노드를 가리킨다 edge(간선) : 노드들을 연결하는 선 그래프는 SNS, 지도기능, 라우팅 알고리즘 등 많은곳에서 쓰인다. 어디에서나 사용하고 있다고 봐도 될만큼 쓰임새가 다양하다. 2. 그래프 종류 (1) 무방향 그래프 정점끼리의 간선에 방향이 없는것을 말한다. 방향이 없다는건 양쪽으로 연결되어 있다는 것이다. (2) 방향 그래프 간선에 방향이 부여되어 있다. 간선은 양쪽을 가리킬수도 있고 한 방향만 가리킬수도 있다. (3) 비가중 그래프 각 간선에 부여된 값이 없다. (4) 가중그래프 각 간선에 값이 부여되어 있으며 이를 활용하여 여러..
[자료구조] 해시테이블
1. 해시테이블이란 js의 객체와 같다고 생각하면된다. 해시테이블은 객체와 마찬가지로 키-값 쌍을 저장하는데 사용한다. 배열과는 다르게 해시테이블은 순서를 가지지 않는다. 값을 찾거나, 새로운 값을 찾거나, 값을 제거하는데 매우 빠르다. 모든 언어들은 해시테이블의 구조를 가지고 있다. 2. 해시함수 조건 (1) 속도 무언가를 찾아내거나 바꾸거나 제거하기 위해 접근할때마다 해시 함수를 실행시켜야 하기 때문에 해시함수는 빨라야 한다. (2) 일관성 일관된 방식으로 분배를 해서 다른 값들과 겹치지 않게 해야 한다. (3) 결정론적 특정 입력값을 입력할때마다 같은 출력값이 나와야 한다. 3. 해시함수 구현 function hash(key, arrayLen) { let total = 0; let WEIRD_PRI..
[자료구조] 우선순위큐
[자료구조] 이진힙 - BinaryHeap 1. 이진힙이란? 힙이란 모양은 트리와 같다. 트리와는 다르게 힙은 부모와 자식간의 규칙이 있다는 것이다. 최대 이진힙에서는 부모노드가 항상 자식노드보다 큰 값을 가진다. 왼쪽이나 오른쪽 diary-blockchain.tistory.com 1. 우선순위큐 리스트 또는 구조 즉 우리가 데이터를 저장한곳에서 한번에 하나씩 요소를 가지고 온다. 한번에 하나씩 처리를 한 다음에 그 다음것을 처리하게 되는데 병원에 있는 응급실과 비슷하다. 많은 사람들이 대기하고 있고 모두에게는 어느정도의 우선순위가 부여된다. 그러면 간호사나 의사가 와서 한번에 한사람을 그 우선순위에 따라 데려가는것이다. 서로 다른 우선순위를 가지는 데이터나 정보를 관리할 필요가 있거나 무언가를 입력하는..
[자료구조] 이진힙 - BinaryHeap
1. 이진힙이란? 힙이란 모양은 트리와 같다. 트리와는 다르게 힙은 부모와 자식간의 규칙이 있다는 것이다. 최대 이진힙에서는 부모노드가 항상 자식노드보다 큰 값을 가진다. 왼쪽이나 오른쪽 상관없이 한 레벨 아래에 있는 자식 노드보다 항상 부모 노드가 크다. 형제들 사이에는 특별한 규칙이 없다. 최소 이진힙에서는 그 반대이다. 부모 노드가 언제나 양쪽의 자식보다 작다. 이진힙은 언제나 가장 적은 공간을 차지한다. 2. 최대 이진힙 구현 (1) 클래스 class MaxBinaryHeap { constructor() { this.values = []; } } (2) insert insert(element) { this.values.push(element); this.bubbleUp(); } (3) bubble..