21-03-10 자바스크립트로 하는 자료구조와 알고리즘(4)

6장 자바스크립트 객체

자바스크립트가 여러 용도로 사용될 수 있는 이유는 객체 덕분이다
객체 상수 {} 또는 new Object()를 통해 객체를 생성할 수 있다
object.propertyName 또는 object[‘propertyName’]으로 접근할 수 있다
프로토타입을 활용 상속은 자바스크립트의 유일한 상속방법이다

자바스크립트는 동적이고 클래스는 새로운 함수 멤버를 이후에 필요할 때 추가할 수 있기 때문

const classExample = () => {
  this.array = [1,2,3,4,5];
  this.name = "JavaScript";
}

let example1 = new classExample();

classExample.prototype.sayName = function() {
  console.log(this.name);
}
// 동적으로 생성된 객체에 함수를 추가할 수 없다
// example1.prototype.sayName2 = function() {} 같은 것은 불가능

객체의 속성들을 다른 범위에서도 직접 접근할 수 있다
비공개 변수(캡슐화)를 흉내내려면 지역변수를 선언하고 해당 변수에 접근할 수 있는 getter(), setter()를 만들 수 있다

객체에 속성을 추가하기

let obj = {};
obj.example = 'value';
obj['example'] = 'change';
// 어떤 식으로 접근하든 성능상의 차이는 없음

7장 자바스크립트 메모리 관리

V8 자바스크립트 엔진 및 최신 자바스크립트 엔진에는 가비지 컬렉터가 있어 사용하지 않는 변수를 삭제한다
객체에 대한 참조가 있다면 해당 참조는 메모리에 있는 것이고, 객체 내에 저장된 변수를 참조할 때엔 해당 객체 전체를 로딩한다

DOM 항목을 가리키는 변수가 이벤트 콜백 외부에 선언된 경우엔 해당 DOM 항목을 제거하더라도 메모리에 남게 된다

let one = document.getElementById('one');
let two = document.getElementById('two');
one.addEventListener('click', () => {
  two.remove();
  console.log(two); // 삭제 이후에도 two를 참조하게 되므로 메모리 누수가 발생한다
})
/*-------------------------------------*/
let one = document.getElementById('one');
one.addEventListener('click', () => {
  let two = document.getElementById('two'); 
  // 블록 내에서만 사용하도록 처리하면 메모리 누수를 줄일 수 있다
  two.remove();
})
/*-------------------------------------*/
let one = document.getElementById('one');
one.addEventListener('click', () => {
  let two = document.getElementById('two'); 
  // 블록 내에서만 사용하도록 처리하면 메모리 누수를 줄일 수 있다
  two.remove();
})
one.removeEventListener('click');

객체가 window 전역 객체에 포함되는 경우에도 해당 객체는 메모리에 존재하므로 가능하면 전역 변수는 사용하지 않는 것이 좋다

객체 내 하나의 속성만 필욯나 경우 전체 객체를 매개변수로 전달해서는 안된다

let test = { prop : 'test' }
/* 이렇게 구현해서는 안된다
const printProp = (test) => {
  console.log(test.prop)
} 
*/ 
const printProp = prop => {
  console.log(prop)
}
printProp(test.prop);

원치 않는 객체 속성은 delete 연산자로 제거할 수 있다 (객체가 아니라면 작동하지 않는다)

const colorCount = arr => {
  // 함수 밖에서 선언하면 메모리 낭비가 되므로 안에 선언해주자
  let RED = 0, GREEN = 1, BLUE = 2;
  let counter = new Array(3).fill(0);
  for (let i = 0, arrLen = arr.length; i < arrLen; i++) {
    let curr = arr[i];
    if (curr === RED) {
      counter[RED]++
    } else if (curr === GREEN) {
      counter[GREEN]++
    } else if (curr === BLUE) {
      counter[BLUE]++
    }
  }
  return counter;
}

8장 재귀

재귀함수는 대개 분할 정복에 사용된다
재귀함수를 사용하려면 점차 기저 조건 에 접근하는 분할 정복 방식 으로 구성하여야 한다

피보나치 수열은 대표적인 예

// for문을 활용한 함수
const getFibo = n => {
  if (n <= 1) return n;
  let sum = 0, last = 1, lastlast = 0;
  for (let i = 1; i < n; i++){
    sum = lastlast + last;
    lastlast = last;
    last = sum;
  }
  return sum;
}

const getFibo = n => {
  if (n <= 1) return n
  else return getFibo(n-1) + getFibo(n-2);
  // n-1 = last, n-2 = lastlast 인 셈
}

꼬리재귀를 이용한 구현

const getFiboBetter = (n, lastlast, last) => {
  if (n === 0) return lastlast;
  if (n === 1) return last;
  return getFiboBetter(n-1, last, lastlast + last)
}

파스칼의 삼각형

const pascalTriangle = (row, col) => {
  if (col === 0) return 1;
  else if (row === 0) return 0;
  else 
    return pascalTriangle(row - 1, col) + pascalTriangle(row -1, col - 1);
}

삼항연산자를 이용한 파스칼의 삼각형

const pascalTriangle = (row, col) => {
    return (col === 0) ? 1 
            : (row === 0) ? 0 
                : pascalTriangle(row - 1, col) + pascalTriangle(row -1, col - 1);
  }

재귀의 빅오 분석은 점화식 을 분석해야한다
이 점화식을 분석할 때 마스터 정리 를 자주 사용한다
→ T(n) = aT(n/b) + O(n^c) (단, a >= 1 , b >= 1)
→ a는 재귀호출에 곱해지는 계수이고 b는 로그 항임
→ 비재귀 요소인 O(n^c)의 c가 logb(a)보다 작다면 T(n) = O(n^3)
→ c가 logb(a)와 같은 경우엔 T(n) = O(nlog(n))
→ c가 logb(a)보다 크다면 T(n) = O(n^2)

10진수를 2진수로 변환하기

// 1. base condition
const base10ToString(n) {
  let binaryString ='';

  function base10ToStringHelper(n) {
    if (n < 2) {
      binaryString += n;
      return;
    } else {
      base10ToStringHelper(Math.floor(n/2));
      base10ToStringHelper(n%2);
    }
  }
  base10ToStringHelper(n);

  return binaryString;
} // 시간 복잡도 O(log2(n));

배열의 모든 순열 출력하기

// 1. base condition : beginIndex === endIndex;
const swap = (strArr, index1, index2) => {
  let temp = strArr[index1];
  strArr[index1] = strArr[index2];
  strArr[index2] = temp;
}

const permute = (strArr, begin, end) => {
  if (begin === end) console.log(strArr);
  else {
    for (let i = begin; i < end + 1; i++){
      swap (strArr, begin, i);
      permute(strArr, begin + 1, end);
      swap(strArr, begin, i);
    }
  }
}

const permuteArray = strArr => {
  permute(strArr, 0, strArr.length - 1);
}

객체 펼치기

const dictionary = {
  'Key1' : '1',
  'Key2' : { 
    'a' : '2',
    'b' : '3',
    'c' : {
      'd' : '3',
      'e' : '1'
    }
  }
}

const flattenDictionary = dictionary => {
  let flattenedDictionary = {};

  function flattenDictionaryHelper (dictionary, propName) {
    if (typeof dictionary != 'object') {
      flattenedDictionalry[propName] = dictionary; 
      return;
    }
    for (let prop in dictionary) {
      if (propName === '') 
        flattenDictionaryHelper(dictonary[prop], propName+prop);
      else
        flattenDictionaryHelper(dictonary[prop], propName+'.'+prop)
    }
  }
  flattenDictionaryHelper(dictionary, '');
  return flattenedDictionary;
} // 시간 복잡도 O(n)

회문 검사하기

const isPalindrome = word => {
  return isPalindromeHelper(word, 0, word.length - 1);
}

const isPalindromeHelper = (word, beginPos, endPos) => {
  if (beginPos >= endPos) return true;
  if (word.charAt(beginPos) !== word.charAt(endPos)) return false
  else return isPalindromeHelper(word, beginPos + 1, endPos - 1);
}

21-03-10 자바스크립트로 하는 자료구조와 알고리즘(4)

6장 자바스크립트 객체

7장 자바스크립트 메모리 관리

8장 재귀

Harry Kim