Javascript 알고리즘 사전 | protect-me

내가 보려고 만든 알고리즘 사전 ❤️‍🔥
MDN Object | MDN Array | MDN Set | MDN Map | MDN String

🧙🏻‍♂️ 배열 선언 및 초기화

배열 선언 및 초기화 | declare array | init array | new Array | Array.from | []

---

기본

const n = 20;
const arr = Array(n).fill(1); // 1로 채워진 길이 20의 배열 반환

활용

// graph: 2차원 배열 생성
const graph = Array.from(Array(n), () => Array())
const graph = Array.from(Array(n), () => [])
const graph = Array.from({ length: n }, (_) => []);

const arr = Array.from(Array(m), () => Array(n)) // => m x n 배열
const arr = Array.from(Array(m), () => Array(n).fill(1)) // 1로 채워진 m x n 배열
// 1로 채워진 n개짜리 배열을 m개 선언 => m이 세로, n이 가로로 보임
// 0: (3) [1, 1, 1]
// 1: (3) [1, 1, 1]
// 2: (3) [1, 1, 1]
// 3: (3) [1, 1, 1]

주의

const arr = new Array(n).fill(new Array(m).fill(0))
console.log(arr);
// 0: (4) [0, 0, 0, 0]
// 1: (4) [0, 0, 0, 0]
// 2: (4) [0, 0, 0, 0]

arr[2][2] = 1
console.log(arr);
// 0: (4) [0, 0, 1, 0]
// 1: (4) [0, 0, 1, 0]
// 2: (4) [0, 0, 1, 0]

위와 같이 선언하면 문제 없이 멀쩡해보이지만
arr[2][2] = 1와 같이 한 요소만 바꾸어도 모든 배열이 수정된 것을 볼 수 있음
0으로 구성된 길이 m의 배열을 한 개만 선언한 후에 n에 해당하는 모든 주소에 참조시키기 때문
따라서 바라보고있는 참조값은 모두 같음

추가 : 유사배열 to 객체

Array.from(arrayLikeObject): 유사배열을 객체로 변환

🃏 중복 제거

set | new set | set to array | array to set

---

new Set + [...]

const arr = [1, 1, 2, 2, 2, 3];
const set = new Set(arr); // set 활용
const unique = [...set]; // 전개연산자 활용
console.log(arr); // [1, 1, 2, 2, 2, 3] *원본 유지
console.log(set); // {1, 2, 3}
console.log(unique); // [1, 2, 3]```

indexOf() + filter()

const arr = [1, 1, 2, 2, 2, 3];
const unique = arr.filter((item, index) => {
  return arr.indexOf(item) === index;
});

console.log(arr); // [1, 1, 2, 2, 2, 3]
console.log(unique); // [1, 2, 3]

1. filter를 통해 arr의 요소들을 돌면서 item으로 받음
2. indexOf를 통해 arr에서 처음 등장하는 item의 index를 찾음
3. 현재 item의 index를 비교함
4. 같으면 중복되지 않은 요소이고, 다르다면 중복된 요소
5. 중복되지 않은 요소들만 return

forEach() + includes()

const arr = [1, 1, 2, 2, 2, 3];
let unique = [];
arr.forEach((item) => {
  if (!unique.includes(item)) {
    unique.push(item);
  }
});

console.log(arr); // [1, 1, 2, 2, 2, 3]
console.log(unique); // [1, 2, 3]

1. forEach를 통해 arr의 요소들을 돌면서 item으로 받음
2. unique 배열에 item이 포함되어있지 않으면 push

활용

배열에서 자기 자신과 중복되는 요소를 찾아서 둘 다 제거하는 로직
ex) [1, 3, 3] => [1]

function deleteDup(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] == arr[j]) {
        arr.splice(i, 1)
        arr.splice(j - 1, 1)
      }
    }
  }
  return arr
}

length가 3인 배열에서 다른 값 하나를 찾는 로직
ex) [1, 3, 1] => [3]

arrayX = arrayX.sort();
arrayy = arrayY.sort();

x = arrayX[1] === arrayX[0] ? arrayX[2] : arrayX[0];
y = arrayY[1] === arrayY[0] ? arrayY[2] : arrayY[0];

🧩 Set, Map

set | set.add(push) | set.has(includes) | set.size(length) | for (let item of set) {}
map | map.set(push) | map.has(includes) | map.size(length)

---

Set

Set 객체는 값 콜렉션으로, 삽입 순서대로 요소를 순회할 수 있음.
하나의 Set 내 값은 한 번만 나타날 수 있음
즉, 어떤 값은 그 Set 콜렉션 내에서 유일함.

var mySet = new Set();

mySet.add(1); // Set { 1 }
mySet.add(5); // Set { 1, 5 }
mySet.add(5); // Set { 1, 5 }
mySet.add('some text'); // Set { 1, 5, 'some text' }
var o = {a: 1, b: 2};
mySet.add(o);
mySet.add({a: 1, b: 2}); // o와 다른 객체를 참조하므로 괜찮음!

mySet.has(1); // true
mySet.has(3); // false, 3은 set에 추가되지 않았음
mySet.has(5);              // true
mySet.has(Math.sqrt(25));  // true
mySet.has('Some Text'.toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 5
mySet.delete(5); // set에서 5를 제거함
mySet.has(5);    // false, 5가 제거되었음
mySet.size; // 4, 방금 값을 하나 제거했음
console.log(mySet);// Set {1, "some text", Object {a: 1, b: 2}, Object {a: 1, b: 2}}

-
  
// 순서대로 항목을 (콘솔에) 기록: 1, "some text", {"a": 1, "b": 2}
for (let item of mySet) console.log(item);

// 순서대로 항목을 기록: 1, "some text", {"a": 1, "b": 2}
for (let item of mySet.keys()) console.log(item);
for (let item of mySet.values()) console.log(item);

// Set 객체를 배열 객체로 변환 (Array.from으로)
var myArr = Array.from(mySet); // [1, "some text", {"a": 1, "b": 2}]

// Set과 Array 사이 변환
mySet2 = new Set([1, 2, 3, 4]);
mySet2.size; // 4
[...mySet2]; // [1, 2, 3, 4]

Map

Object의 키는 Strings이며, Map의 키는 모든 값을 가질 수 있다.
Object는 크기를 수동으로 추적해야하지만, Map은 크기를 쉽게 얻을 수 있다.
Map은 삽입된 순서대로 반복된다.

const contacts = new Map()
contacts.set('Jessie', {phone: "213-555-1234", address: "123 N 1st Ave"})
contacts.has('Jessie') // true
contacts.get('Hilary') // undefined
contacts.set('Hilary', {phone: "617-555-4321", address: "321 S 2nd St"})
contacts.get('Jessie') // {phone: "213-555-1234", address: "123 N 1st Ave"}
contacts.delete('Raymond') // false
contacts.delete('Jessie') // true
console.log(contacts.size) // 1

👨‍👦‍👦 복사 및 비교

배열 복사 | 객체 복사 | 클론 | clone | copy | shallow copy
깊은 복사 ► Copy 컴팩트 가이드 | 복사, 클론

---

Copy Array

배열 얕은 복사

const arr = [1, 1, 2, 2, 2, 3];
const copy = arr.slice()
console.log(arr); // [1, 1, 2, 2, 2, 3]
console.log(copy); // [1, 1, 2, 2, 2, 3]
console.log(arr == copy); // false => 참조값이 다름

const arr2 = [[1, 2], [3, 4], [5, 6]];
const copy2 = arr2.slice()
console.log(arr2); // [[1, 2], [3, 4], [5, 6]]
console.log(copy2); // [[1, 2], [3, 4], [5, 6]]
console.log(arr2 == copy2); // false => 참조값이 다름

배열 얕은 복사 주의점

1차원 배열은 깊은 복사가 가능한 것처럼 보이지만 2차원 이상의 배열은 깊은 복사가 불가능함(참조 값을 공유함)

const arr2 = [[1, 2], [3, 4], [5, 6]];
const copy2 = arr2.slice()

console.log(arr2); // [[1, 2], [3, 4], [5, 6]]
console.log(copy2); // [[1, 2], [3, 4], [5, 6]]
console.log(arr2 == copy2); // false
console.log(arr2[0] == copy2[0]); // true, 값이 같음
arr2[0].push(55)
console.log("1 arr2", arr2); // arr2[0]에만 넣었는데
console.log("1 copy2", copy2); // copy2[0] 에도 55가 들어감

arr2[0] = [7, 8] // 완전히 새로운 배열의 참조값을 할당했을 시
console.log("2 arr2", arr2); // [7, 8]
console.log("2 copy2", copy2); // [1, 2, 55]
console.log(arr2 == copy2); // false, 둘은 다른 값이 됨

Copy Object

객체 얕은 복사

const obj = { name: "maison", age: 18 }
const copy = Object.assign({}, obj)
console.log(obj); // { name: "maison", age: 18 }
console.log(copy); // { name: "maison", age: 18 }
console.log(obj == copy); // false => 참조값이 다름

객체 얕은 복사 주의점

Object.assign을 통한 복사는 객체 내부의 객체를 깊이 복사해내지 못하고 참조값을 복사함

const obj2 = {
  name: "maison", age: 18,
  playlist: [
    { singer: "abc", title: "def" },
    { singer: "ghi", title: "jkl" }
  ]
}
const copy2 = Object.assign({}, obj2)
console.log(obj2); // 같은 값
console.log(copy2); // 같은 값
console.log(obj2 == copy2); // false, 참조값은 다름
console.log(obj2.playlist == copy2.playlist); // true, 참조 값이 같음 🚨
obj2.playlist[0].singer = "hell"
console.log(obj2); // ob2의 배열 내 객체를 수정하면
console.log(copy2); // copy2의 배열 내 객체도 함께 변경되어있음

const obj3 = {
  name: "maison", age: 18,
  playlist: { singer: "abc", title: "def" }
}
const copy3 = Object.assign({}, obj3)

console.log(obj3); // 같은 값
console.log(copy3); // 같은 값
console.log(obj3 == copy3); // false, 참조값은 다름
console.log(obj3.playlist == copy3.playlist); // true, 참조 값이 같음 🚨
obj3.playlist.singer = "hell"
console.log(obj3); // ob2의 객체 내 객체를 수정하면
console.log(copy3); // copy2의 객체 내 객체도 함께 변경되어있음

JSON.parse + JSON.stringify

이거 보여주려고 어그로 끌었다

1. JSON.stringify를 통해 JSON 문자열로 변환
2. JSON.parse를 통해 JSON 문자열을 javascript객체로 다시 변환
   (JSON 문자열로 변환했다가 다시 객체로 변환하기에, 객체에 대한 참조가 없어짐)

주의 🚨
1. 다른 방법에 비해서 성능적으로 느림
2. JSON.stringify 메소드가 function을 undefined로 처리함

const arr2 = [[1, 2], [3, 4], [5, 6]];
const copy2 = JSON.parse(JSON.stringify(arr2));

console.log(arr2); // [[1, 2], [3, 4], [5, 6]]
console.log(copy2); // [[1, 2], [3, 4], [5, 6]]
console.log(arr2 == copy2); // false
console.log(arr2[0] == copy2[0]); // true
arr2[0].push(55)
console.log(arr2, copy2); // 둘은 다른 값을 나타냄

내용 비교

참조값이 아닌 원시값을 비교하여 같은 배열 또는 객체인지 확인 가능

// 배열 비교 시, 순서가 상관없다면 비교 전 sort를 수행
JSON.stringify(arr1) === JSON.stringify(arr2) 
JSON.stringify(obj1) === JSON.stringify(obj2)

🔪 String handling

String | 문자 다루기 | slice | substring | split | splice

---

기본

String.slice()

str.slice(beginIndex[, endIndex]) *endIndex를 포함하지 않고 추출함.

const str = 'The quick brown fox jumps over the lazy dog.';
console.log(str.slice(31)); // "the lazy dog."
console.log(str.slice(4, 19)); // "quick brown fox"
console.log(str.slice(-4)); // "dog."
console.log(str.slice(-9, -5)); // "lazy"

String.split()

str.split([separator[, limit]]) *해당하는 문자열 기준으로 나누어 배열로 반환함

const str = 'The quick brown fox';
const words = str.split(' ');
console.log(words); // (4) ["The", "quick", "brown", "fox"]
const chars = str.split('');
console.log(chars[8]); // "k"
const strCopy = str.split();
console.log(strCopy); // ["The quick brown fox"]

활용 : String.splice()

Array에 사용하는 splice 함수는 잘라낸 배열과 자르고 남은 배열을 분리하여 활용할 수 있는 반면
String의 slice 함수는 원본을 수정하지 않기 때문에 자르고 남은 문자열을 알 수 없음

참고 : [stackoverflow] Is there a splice method for strings?

String.prototype.splice = function (index, count, add) {
  var chars = this.split('');
  chars.splice(index, count, add);
  return chars.join('');
}
console.log(str.splice(10, 6)); // "The quick fox"
console.log(str.splice(4, 5, "slow")); // "The slow brown fox"

기타

• substr : 사용 금지
• slice VS substring 차이점

반복문

for | forEach (Array) | for ... of (Array) | for ... in (Object) *key값
JS 반복문 ► javascript 반복문 정리 | for | forEach | for in | for of

---

📈 graph

그래프 | DFS | BFS | 깊이우선탐색 | 너비우선탐색 | 완전 탐색

---

활용

그래프 작성 시, reduce() + concat()을 활용한 코드
이미 있으면 기존의 배열을, 없으면 새 빈 배열을 할당한 후, 합칠 배열을 concat

    const adjList = edges.reduce((G, [from, to]) => {
        G[from] = (G[from] || []).concat(to);
        G[to] = (G[to] || []).concat(from);
        return G;
    }, {});

arr의 요소가 Number인 경우

function deleteDup(arr) {
  const q = {}
  arr.forEach(item => {
    q[String(item)] = (q[String(item)] + 1 || 1);
  })
  for (let key in q) {
    if (q[key] == 1) return key
  }
}

🔁 map, filter, reduce

---

(생략)

기타

Array to Object

['Leo', 'Rui', 'fox', 'tiger'].reduce((a, c, i) => {
  a[i] = c
  return a
}, {}) // {0: "Leo", 1: "Rui", 2: "fox", 3: "tiger"}

Array.concat() && Array.join()

concat return Array
join return String

const elements = ['Fire', 'Air', 'Water'];
console.log(elements.join()); // "Fire,Air,Water"
console.log(elements.join('')); // "FireAirWater"
console.log(elements.join('-')); // "Fire-Air-Water"

변환

String to Number

Number(str)
+str

Number to String

String(num)
num + ''

다이나믹 프로그래밍 | DP

피보나치

자바스크립트로 알고리즘 정리하기 #9 다이나믹 프로그래밍 개념

가장 큰 정사각형 찾기

프로그래머스 - 가장 큰 정사각형 찾기 (javascript)

구조 분해 할당

• 객체

const obj = {
  a: 'hello',
  b: {
    c: 'hi',
    d: {
      e: 'wow'
    }
  }
}

// 기존
const a = obj.a
const b = obj.b
const c = obj.b.c
const d = obj.b.d
const e = obj.b.d.e

console.log(a, b, c, d, e)

// 구조 분해 할당
const { a, b: { c, d: { e }}} = obj
console.log(a, b, c, d, e) // b, d 는 not defined

// 구조 분해 할당 - 개선
const { a, b } = obj
const { c, d } = b
const { e } = d
console.log(a, b, c, d, e) // b, d 는 not defined

• 배열

// 기존
const arr = [0, 1, 2, 3, 4]
const one = arr[0]
const two = arr[1]
const three = arr[2]
const four = arr[3]
const five = arr[4]

// 구조 분해 할당
const [one, two, three, four, five] = arr

// 구조 분해 할당(생략)
const [one, , three, , five] = arr

고차원 함수

기본

$el.addEventListener('click', () => {
  console.log(event.target) // target
})

callback 함수에 event는 브라우저에서 자동으로 삽입해줌

함수 분리

function callback() {
  console.log(event.target) // target
}
$el.addEventListener('click', callback)

callback 함수를 따로 분리한 후,
addEventListener의 callback 함수 자리에 함수를 삽입
함수 자리에 함수가 들어간 적절한 상황임

인수 전달 - 잘못된 예 ⛔️

function callback(event, num) {
  console.log('e', event.target) // undefined
  console.log('n', num) // undefined
}
$el.addEventListener('click', callback(0))

callback(0)를 입력하는 동시에 함수가 실행되고,
callback 함수의 return 값이 명시되어있지 않기 때문에
암시적으로 return undefined가 설정됨.
즉, 함수 자리에 return 값(undefined)이 들어가는 상황으로
$el.addEventListener('click', undefined)와 같아짐
따라서 인수를 전달하고자 할 때에는 아래와 같이 고차원 함수를 활용

인수 전달 - 고차원 함수

function callback(num) {
  return () => {
    console.log('e', event.target) // target
    console.log('n', num) // 0
  }
}
$el.addEventListener('click', callback(0))

$el.addEventListener('click', { console.log... }) 와 같아짐
즉, 함수 자리에 callback 함수의 return 값을 넣는데,
그 return 값이 바로 함수.
따라서 함수 자리에 함수를 넣은 적절한 상황임

인수 전달 - 고차원 함수(2)

function callback(num) {
   console.log('e', event.target) // target
  console.log('n', num) // 0
}
$el.addEventListener('click', () => {
  callback(0)
})

flat / every / some

flat

const arr = [
  ["td", "td", "td"],
  ["td", "td", "td"],
  ["td", "td", "td"],
]
const flatedArry = arr.flat()
console.log(flatedArry); // ["td", "td", "td", "td", "td", "td", "td", "td", "td"]

every

• 모두 만족하면 true, 하나라도 만족하지 않으면 false

const arr1 = [true, true, true, false]
console.log(arr1.every(el => el)) // false
const arr2 = [true, true, true, true]
console.log(arr2.every(el => el)) // true

some

• 하나라도 만족하면 true, 모두 만족하지 않으면 false

const arr1 = [true, true, true, false]
console.log(arr1.some(el => el === false)) // false
const arr2 = [true, true, true, true]
console.log(arr2.some(el => el === false)) // true```

form, input / queryselector, event.target

<form class="wrapper">
  <input id="name-input">
  <input id="age-input">
</form>

const wrapper = document.querySelector('.wrapper')
wrapper.addEventListener('click', () => {
  const name = event.target['name-input']
  console.log(name)
})

javascript 함수 선언 방식

참고

(수정 중)

function myFunc() {
}

myFunc = () => {
}

falsy 처리

또는 | or | '||'

• 앞의 값이 falsy 값이면 뒤의 값(최초의 true값, 없으면 false)

const box = 0
console.log(box || 'here') // here

null 병합 연산자 | '??'

• 앞의 값이 null 혹은 undefined가 아니라면 뒤의 값

const box = 0
console.log(box || 'here') // here
console.log(box ?? 'here') // 0

옵셔널 체이닝 | optional Chaining '?'

• 프로퍼티가 없는 중첩 객체에 에러 없이 안전하게 접근 가능
• ?.은 ?.'앞’의 평가 대상이 undefined나 null이면 평가를 멈추고 undefined를 반환

const obj = {
  name: {
    first: 'protect',
    family: 'me'
  },
  age: '18'
}
console.log(obj.name.first[0]) // p
// console.log(obj.second.first[0]) // 에러: 'first' of undefined
console.log(obj.second?.first[0]) // undefined

fragment

• append는 할 때마다 다시 그려지므로 여러 개를 연속으로 하면 매우 비효율적
• DocumentFragment는 다른 노드를 담는 임시 컨테이너 역할을 하는 특수 목적의 노드
• 가상의 노드 객체로서, 메모리상에서만 존재함
  const $fragment = document.createDocumentFragment()

split

• split 구분자로 여러개 넣기

const exp = '100-200*300-500+20'
const spread = exp.split(/-|\+|\*/)
console.log(spread) // (5) ['100', '200', '300', '500', '20']

📚 참고

---

[Javascript] 배열 중복 제거하는 3가지 방법
자바스크립트 객체 복사하기
[stackoverflow] Is there a splice method for strings?

---

Photo by Marc-Olivier Jodoin on Unsplash