JS 알고리즘 총정리

리린·2021년 10월 7일

알고리즘

목록 보기
1/2

알고리즘 팁

  • 사소한 에러가 나면 그 부분을 알고리즘에 대입하여 생각해보자.

연산

AND OR

and: &&
or : ||

Math 객체 정리

Math.pow(2,10); // 2의 10승 : 1024
Math.round(0.4); // 반올림 : 0
Math.ceil(0.4); // 올림 : 1
Math.floor(0.4); // 내림 : 10
Math.abs(-5); // 절대값 : 5
Math.max(x,y,z); // 가장큰 인자 반환(min도 있음)
Math.random() // 0과 1.0 사이에 임의수 반환
Math.sqrt(4) // 제곱근 반환 : 2
Math.cbrt(x) //x의 세제곱근 반환
Math.exp(x) //e의 x제곱근 값을 반환
Math.log(x) //x의 자연로그 값을 반환.(ln x)
Math.log2(x) //x의 2를 밑으로 가지는 로그 값을 반환
Math.pow(x,y) //x의 y제곱을 반환
Math.sign(x) //x의 부호 값을 반환

증감연산자

++ : 대입 후 더해줌 (p1+=1 과 일치)
-- : 대입 후 빼줌 (p2+=2 와 일치)

배열 합 구하기:reduce 함수

[배열].reduce((누적값, 현재값) => 누적값+현재값, 누적값의 기본값)
..뭔가 배열이 리턴된다.

몫과 나머지 구하기

몫 = parseInt(17/2)
나머지 = 17 % 2

최소수 vs 최대수

최소수: Number.MIN_SAFE_INTEGER
최대수: Number.MAX_SAFE_INTEGER
출처: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MIN_SAFE_INTEGER

for문

기본 for문

for (let i = 1; i <= n; i++){
...
return answer
}

  • 순서가 중요함

forEach

const myArr = [1, 2, 3, 4, 5];
const newMyArr = myArr.forEach((currentElement, index, array) => {
console.log(요소: ${currentElement});
console.log(index: ${index});
console.log(array);
});
console.log(newMyArr); // undefined

  • forEach() 메서드는 배열에 활용이 가능한 메서드로, 파라미터로 주어진 함수를 배열 요소 각각에 대해 실행하는 메서드이다.
  • map() 메서드와 거의 비슷하지만 차이점은 따로 return 하는 값이 없다는 점이다.

for key in 배열

var obj = { a: '가', b: '나', c: '다' };
for (var key in obj) {
console.log(key, obj[key]); // a 가, b 나, c 다
}

for value of 배열

var iterable = [10, 20, 30];
for (var value of iterable) {
console.log(value); // 10, 20, 30
}

  • es6에서 추가됨

for 키 in 배열 vs for 값 of 배열 차이점

break vs continue;

break: for문을 완전히 중단
continue: 현재 순회문을 중단

배열

배열 길이 구하기

arr.length

배열 요소만 출력

배열 값 추가

test.unshift('123');
// 앞에 새로운 배열값 추가
test.push('890');
// 뒤에 새로운 배열값 추가

  • unshift를 하지 말고 차라리 빈 배열일 때 push를 하자

배열값 찾기

const pets = [
{ type: 'Dog', name: 'Max'},
{ type: 'Cat', name: 'Karl'},
{ type: 'Dog', name: 'Tommy'},
]
pet = pets.find(pet => pet.type ==='Dog' && pet.name === 'Tommy');
console.log(pet); // { type: 'Dog', name: 'Tommy' }

배열 출력하기

${answer} : 쉼표로 구분된 값이 나온다
[...answer] :answer이 인덱스를 키로 가진 객체인 경우 배열로 변환된다.

배열 정렬하기

arr.sort((a,b) => a - b) : 오름차순 정렬
arr.sort((a,b) => b-a): 내림차순 정렬

구조분해할당

const [sPosition, ePosition, position] = command

배열 초기화하기

Array.from(
{length: 20}, // 유사배열
() => Array(10).fill(0) // 각각의 배열에 적용할 함수
);

배열 내용만 출력하기

arr.join(", ")

집합

집합 선언

const setA = new Set([1,2,3,4,5,6,7,8]); // array => set 으로 변환 (알아서 중복제거 됨)
const setB = new Set([3,4,5,6,7]);

합집합

const union = new Set([...setA, ...setB]); // set => array spread syntax 사용

교집합

const intersection = new Set([...setA].filter(x => setB.has(x))); // 둘 다 있는 것들을 솎아낸다.

차집합 (A-B / B-A /합집합-교집합)

const difference1 = new Set([...setA].filter(x => !setB.has(x))); // set1 - set2
const difference2 = new Set([...setB].filter(x => !setA.has(x))); // set2 - set1
const symmetricDifference = new Set([...difference1, ...difference2]); // union - intersection

의문

const isSuperSet = function (superset, subset) { // check if left set(superset) is a superset of right set(subset)
for (let element of subset) if (!superset.has(element)) false; // 한 번이라도 superset으로 들어온 집합이 subset으로 들어온 집합의 값을 가지고 있지 않다면 => false
return true;
}

집합에서 배열로 바꾸기

Array.from(tmp).sort((a, b)=>b-a);

문자열

문자열 길이

var browserType = 'mozilla';
browserType.length;

특정 문자열 찾기

browserType[0]; //첫번째 문자
browserType[browserType.length-1]; // 마지막 문자

문자열에서 특정 문자열의 인덱스 찾기

browserType.indexOf('zilla'); // 2 반환

특정 문자열이 포함되지 않은 문자열 찾기

if(browserType.indexOf('mozilla') !== -1) {
// do stuff with the string
}

문자열을 인덱스로 구분하여 출력하기

browserType.slice(0,3); //moz 반환

  • 변경된 값을 리턴해준다( 불변성 유지)

특정 문자부터 끝까지 출력

browserType.slice(2);

  • 변경된 값을 리턴해준다( 불변성 유지)

대소문자 변경

var radData = 'My NaMe Is MuD';
radData.toLowerCase();
radData.toUpperCase();

  • 변경된 값을 리턴해준다( 불변성 유지)

대소문자 확인

대소문자로 변환한 것과 기존 문자열을 비교하여 확인함.

문자열의 일부를 변경

browserType.replace('moz','van');

  • 변경된 값을 리턴해준다( 불변성 유지)

.replace 정규식 사용하기

s.toLowerCase().replace(/[^a-z]/g, '');
: a부터 z가 아닌 것은 ''로 대체하라(=없애라) 는 뜻.

str_text.replace(/./gi, "-")
: 특수 기호를 맨처음 적을 때는 항상 역슬래쉬() 부분이 정규식 맨 앞에 존재 해야함

"4asdf/.asdf/.fsdd4df".replace(/[/4.]/gi, "@"); => @asdf@@asdf@@fsdd@df
: [] 안에 특수기호를 넣으면 하나하나 개별적으로 변환 ..
대괄호 안에 들어 있는 / 과 4와 . 을 개별적으로 하나하나 변환

"asdf/.asdf/.fsdddf".replace(/\/./gi, "@"); => asdf@asdf@fsdddf
: [] 없이 특수기호 여러개를 작성하면 하나의 묶음으로 인식해서 변환

"안녕? Hi! 123456789.0".replace(/[^0-9]/g, ""); =>1234567890
: 숫자가 아닌 문자열을 선택하는 정규식
[a-z] : a ~ z 사이의 문자를 찾음
[^a-z] : a~ z가 아닌 문자를 찾음
[abc] : a, b, c 중 하나를 찾음
[^abc] : a, b, c를 제외한 문자를 찾음
[0 -9]: 0 ~ 9 사이의 숫자를 찾음
[^0 -9]: 0 ~ 9 사이의 숫자가 아닌 문자를 찾음

g : 발생할 모든 pattern에 대한 전역 검색
i : 대/소문자 구분 안함
m: 여러 줄 검색 (참고)

string.padEnd()

const str1 = 'Breaded Mushrooms';
console.log(str1.padEnd(25, '.'));
// expected output: "Breaded Mushrooms........"
const str2 = '200';
console.log(str2.padEnd(5));
// expected output: "200 "

  • 현재 문자열에 다른 문자열을 채워, 주어진 길이를 만족하는 새로운 문자열을 반환합니다. 채워넣기는 대상 문자열의 끝(우측)부터 적용됩니다

끊는 점 기준으로 배열 리턴

const str = 'The quick brown fox jumps over the lazy dog.';
const words = str.split(' ');
console.log(words[3]);
// expected output: "fox"

문자열 배열로 변환하기

const str = "a b c";
const arr = str.split(" ");

  • 단, s[1] 등의 배열 인덱스를 사용가능하긴 하다.

문자열 배열 문자열로 다시 변환하기

const strArr = ['a', 'b', 'c'];
const str = strArr.join('');

문자열 반대로 뒤집기

var name = "의적홍길동";
var nameReverse = name.split("").reverse().join("");

중복 문자 제거

i !==s.indexOf(s[i])

  • 중복된 문자열들은 인덱스 i 와 s.indexOf(s[i]) 이 다르다.
  • indexOf(값)은 값이 처음 나온 index를 리턴하기 때문이다

메서드

arr. forEach(item, index, 배열 그 자체)

arr. map(item, index, 배열 그 자체)

  • 각각 연산을 진행한 것을 모아 배열로 반환해준다
  • map과 forEach의 차이:
    forEach는 콜백함수로서 배열을 변환시키지만 map은 배열을 변환시키지 않는다.
    forEach는 리턴값 대신 undefined를 리턴하지만 map은 메모리를 할당하고 리턴 값을 저장한다

arr. reduce((누적값, item, index, 배열 그 자체)=> 리턴값, 누적값의초기값)

  • 누적값을 반환해준다
  • reducer함수의 반환값은 누적반환값이 아니다. .reducer메서드의 반환값이 누적반환값이다. (만약 전자 식으로 코드를 짜면 에러가 터짐)
  • acc를 리턴을 해줘야 한다.
  • break하는 법: reduce function은 4번째 인자인 array를 mutating하기 때문에 이를 이용해서 종료할 수 있다.
const array = ['12', '34', '56', '78', '99'];
const x = array
.reduce((acc, curr, i, arr) => {
    if(i === 2) arr.splice(1);  // eject early
    return acc += curr;
  }, '');
console.log('x: ', x);  // x:  123456

arr. filter ((item, index, 배열 그 자체, this로 사용할 값) =>리턴값)

  • 함수를 통과한 값만 모아서 배열로 반환해준다.

arr. splice ( 시작 index, 제거 개수, 배열추가 item1, 배열 추가item2, ...)

  • 배열 추가 item이 없다면 삭제만 함
  • 원래 배열을 변형시킴

arr. slice ( 시작 index, 마무리 index ...)

arr.findIndex(함수)

  • filter와 비슷하나 배열 대신 함수에 맞는 index를 배열로 반환

타입 확인 메서드

숫자 or 문자 확인

isNaN('item') //true 반환
isNaN(123) //false 반환

  • isNaN 함수는 숫자일 경우 False, 문자이면 True 를 반환

객체

키 & 값 가져오기

let fruitKeys = Object.keys(objectSample);
let fruitValues = Object.values(objectSample);

예제: 

var objectSample ={
	"APPLE" : "14000",
	"BANANA" : "2000",
	"MELON" : "8000",
	"BAD_APPLE" : "1400",
	"BAD_BANANA" : "200",
	"BAD_MELON" : "800",
}

let fruitKeys = Object.keys(objectSample);
let fruitValues = Object.values(objectSample);

객체 확장 연산자

obj = {...obj, ...pair};

value값으로 key 값 찾기

function getKeyByValue(object, value) {
return Object.keys(object).find(key => object[key] === value);
}

출처: https://velog.io/@try_catch/JS-value%EA%B0%92%EC%9C%BC%EB%A1%9C-key%EA%B0%92-%EC%B0%BE%EA%B8%B0

value 값으로 key 여러개 찾기 (응용)

function getKeyByValue(object, value) {
return Object.keys(object).filter((key) => object[key] === value);
}

알고리즘 유형

해시

출처: https://splendidlolli.tistory.com/270

  • 데이터를 저장할 위치인 '인덱스'를 간단한 연산으로 구하는 것. 이렇게 구한 인덱스를 '해시값'이라고 한다.

  • 시간 복잡도가 O(1)이다. (배열의 단점을 커버한다)

  • 자바스크립트로 해시 구현하기
    https://evan-moon.github.io/2019/06/25/hashtable-with-js/

  • 값이 나올 때마다 객체에 1씩 카운팅하며 저장

dfs

function solution(numbers, target) {
    let answer = 0;
    
    dfs(0, 0);
    
    function dfs(index, sum) {
        if(index === numbers.length) {
            if (sum === target) {
                answer++;
             }
            return;
        }
        
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
    
    return answer;
}
function solution(n, computers) {
    let visited = [false];
    let answer = 0;

    function dfs(i) {
        visited[i] = true;
        for(let j=0; j<computers[i].length; j++) {
            if(computers[i][j]===1 && !visited[j]){
                dfs(j);
            }
        }
    }
    
    for (let i=0; i < computers.length; i++) {
        if (!visited[i]) {
            dfs(i)
            answer++;
        }
    }
    return answer;
}
  • 방문하지 않은 노드를 세면 되는 문제
  • visited 노드로 true/false 추적
  • dfs 함수 선언: 방문한 것은 방문처리하고, 연결된 노드에서 1이 되어있고, 방문처리 되지 않았다면 방문처리하기(dfs)
  • visited 되지 않은 것은 방문처리하고, answer 추가하기

선택정렬

출처: https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

이분탐색

출처: https://im-developer.tistory.com/126

function binarySearch (target, dataArray) {
let low = 0;
let high = dataArray.length - 1;
let mid = Math.floor((high + low) / 2);
while (target !== dataArray[mid]) {
	if (target < dataArray[mid]) {
	high = mid - 1;
	mid = Math.floor((high + low) / 2);
	} else {
	low = mid + 1;
	mid = Math.floor((high + low) / 2);
	}
}
return dataArray[mid];
}

투포인터 알고리즘

p1 p2 사용하기

function solution(arr1, arr2) {
let answer = [];
let n = arr1.length;
let m = arr2.length;
let p1 = (p2 = 0);
while (p1 < n && p2 < m) {
if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
else answer.push(arr2[p2++]);
}
while (p1 < n) answer.push(arr1[p1++]);
while (p2 < m) answer.push(arr2[p2++]);
return answer;
}

  let a = [1, 3, 5];
  let b = [2, 3, 6, 7, 9];
  console.log(solution(a, b));
  • 포인터1= 포인터2=0
  • while 포인터1 < 배열1 길이 && 포인터2 < 배열2 길이
  • 배열1[포인터1], 배열2[포인터2]의 값 비교
  • 각 경우마다 포인터1 or 포인터2를 1씩 증가시킴
  • 마지막으로 남은 게 포인터1일 경우 배열1[포인터1]을 answer에 밀어넣기
  • 마지막으로 남은 게 포인터2일 경우 배열2[포인터2]을 answer에 밀어넣기

lt rt 사용하기 : lt 고정하고 rt에 for문 돌리기

function solution2(m, arr) {
let answer = 0,
lt = 0,
sum = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) answer++;
while (sum >= m) {
sum -= arr[lt++];
if (sum === m) answer++;
}
}
return answer;
}
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
function solution2(m, arr) {
let answer = 0,
sum = 0,
lt = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
while (sum > m) {
sum -= arr[lt++];
}
answer += rt - lt + 1;
}
return answer;
}

슬라이딩 윈도우

  • 시간복잡도 : O(N)
  • 창을 밀고 나가듯이 부분합 등을 구할 수 있다.
  • 창을 미는 방법: 선출후입( 뒤의 원소를 더하고, 앞의 원소를 빼주며 창을 민다)

해쉬맵 (new Map 생성자)

const map1 = new Map([['key1', 'value1'], ['key2', 'value2']]);
const map = new Map([['key1', 'value1'], ['key1', 'value2']]);
map.size : 요소의 개수
map.set(키, 값) : 요소를 추가
map.get(키) : key에 해당하는 값을 가져옴
map.has(키) : 요소 존재여부 확인
map.delete(키) : 요소 삭제 --boolean값 반환 (메서드 체이닝 불가 )
map.clear(): 요소 일괄 삭제
map.foreach((v,k,map)=>console.log(v, k, map)) : value, key, map 전체 순회 가능
map.keys(): 키들 모은 배열 반환
map.values() : 값들 모은 배열 반환
map.entries(): 키와 값이 쌍인 배열을 배열에 넣어 반환

  • for ... of와 스프레드 문법, 배열 디스트럭 등 할당 가능하다
  • 디스트럭:
    const [a, b] = map;
    console.log(a, b); // [{name: "Lee"}, "developer"][{name: "Kim"}, "designer"]
  • 키로 문자열 및 심볼만이 아닌, 객체 포함 모든 값을 키로 사용 가능함

const map1 = new Map([['key1', 'value1'], ['key2', 'value2']]);
console.log(map1); // Map(2) {"key1" => "value1", "key2" => "value2"}
const map2 = new Map([1, 2]); // TypeError: Iterator value 1 is not an entry object
// 중복된 키가 있으면 덮어 써진다.
const map = new Map([['key1', 'value1'], ['key1', 'value2']]);
console.log(map); // Map(1) {"key1" => "value2"}

출처: https://wonjaetech.tistory.com/entry/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-Map

정렬하기

: // sort by value
const mapSort1 = new Map([...myMap.entries()].sort((a, b) => b[1] - a[1]));
console.log(mapSort1);
// Map(4) {"c" => 4, "a" => 3, "d" => 2, "b" => 1}
const mapSort2 = new Map([...myMap.entries()].sort((a, b) => a[1] - b[1]));
console.log(mapSort2);
// Map(4) {"b" => 1, "d" => 2, "a" => 3, "c" => 4}
// sort by key
const mapSort3 = new Map([...myMap.entries()].sort());
console.log(mapSort3);
// Map(4) {"a" => 3, "b" => 1, "c" => 4, "d" => 2}
const mapSort4 = new Map([...myMap.entries()].reverse());
console.log(mapSort4);
// Map(4) {"d" => 2, "b" => 1, "c" => 4, "a" => 3}

기타 테크닉

  • 10진수를 2진수로 변환

    const num = 1384;
    num.toString(2); // "10101101000"
    // 십진수 1384를 이진수로 변환
    parseInt("10101101000", 2).toString(16); //"568"
    // 이진수 "10101101000"를 십진수 1384로 변경하고 다시 16진수로 변환

profile
리린
개발자지망생
다음 포스트

js : binary search

0개의 댓글