해시
- 어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있다면 탐색없이 바로 데이터 찾을 수 있다
- key 와 data를 저장해서 빠른 데이터 탐색 (일대일 대응), key 통한 접근 1) 단방향, key → data 가능, data → key 불가능 2) 탐색과정 필요없다 O(1). 3) 변환과정 필요, data→index
해시는 주소록 처럼 사용가능, 값에 대한 “해시 테이블”이 존재하고 테이블의 데이터를 “버킷”이라고 한다
사용분야 - 비밀번호 관리, 데이터베이스 인덱싱, 블록체인
Javascript에서는 Map, Set을 사용하여 해시를 이용한다.
- Map으로 key와 value를 저장
- Set으로 key 만을 저
- Key 값은 언제나 유일
순열(순열, 중복 순열, 조합, 중복조합)
- 서로 다른 n개에서 r개를 뽑아서 순서대로 정렬하는 경우의 수
- 재귀 표현이 반복된다. ( if → 결과ok → output / if → 결과no → 다시 if)
- 원 배열, 잔여배열 을 통해 작업 ( [ㄱ,ㄴ,ㄷ] → [ㄱ],[ㄴ,ㄷ] )
재귀를 사용하여 동일한 작업을 하는 반복 루프를 만들어 원하는 결과값이 출력될때까지 재귀를 수행하도록 한다.
조합
- 순서가 없다. → 순열에서 한 부분만 변경하면 구현 가능하다.
https://velog.io/@rlatp1409/알고리즘-JS-순열과-조합-구현-자바스크립트
탐색
- 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문
DFS(깊이 우선 탐색)
- 루트에서 다음 노드로 넘어가기전에 해당 노드에 대한 분기 완벽 파악
- 모든 노드를 방문하고자 할때, 방문 여부를 반드시 검사해야함 (backtracking)
- 간단 + 느림
큐를 사용하여 정점(시작점) 넣는다.
시작점과 연결된 [ㄱ,ㄴ,ㄷ]에서 ㄱ을 빼고 ㄱ에 연결된 ㄹ를 맨 앞에 넣는다
[ㄹ,ㄴ,ㄷ]에서 위 행동을 반복하여 큐가 빌때까지 재귀 반복
BFS (너비 우선 탐색)
- 인접한 노드 먼저 탐색
- 두 노드 사이의 최단 경로 /임의의 경로 찾고 싶을 때 이 방법 선택
- 재귀적 동작 no ( 반복문 사용)
- 어떤 노드 방문 여부를 반드시 검사
큐를 사용하여 정점(시작점) 넣는다.
시작점과 연결된 [ㄱ,ㄴ,ㄷ]에서 ㄱ을 빼고 ㄱ에 연결된 ㄹ를 맨 뒤에 넣는다
[ㄹ,ㄴ,ㄷ]에서 위 행동을 반복하여 큐가 빌때까지 재귀 반복
DFS, BFS 언제 사용?
DFS - 길의 형태 파악 가능, 경로의 특징 이용
BFS - 최단거리 구하기
https://velog.io/@sean2337/Algorithm-DFS와-BFS의-쉬운-개념-JavaScript-구현-방법
DP (Dynamic Programming) 동적 계획법
- 한번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 (중복여부)
- 두가지 조건
- 큰문제를 작은문제로 나눌수 있다
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일
- 구현 방식
- top-down : 재귀적 구현( + 메모이제이션 )
- botton-up : 반복문 구현 ( + DP 테이블 )
- 시간 복잡도
https://gyyeom.tistory.com/116
Divide and conquer (분할 정복)
- 문제를 2가지 이상으로 나눈뒤 각 문제에 대한 답을 재귀를 이용해 구하고 n가지의 답으로 전체 답을 구하는 방식.
- 일반 재귀와 차이점 → 분할하여 각 문제에 대한 답을 구한다.
- 3가지 구성요소
- 분할(divide)
- 병합(merge)
- 분할 불가한 가장 작은 문제(base case)
- 2가지 조건
- 문제를 나눌수 있는 방법
- 문제를 나눈 후의 효율성
https://blog.naver.com/qpghnv/221580612451
GCD (최대공약수, 최소공배수)
- 최대 공약수 → 두 수의 약수중 가장 큰 정수
let getGCD = (num1, num2) => {
let gcd = 1;
for(let i=2; i<=Math.min(num1, num2); i++){
if(num1 % i === 0 && num2 % i === 0){
gcd = i;
}
}
return gcd;
}- 최소 공배수 → 두 수의 공통 배수 중 가장 작은 수
let getLCM = (num1, num2) =>{
let lcm = 1;
while(true){
if((lcm % num1 == 0) && (lcm % num2 == 0)){
break;
}
lcm++;
}
return lcm
}유클리드 호제법을 이용한 구현
num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다.
- 최대 공약수
let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);- 최소 공배수
- lcm = (num1*num2) / gcd
정리
https://velog.io/@devjade/JavaScript로-최대공약수GCD-최소공배수LCM-구하기
function solution(num1, num2) {
const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
const lcm = (a, b) => a * b / gcd(a, b);
return [gcd(num1, num2), lcm(num1, num2)];
}Array.prototype.sort 정렬
- 문자정렬 → vanilla 사용
- 숫자 오름차순 → (a,b)⇒{ return a-b; } / 내림차순은 b-a
- 비교
- if a가 b보다 작다면 return -1;
- if a가 b보다 크다면 return 1;
- if 같다면 return 0;
https://velog.io/@kim-jaemin420/메서드Array.prototype.sort자바스크립트-정렬함수-sort
