1. 해싱과 암호화 (1) 해싱 [자료구조] 해시테이블 1. 해시테이블이란 js의 객체와 같다고 생각하면된다. 해시테이블은 객체와 마찬가지로 키-값 쌍을 저장하는데 사용한다. 배열과는 다르게 해시테이블은 순서를 가지지 않는다. 값을 찾거나, 새 diary-blockchain.tistory.com 해싱이란 원본 문자열을 다른 값으로 변환시키는 것이다. 즉, 원본 문자열을 내가 미리 짜놓은 해시 알고리즘을 거쳐 다른 값으로 나오게 하는 것이다. 해시 알고리즘을 통해 길이가 매우 긴 문자열도 내가 정해놓은 틀에 맞춰 변형시킬수 있다. 동일한 문자열은 동일한 해시 알고리즘을 사용하면 동일한 해시값을 생성해야한다. 서로 다른 문자열은 동일한 해시 알고리즘을 사용하면 서로 다른 해시값을 생성해야 한다. 해싱이 완료..

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..