Big O of Objects

  1. 삽입 O(1)
  2. 제거 O(1)
  3. 탐색 O(n)
  4. 접근 O(1)

Big O of Object mehtods

  1. Object.keys() O(n)
  2. Object.values() O(n)
  3. Object.entries() O(n)
  4. Object.hasOwnProperty("키 이름") O(1)

Big O of Arrays

  1. 탐색 O(n)
  2. 접근 O(1)

Big O of Array methods

  1. push O(1)
  2. pop O(1)
  3. shift O(n)
  4. unshift O(n)
  5. concat O(n)
  6. slice O(n)
  7. splice O(n)
  8. sort O(nlogn)
  9. forEach/map/filter/reduce 등 O(n)

'코딩 테스트 > 알고리즘' 카테고리의 다른 글

Problem Solving Approach  (0) 2020.07.09
자바스크립트. 문자 세기  (0) 2020.07.08
자바스크립트. 정렬 순서  (0) 2020.07.04
자바스크립트. for 반복문 수행시간 비교  (0) 2020.07.04
Big O Notation  (0) 2020.07.02

What is a Type System

Type

값을 갖는 다양한 속성 및 함수을 쉽게 참조할 수 있습니다.

"red"

  1. string
  2. 문자열의 속성과 메서드가 모두 포함된 값입니다.

Types

  1. Primitive Types: number, boolean, void, undefiend, string, symbol, null

  2. Object Types: functions, arrays, classes, objects

왜 우리는 타입을 신경써야 하는가

  1. type은 Typecript Compiler에서 오류를 분석하는 데 사용됩니다.
  2. 유형을 사용하면 다른 엔지니어가 코드에 어떤 값이 있는지 이해할 수 있습니다.

타입스크립트는 무엇인가

자바스크립트 종류

자바스크립트는 표준 자바스크립트인 ES5와 ES6 이상 버전을 의미하는 ESNext 그리고 type을 추가한 타입스크립트입니다.
ES5 -> ES6 -> typescript 포함관계 입니다.

타입 기능 장점

개발자들이 타입 오류가 발생했을 때 자바스크립트 보다 쉽게 대처합니다.
그리고 대규모 프로젝트에서 의사소통을 원활히 합니다.

트랜스파일

타입스크립트는 Typescript Compiler를 통해 ES5 자바스크립트로 변환됩니다.
트랜스파일러는 소스코드를 다른 프로그래밍 언어로 변경할 때 사용하고 바이너리 코드로 바꾸는 컴파일러와 구분하기 위해 사용합니다.

EXNext grammer

yield

function* gen() {
  yield* [1, 2];
}

for (const value of gen()) {
  console.log(value);
}

yield 문은 iterator를 생성할 때 사용합니다.
iterator는 독립적으로 존재하지 않고 iterable를 통해 얻습니다.
iterator를 만드는 iterable을 generator라고 합니다.

Promise, async, await

async function get() {
  let values = new Array();
  values.push(await Promise.resolve(1));
}

Typescript grammer

tuple

let numberArray: number[] = [1, 2, 3]; // 배열
let tuple: [boolean, number, string] = [true, 1, 'a']; // 튜플

abstract data type, algebraic data type

대수 타입은 다른 자료형의 값을 가지는 자료형입니다.

type numberOrString = number | string; // 합집합 타입
type animalAndPerson = Animal & Person; // 교집합 타입
var runningSum = function (nums) {
  let sum = 0;
  let result = new Array();
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    result.push(sum);
  }
  return result;
};

Input: nums = [1,2,3,4]

Output: [1,3,6,10]

Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4]

 

Input: nums = [1,1,1,1,1]

Output: [1,2,3,4,5]

Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]

 

반복문을 사용해 num 값들을 sum에 차례대로 더해준다.

더해줄 때마다 sum을 result 배열에 담아준다.

'코딩 테스트 > LeetCode' 카테고리의 다른 글

Easy) 1512. Number of Good Pairs  (0) 2020.09.15
Easy) 1108. Defanging an IP Address  (0) 2020.09.15
Easy) 771. Jewels and Stones  (0) 2020.09.15
Easy) Shuffle the Array  (0) 2020.09.13
Easy) Kids With the Greatest Number of Candies  (0) 2020.09.13
function solution(board, moves) {
  let answer = 0;
  let basket = new Array();
  for (let i = 0; i < moves.length; i++) {
    let pick = moves[i] - 1;
    let doll = 0;
    for (let j = 0; j < board.length; j++) {
      if (board[j][pick] > 0) {
        doll = board[j][pick];
        board[j].splice(pick, 1, 0);
        break;
      }
    }

    if (doll > 0) {
      basket.push(doll);
    }
    if (basket.length > 1) {
      let last = basket[basket.length - 1];
      let beforeLast = basket[basket.length - 2];
      if (last === beforeLast) {
        basket.splice(basket.length - 2, 2);
        answer += 2;
      }
    }
  }
  return answer;
}

let board = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 3],
  [0, 2, 5, 0, 1],
  [4, 2, 4, 4, 2],
  [3, 5, 1, 3, 1],
];

let moves = [1, 5, 3, 5, 1, 2, 1, 4];

basket: 뽑은 인형을 담는 배열

pick: moves 배열 값으로 선택되는 세로축 번호

doll: 뽑은 인형 번호, 0은 빈 공간


for (let j = 0; j < board.length; j++) {
  if (board[j][pick] > 0) {
    doll = board[j][pick];
    board[j].splice(pick, 1, 0);
    break;
  }
}​

board.length는 인형뽑기 깊이를 의미합니다. 인형 번호가 1 이상이고 빈 공간이 0입니다.

board[j][pick]가 0보다 큰 경우는 인형이 있다는 것이고 doll에 인형 번호를 줍니다.

그리고 splice 함수를 이용해 인형이 있던 자리값을 0으로 바꾸어 줍니다.

인형을 뽑았기 때문에 반복문을 종료합니다.

 if (doll > 0) {
   basket.push(doll);
 }

board에서 인형을 뽑을 때 pick이 지정한 세로축에 인형이 없을 수도 있습니다!!

그러면 doll은 0인 상태인지 확인하고 basket에 인형을 담습니다.

    if (basket.length > 1) {
      let last = basket[basket.length - 1];
      let beforeLast = basket[basket.length - 2];
      if (last === beforeLast) {
        basket.splice(basket.length - 2, 2);
        answer += 2;
      }
    }

basket에 둘 이상이 있어야 뽑은 인형과 바로 전에 뽑은 인형을 비교할 수 있습니다.

방금 뽑은 인형과 이전에 뽑은 인형을 비교해 같다면

basket에서 이 둘을 splice를 이용해 제거합니다. 그리고 두 인형이 제거되었으므로 answer에 2를 더해줍니다.

'코딩 테스트 > 프로그래머스' 카테고리의 다른 글

Level 1 모의고사  (0) 2020.07.08

What does better mean?

1. Faster?

2. Less memory-intensive?

3. More readable?

 

The Problem with Time

1. Different machines will record different times

2. The same machine will record different times

 

다른 performance 측정법

Counting Operations이 있지만 연산자를 세는 방법은

힘들고 시간이 오래 걸린다.

 

Big O 정의

간단한 연산들은 컴퓨터가 최대 f(n)번 해야한다면 알고리즘은 O(f(n))이다.

f(n)은 상수형, 선형 등 형태가 다양하다.

 

1. f(n)이 2n일 때 상수는 무시되고 O(n)이 된다.

2. f(n)의 최고차항만 남긴다.

 

O(1)

O(n)과 같이 보이지만 i가 10 이후부터 연산 개수가 증가하지 않기 때문에 O(1)이다!!

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

 

Space Complexity

boolean, number, undefined, null은 상수이다.

String 공간 복잡도는 O(n)이다.

참조형은 일반적으로 O(n)이고 n은 배열 길이나 object key 개수이다.

+ Recent posts