숫자 오름차순 순서로 수도코드를 짰음.

정리하다 보니 더 나은 방법이 떠올랐기 때문에 현재로써는 n queens가 가장 효율적임.(n rooks도 그 방법으로 할 예정)

1. findNRooksSolution()

: returns a single solution to the n-rooks problem

2. countNRooksSolutions()

: returns a count of the total number of solutions to the n-rooks problem

3. findNQueensSolution()

: returns a single solution to the n-queens problem

4. countNQueensSolutions()

: returns a count of the total number of solutions to the n-queens problem

1. Inheritance & Polymorphism

• Inheritance(상속): 상위 객체의 특징을 하위 객체에게 넘겨주는 것
• Polymorphism(다형성): 동일한 조작방법으로 동작을 시키지만, 작동 결과는 다른 것

2. Prototype

2-1. Prototype Object

• prototype 객체:
  • constructor에 의해 생성될 각각의 인스턴스에게 공유. 프로퍼티를 제공하기 위해 사용
  • 함수.prototype, 객체.__proto__(dunder proto)로 접근 가능하다.
• dunder proto덕분에 프로토타입 체이닝이 가능해짐

프로토타입 객체가 뭔지.

프로토타입

프로토타입 체이닝, 왜 가능해지는지

2-2. Prototype chaining

scope chaining처럼, 메서드 혹은 속성을 찾지 못했을 경우 상위 프로토 타입을 참조하는 것.

3. Subclassing patterns

3-1. Functional Subclassing

var car = function (loc) {
    var obj = { loc: loc };
    obj.move = function () {obj,loc++ };
    return obj;
}

var Van = function (loc) {
    //super class의 instance에 이 subclass만의 method를 할당.
    var obj = Car(loc);
    obj.grab = function () { ... };
    return obj;
}

var Cop = function (loc) {
    var obj = Car(loc);
    obj.cal = function () { ... };
    return obj;
}

쓸모없는 메모리 소모가 많아짐. > 각 function마다 함수들을 다 만들기 때문이다.

3-2. Pseudoclassical Subclassing

ES6에서 class가 생기기 전에 subclass를 구현하기 위해 만들었던 방법

3-3. ES6 class Subclassing

3. Subclass Dance party

line up: 반드시 상속을 이용하여 구현해야 함.

hint: 무조건 그대로 사용하기보다는 필요하다면 자식클래스에서 메서드 확장을 통해

4. QnA

Q1.

화살표 함수와 무명함수는 this바인딩이 다르기 때문에 사용되는 부분이 다르다.

1. 자바스크립트?

prototype기반의 언어.

ES5까지는 class가 없었음. > sudo-classical

ES6부터 calss 지원(하지만 그렇다고 해서 JS가 프로토타입 기반의 언어인 것은 변하지 않았음.)

2. prototype 상속

2-1. __proto__: 프로토타입을 확인할 수 있다.

function Human(name) {
    this.name = name;
}
let steve = new Human('steve');
steve.__proto__ === Human.prototype; //true

Q1. 아래 코드가 실행되는 이유는?

var Human = function(name) {
    this.name = name;
}
Human.prototype.sleep = function() {};

var steve = new Human('steve');
steve.toString(); // [object Object]

Human.__proto__에는 toString()이 없음. 하지만 Human의 기본형인 Object에는 toString()이 존재함. (모든 객체는 Object를 상속받음)

steve.__proto__.__proto__ === Object.__proto__; //true

2-2. JS에서 상속 구현하기

1) .__proto__에 .prototype대입: 상속이 아님

var Human = function(name) {
    this.name = name;
}
Human.prototype.sleep = function() {
    console.log('zzz');
}

var Student = function() {}
Student.prototype.learn = function() {
    console.log('배우는 중...');
}

var student1 = new Student();
student1.__proto__ = Human.prototype; //Error는 안생기지만 이렇게 쓰지 않는 것이 좋다.

__proto__프로퍼티는 참조의 용도로만 사용해야 한다. (변형하지 않아야 함)

그리고 위와 같이 쓰면 student1변수 하나만의 prototype만 변하는 것이기 때문에 Student에 할당한 것이 아니다.

2) .prototype에 .prototype 대입: 상속이 아님

var Human = function(name) {
    this.name = name;
}
Human.prototype.sleep = function() {
    console.log('zzz');
}

var Student = function() {}
Student.prototype.learn = function() {
    console.log('배우는 중...');
}


var student1 = new Student();

위와 같이 쓰는건 MyArray.prototype이 Array.prototype을 참조하는것이 되어버려서 할당이 아니다.

3)Object.create()사용

var Human = function(name) {
    this.name = name;
}
Human.prototype.sleep = function() {
    console.log('zzz');
}

var Student = function(name) {
    Human.call(this, name); //혹은 apply 사용
    //현재 Student의 prototype에 constructor가 없는 상태이다.
    //그렇기 때문에 Human의 constructor를 받아와야 한다.
    //Human의 constructor는 Student의 상태를 모르기 때문에 call이나 apply를 사용해서 현재의 this를 넣어줘야 한다.
}

Student.prototype = Object.create(Human.prototype);
Student.prototype.constructor = Student;
Student.prototype.learn = function() {
    console.log('배우는 중...');
}

var student1 = new Student('first');
student1.learn(); //배우는 중...
student1.sleep(); //zzz

참고

CodeStates Immersive Course

YOU DON'T KNOW JS(this와 객체 프로토타입, 비동기와 성능) - 카일 심슨 [한빛미디어]

1. Prototype

자바스크립트는 Java, C++과 같은 클래스 기반 객체지향 프로그램이 아니고 프로토타입기반의 객체지향 언어이기 때문에 프로토타입이 매우 중요하다.

ES5까지는 class가 없었음. > class구현을 위해 sudo-classical 등장

ES6부터 calss를 지원하기는 하지만 모양만 class같은것 뿐이지 다른 언어의 class들과는 작동 방식이 다르다.(JS는 prototype기반의 언어이기 때문에!)

• 자바스크립트의 모든 객체는 [[Prototype]]이라는 인터널 슬롯(internal slot)를 가진다. [Prototype]]의 값은 null 또는 객체이며 상속을 구현하는데 사용된다. [[Prototype]] 객체의 데이터 프로퍼티는 get 액세스를 위해 상속되어 자식 객체의 프로퍼티처럼 사용할 수 있다. 하지만 set 액세스는 허용되지 않는다.
• [[Prototype]]의 값은 Prototype(프로토타입) 객체이며 __proto__ accessor property로 접근할 수 있다. __proto__ 프로퍼티에 접근하면 내부적으로 Object.getPrototypeOf가 호출되어 프로토타입 객체를 반환한다.

1-2. [[Prototype]] vs prototype 프로퍼티

prototype 프로퍼티는 프로토타입 객체를 가리키는 [[Prototype]] 인터널 슬롯은 다르다. prototype 프로퍼티와 [[Prototype]]은 모두 프로토타입 객체를 가리키지만 관점의 차이가 있다.

• [[Prototype]]
  • 함수를 포함한 모든 객체가 가지고 있는 인터널 슬롯
  • __proto__로 접근이 가능하며 객체의 입장에서 자신의 부모 역할을 하는 프로토타입 객체를 가리키며 함수 객체의 경우 Function.prototype를 가리킨다.
• prototype 프로퍼티
  • 함수 객체만 가지고 있는 프로퍼티이다.
  • 함수 객체가 생성자로 사용될 때 이 함수를 통해 생성될 객체의 부모 역할을 하는 객체(프로토타입 객체)를 가리킨다.

2. constructor 프로퍼티

프로토타입 객체는 constructor 프로퍼티를 갖는다. 인스턴스의 프로토타입을 만든 Object 함수의 참조를 반환한다.

참고

YOU DON'T KNOW JS(this와 객체 프로토타입, 비동기와 성능) - 카일 심슨 [한빛미디어]

[Poiemaweb] 프로토타입

[MDN] Object.prototype.constructor

1. Solution9-10

1-1. Deep copy & Shallow copy

1) Deep copy

• 원시 타입(primitive type)
• String, Boolean, Number 등 구조가 비교적 단순한 타입
• 복사가 일어날 때 독립적이고 새로운 메모리 공간을 확보하여 값을 저장.

2) Shallow copy

참조타입이 독립적인 값을 저장하지 않는 이유: 비효율을 방지하기 위해서

• 참조 타입(reference type)
• Object, Array, Function 등 구조가 비교적 복잡한 타입
• 복사가 일어날 때, 메모리 어딘가에 객체 그 자체가 아닌 객체의 위치 값을 저장

2. ES6 기능(개인적으로 알아봄)

2-1. ES6: 추가된 원시타입 symbol

[Poiemaweb] 7번째 타입 심볼(symbol)

[MDN] Symbol

변경 불가능한 원시 타입!

주로 이름의 충돌 위험이 없는 유일한 객체의 프로퍼티 키(property key)를 만들기 위해 사용함.

2-2. ES6: 계산된 프로퍼티명(Computed Property Names)

YOU DON'T KONW JS (this와 객체 프로토타입, 비동기와 성능) - 카일 심슨 [한빛미디어] 70p

ES6부터 계산된 프로퍼티명(Computed Property Names)이라는 기능이 추가되었으며 Symbol에서 많이 사용할 수 있을 것!

var prefix = "foo";
var myObject = {
    //prefix + "bar": "hello",
    //위와 같이 사용하면 예상하지 못한 '+'라며 SyntaxError가 뜬다.
    [prefix + "bar"]: "hello",
    //하지만 위와 같이 []로 계산식을 묶어주면 Error가 뜨지 않는다!!!
    [prefix + "baz"]: "world"
};

myObject["foobar"]; //hello
myObject["foobaz"]; //world

이제 object의 key값을 넣을 때 에도 계산을 할 수 있다!!!

1. Checkpoint 9

Q7. After the following code runs, what will be the value of myArray?

var myArray = [2, 3, 4, 5];
function doStuff(arr) {
  arr = [ ];
}

doStuff(myArray);

예상: []

정답: [2, 3, 4, 5]

Q9. After the following code runs, what will be the value of player?

var player = { score: 3 };

function doStuff(obj) {
  obj = {};
}

player = doStuff(player);

예상: {score:3}

정답: undefined

Q8은 []로 안바꼈으면서 Q9는 왜 undefined인지 모르겠다.

왜냐?? object는 array와는 다르냐????? array도 object기반인데 왜?

---

191120(수) 추가 doStuff의 return값이 명시되어 있지 않기 때문에 undefined가 return된다. 그래서 위 코드를 거치게 되면 player의 값이 undefined가 됨.

Q10. After the following code runs, what will be the value of example?

var obj = { 
  inner: { x: 10 }
};
var example = obj.inner;
obj.inner   = undefined;

예상, 정답: { x: 10 }

2. Checkpoint 10

Q1. After the following code runs, what will be the value of result?

var x = 10;

function f () {
  x = x + 1;
  return x;
}

function add (x, y) { return x + y; }

var result = add(x, f());

예상, 정답: 21

Q4. After the following code runs, what will be the value of result?

var x = 10;

function f () {
  x = x + 1;
  return x;
}

var obj = {
  func: f,
  g: f(),
  h: x,
};

obj.func();
var result = obj.g;

예상: 12

정답: 11

Q8. After the following code runs, what will be the value of result?

var x = 10;

var obj = {
  y: x,
  z: obj.y + 1
};

var result = obj.z;

예상: 11

정답: Throws an error

1. Time Complexity 2

1-1. O(1): constant time

입력데이터의 크기와 상관 없이 언제나 일정한 시간이 걸리는 알고리즘

F(n) {
    return (n[0] === 0) ? true : false;
}

1-2. O(n): linear time

입력데이터의 크기와 비례해서 시간이 증가하는 알고리즘

function F(n) {
    for (let i = 0; i < n.length; i++) {
        conosole.log(i);
    }
}

1-3. O(n^2): quadratic time

function F(n) {
    for (let i = 0; i < n.length; i++) {
        for (let j = 0; j < n.length; j++) {
            console.log(i + j);
        }
    }
}

1-4. O(nm)

function F(n, m) {
    for (let i = 0; i < n.length; i++) {
        for (let j = 0; j < m.length; j++) {
            console.log(i + j);
        }
    }
}

Compleity Analysis

알고리즘을 실행하는 것에 있어 시간과 공간을 얼마나 차지하는지 나타내는 지표

시간과 공간의 복잡도: 그 알고리즘의 효율을 나타냄

1. 시간복잡도

<- 효율적 ------------------------------------------------ 비효율적 ->

시간복잡도를 알 수 있으면 알고리즘의 실행시간이 얼마나 걸릴지 예상해 볼 수 있다.

2. 자료구조별 시간복잡도

해시테이블 추가: O(1)

Binary Search: O(log n)

Linked List: O(n)

재귀함수: O(c^n)

2-1. Array

메모리가 정해져있는 배열이라고 가정함.(JS는 아님)

• Lookup (position): 정해져 있는 자리에 저장되어 있는 데이터를 바로 불러오는 것이기 때문에 O(1)
• Assign: Lookup과 마찬가지로 정해져 있는 자리에 있는 값을 변경하면 되는 것이기 때문에 O(1)
• Insert: insert하고 싶은 자리에 insert를 하기 전에 그 자리의 index와 같거나 큰 index를 가진 값들은 다 뒤로 한 칸 씩 물러나야 하기 때문에 O(n)
• Remove: Insert와 비슷하게 삭제하고 싶은 자리의 데이터를 삭제하고 그 자리의 index보다 큰 값을 가진 index의 데이터들을 다 한 칸씩 앞으로 당겨야 하기 때문에 O(1)
• Find(value): 처음부터 원하는 값을 찾을 때 까지 하나씩 비교해나가야 하기 때문에 O(n)

2-2. Linked List

• Lookup: 바로 접근을 하지 못하기 때문에 헤드에서부터 원하는 수만큼 next를 타고 들어가야 한다. 그래서 O(n)

• Find, Assign: Lookup과 같이 원하는 값을 찾을 때 까지 next를 타고 찾아야 하기 때문에 O(n)

• Insert (추가하고 싶은 자리의 앞에 해당하는 node의 주소를 알고 있을 경우)

  ​ : 바로 추가할 수 있기 때문에 O(1)

• Remove

  • head, tail: 가장 앞, 뒤의 node를 지워버리면 되기 때문에 O(1)
  • middle: 지우고자 하는 node의 바로 앞에 있는 node를 알 수 없기 때문에 그 node는 head에서부터 찾아나가야 한다. > O(n)

1) Doubly-Linked Lists

node가 next node를 가리키는것 뿐만 아니라 pre node도 가리킴.

• Lookup, Find, Assign: O(n)
• Insert: O(1)
• Remove: 지우고자 하는 node의 다음node뿐만 아니라 이전node까지 알 수 있기 때문에 Insert와 같이 O(1)

2-3. Tree

1) Basic Tree

• find: 일반 tree의 경우 모든 child를 찾아야 하기 때문에 O(n)의 시간복잡도를 가진다.

2) Binary Search Tree

• find:

  • 입력 데이터의 분포가 고른 편이다:
    • 모든 노드가 일정한 규칙을 가지고 데이터가 저장되기 때문에 O(log n)
  • 입력 데이터의 분포가 고르지 않다:
    • root보다 작은 수의 값만 입력될 경우 linked list와 다를 것이 없기 때문에 O(n)
  • 해결 방법
    • 추가할 때 마다 밸런스를 확인하고 그걸 맞춰가면 O(log n)
    • 이진트리 root깊이가 2이상 차이가 날 경우 트리를 비틀어서 밸런스를 맞추면 됨.

• array를 사용하지 않고 BST를 사용할 경우 그 이유는?

  • array는 메모리에서 연속적인 블락을 차지
  • BST의 경우 구성 시 Linked List를 쓰기도 하는 등 메모리 사용을 효율적으로 할 수 있음.

2-4. Hash Table

• 추가: O(1) 해시 테이블은 for나 while등의 루프를 도는 자료구조가 아니기 때문에 constante한 시간 복잡도를 가진다.

1. Checkpoint 5 & 6

1-1.bind()

call(), apply()와 bind()의 차이.

=> bind()는 함수를 실행하지 않고 this 바인딩만 한 뒤, 함수를 반환한다. : 함수를 실행하지 않음!

바인드에도 우선순위가 있나요? => 예, 있습니다. 레퍼런스로 올리겠음.

JS this 바인딩 우선순위

1-2. 5-Q9

var name = "Window";
var alice = {
  name: "Alice",
  sayHi: function() {
    alert(this.name + " says hi");
  }
};
var bob = { name: "Bob" };


alice.sayHi.bind(bob);

setTimeout(alice.sayHi(), 1000);

bind()는 일시적이다.

1-3. 비동기와 동기함수의 차이

setTimeout은 비동기 함수: 백그라운드에서 기다리다가 콜백함수를 실행

Callback Queue는 Call Stack이 비워진 후 실행된다.

자바스크립트 비동기 처리와 콜백 함수

2. Sprint Office Hour

알아보기: 참조타입, 원시타입 비교

1. Linked List

191119(화) 추가 removeHead에서 다른 곳에서 참조하는 것이 없는 node는 GC(Garbage Collector)가 처리해 준다.

2. Tree

• Tree 클래스

  • node : 데이터 저장
  • child : array

• .addChild(value) : tree에 값이 value 인 자식 node 추가.

  1. 값이 value 인 새로운 Tree 생성.
  2. this.child에 새 Tree를 push.

• contains(target) : target이 tree에 존재하는지 확인.

타이핑하다가 손으로 하는 게 더 빠를 것 같아 손으로 썼음.

191118(월) 추가 constains함수의 child탐색의 경우 2.의 2)부분을 저렇게 하면 안된다. 저걸 쓸 때는 이상한걸 못느꼈는데 코드를 짜려고 보니 말도 안돼서 그부분은 갈아엎었다.

1. Linked List

• node: 데이터와 다음 링크를 저장하는 변수를 저장하는 object 를 뜻함

• head: 첫번째 노드를 가리키는 변수

• tail: 마지막 노드

• insert(): 리스트에 데이터를 저장

  • 원하는 위치에 데이터를 저장할 수 있다.

• remove(): 리스트의 데이터를 삭제

  • 원하는 위치에 있는 데이터를 삭제할 수 있다.

2. Graph

• Alice, Bell, Chris와 같은 사람들(파란 원): 정점(vertex), node
• 사람들 사이의 연락망(빨간 선): 간선(edge)

무방향 그래프: 간선의 방향이 없는 그래프

• Bell이 Finn에게 연락할 수 있는 방법
  1. Bell - Chris - Dominic - Eli - Finn
  2. Bell - Chris - Eli - Finn
  3. Bell - Alice - Dominic - Eli - Finn
  4. Bell - Alice - Dominic - Chris - Eli - Finn

방향 그래프: 간선의 방향이 있는 그래프

• Bell이 Finn에게 연락할 수 있는 방법
  1. Bell - Chris - Eli - Finn
  2. Bell - Alice - Dominic - Chris - Eli - Finn

방향그래프가 무방향그래프보다 구현이 더 간단하다.

• 무방향그래프는 방향이 지정되어있지 않기 때문에 양방향의 edge의 정보를 모두 저장해줘야 한다.

• node: { Alice, Bell, Chris, Dominic, Eli, Finn } 총 6개의 node
• edge: { <Alice, Bell>, <Alice, Dominic>, <Bell, Chris>, <Chris, Dominic>, <Chris, Eli>, <Dominic, Eli>, <Eli, Finn> } 총 7개의 edge
• Graph: 그래프
• node와 관련된 method
  • addNode(): 그래프에 노드 추가
  • contains(): 그래프의 노드에 전달인자가 존재하는지 확인
  • removeNode(): 노드 삭제
• edge와 관련된 method
  • addEdge(): 그래프에 edge추가
  • hasEdge(): 그래프의 노드에 전달인자와 같은 edge가 있는지 확인
  • removeEdge(): edge 삭제

3. Tree

계층적 관계(Hierarchical Relationship)를 표현하는 자료구조

그래프의 종류 중 하나. node의 수 = edge의 수 + 1 의 특징을 갖는 그래프이며 가지를 늘려가며 뻗어나기기 때문에 Tree 라는 이름이 붙었다.

HTML의 DOM이 대표적인 tree구조이다!

위 그림에서 A는 B, C, D라는 자식을 가지고 있다.

마찬가지로 B는 E, F를 C는 G를 D는 H, I, J를 자식으로 가지고 있다.

이렇게 보면 js Object의 prototype과 비슷한 것 같다는 생각이 든다.

• root node(최상위 노드): 트리 구조에서 최상위에 존재하는 노드.
  • 위 그림에서는 A
• terminal node(단말 노드) or leaf node(잎사귀 노드): 아래로 다른 노드가 연결되어 있지 않은 노드.
  • 위 그림에서는 E, F, G, H, I, J
• internal node(내부 노드): 단말 노드를 제외한 모든 노드.
  • 위 그림에서는 B, C, D

• tree클래스: node(데이터)와 child들을 저장할 Object가 필요하다.
• addChild(): tree에 자식node추가.
• contains(): 전달인자가 tree에 존재하는지 확인.

4. Binary Search Tree

4-1. Binary Tree(이진 트리)

• 루트 노드를 중심으로 두 개의 서브트리로 나눠진다.
• 나눠진 두 서브 트리도 모두 이진 트리여야 한다.

트리는 level, height, Sub Tree(서브 트리)를 가지고 있다.

• level: 트리의 깊이. root의 level은 0이다.
• height: 트리의 높이. 트리의 level이 0부터 시작하기 때문에 height와 트리의 최대 level은 같다.
• Sub Tree: 큰 트리에 속하는 작은 트리

Binary Tree(이진 트리)

위와 같은 트리도 이진 트리다.

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주하기 때문!

Full Binary Tree(포화 이진 트리)

Full Binary Tree(포화 이진 트리)

• 모든 레벨이 가득 차 있는 트리를 포화 이진 트리라고 한다.

Complete Binary Tree(완전 이진 트리)

Complete Binary Tree(완전 이진 트리)

• 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 빈 틈 없이 노드가 채워진 이진 트리.

4-2. Binary Search Tree(이진 탐색 트리)

이진 탐색 트리는 이진 트리와는 조금 다르다.

모양은 같지만 이진 트리와는 달리 데이터 삽입 시 전처리 과정을 거친다.

• 이진 탐색 트리는 root node 기준으로 그보다 작은 수는 left에, 큰 수는 right에 저장된다. 편의상 root node를 root라고 하겠다.
  • 위의 그림에서 '9'의 경우를 살펴보자.
    • root의 값은 10이다. '9'는 '10'보다 작기 때문에 left에 저장되기 위해 root.left를 살펴본다.
    • 하지만 root.left에는 '8'이라는 노드가 이미 존재한다. 그러므로 '8'과 '9'를 비교한다. '9'는 '8'보다 크기 때문에 '8'에 해당하는 노드의 right에 저장된다.
    • root.left.right에 '9'가 저장된다.
  • '4'의 경우를 살펴보자.
    • root의 값 '10'. '4' < '10' => left를 향한다.
    • root.left에 노드 존재. root.left와 '4'를 비교한다. '4' < '8' => root.left의 left로!
    • 이럴수가 root.left.left에도 노드가 있다! 당황하지 말고 다시 해당 노드와 '4'를 비교해 보자. '4' > '3' => root.left.left의 right로!
    • root.left.left.right에 '4'가 저장된다.

• tree클래스
  • node: 데이터
  • left: node보다 작은 값을 저장할 object
  • fight: node보다 큰 값을 저장할 object
• insert(value): value값을 저장한다. 저장 과정은 위를 참고.
• contains(value): value값이 tree에 포함되어있는지 확인한다.
• depthFirstLog(): 깊이 우선 탐색(DFS)을 한 결과를 array형태로 출력한다.

4-3. DFS(Depth First Search)

DFS는 Depth First Search로 말 그대로 깊이 우선 탐색을 뜻한다.

이진트리에서는 노드에 적혀 있는 숫자의 오름차순으로 탐색 한다.

5. Hash Table

Hash Table: 크기가 크거나 숫자가 아닌 데이터를 저장하기 좋은 데이터 구조.

key들(숫자가 아니어도 상관 없음)은 hash function을 거치면 특정한 숫자가 된다. 여기서 A키는 언제 어디서 hash function을 거치더라도 같은 숫자를 출력한다.

hash function을 거친 key의 특정 숫자를 저장소의 사이즈만큼 나머지 연산을 한 결과값에 해당하는 index에 데이터를 저장한다.

여기서 데이터는 linked list의 형식으로 저장된다.

• storage: 크기가 변하지 않는 저장소이다. index마다 개별의 linked list가 존재한다.
  • 편의상 storage의 크기는 n이라고 하겠다.
• hash function(key): key값을 입력하면 hash 알고리즘의 결과를 출력한다. 출력값은 반드시 숫자형이어야 하며 같은 key값을 입력했을 때 출력값도 동일해야 한다.
  • 출력값이 골고루 나올수록 좋은 hash function이다.
• insert(key, value): storage( hash function(key)%n )에 value를 저장한다. (linked list 형식)
• retrieve(key): key값을 기준으로 해당하는 value를 찾는다.
• remove(key): key값을 기준으로 해당하는 value를 삭제한다.

참고

윤성우의 열혈 자료구조 - 윤성우 [ORANGE MEDIA]

[VISUALGO]

[Khan Academy: 그래프 설명하기]

[자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기 - 엔지니어대한민국(YouTube)

Q1. 코드 실행 후 result 값?

var obj1 = { x: 10 };

var obj2 = Object.create(obj1);

var result = obj2.x;

[ o ] 10

[ ] 20

[ ] 30

[ ] undefined

console.log(obj1 === obj2.__proto__); //true

Object.create(obj1); 의 리턴값은 .__proto__가 obj1을 가르키는 빈 객체

Q6. 코드 실행 후 result 값?

var obj1 = { x: 10 };

var obj2 = Object.create(obj1);

obj2.x += 10;
obj1.x = 15;

var result = obj2.x;

[ ] 10

[ o ] 20

[ ] 25

[ ] 30

[ ] undefined

obj2.x += 10; 의 경우 obj2.x = obj1.x + 10 과 같기 때문에 이전까지 비어있던 obj2에 obj2.x: 20라는 속성이 생김

1. Stack

상자를 쌓듯이, 먼저 들어간 것이 나중에 나온다. FILO(First-In, Last-Out)

아래는 stack의 전반적인 진행을 그림으로 표현한 것이다.

1-1. Property

• top: 요소를 삽입/ 삭제하는 위치(index)
• maxSize: 저장소의 최대 크기
• stackArray: 저장소

1-2. Method

• push(): 새 요소를 마지막에 추가한다. 반환값 없음.
• pop(): 마지막 요소를 삭제한다. 삭제한 요소 출력.
• empty(): 저장소가 비어있는지 확인한다. 비어있으면 true, 아니면 false
• size(): 저장되어 있는 데이터가 몇 개 인지 반환한다.

1-2. Pseudo Code

• top은 0으로 초기화

• push()

  1. stackArray를 확인한다.
     1. stackArray가 가득 차 있다 > Overflow출력 후 method 나가기
     2. stackArray가 가득 차 있지 않다 > 다음으로 진행
  2. top 의 위치에 해당 요소를 삽입한다.
  3. top값을 1 증가시킨다.

• pop()

  1. stackArray를 확인한다.
     1. stackArray가 비어있다 > Underflow출력 후 method 나가기
     2. stackArray가 비어있지 않다 > 다음으로 진행
  2. top의 위치에 있는 요소를 method 내부 변수에 저장하고 삭제한다.
  3. top값을 1 감소시킨다
  4. 삭제된 요소(method의 내부 변수에 저장했던 요소)를 반환 후 method를 나간다.

• empty()

  1. stackArray의 0번째 index부터 top까지의 for문을 만든다
     1. stackArray(i)가 존재하면 false를 반환한다.
     2. for문을 진행한다
  2. true를 반환한다.

• size()

  • empty()와 유사하게 작성하면 된다.

- 사용 예

• 뒤로가기 버튼
• 콜스택

2. Queue

줄을 섰을 때 먼저 기다린 사람이 먼저 나가는 것과 같은 선입선출 구조. 먼저 들어간 것이 먼저 나온다. FIFO(First-In, First-Out)

아래는 queue의 전반적인 진행을 그림으로 표현한 것이다.

2-1. Property

• front: 가장 오래된 요소의 index
• rear: 새로운 요소가 들어갈 index === 가장 최근 요소 index의 + 1
• queueArray: 저장소

2-2. Method

• push(): 새 요소를 추가한다. 반환값 없음.
• pop(): 가장 오래된 요소를 삭제한다. 삭제한 요소 출력.
• empty(): 저장소가 비어있는지 확인한다. 비어있으면 true, 아니면 false
• size(): 저장되어 있는 데이터가 몇 개 인지 반환한다.

2-3. Pseudo Code

• front와 rear는 0으로 초기화.

• push()

  1. queueArray를 확인한다.
     1. queueArray가 가득 차 있다 > Overflow출력 후 method 나가기
     2. queueArray가 가득 차 있지 않다 > 다음으로 진행
  2. rear 의 위치에 해당 요소를 삽입한다.
  3. rear값을 1 증가시킨다.

• pop()

  1. queueArray를 확인한다.
     1. queueArray가 비어있다 > Underflow출력 후 method 나가기
     2. queueArray가 비어있지 않다 > 다음으로 진행
  2. front의 위치에 있는 요소를 method 내부 변수에 저장하고 삭제한다.
  3. front값을 1 증가시킨다
  4. 삭제된 요소(method의 내부 변수에 저장했던 요소)를 반환 후 method를 나간다.

• empty()

  1. queueArray의 0번째 index부터 queueArray의 크기까지의 for문을 만든다
     1. queueArray(i)가 존재하면 false를 반환한다.
     2. for문을 진행한다
  2. true를 반환한다.

• size()

  • empty()와 유사하게 작성하면 된다.

- 사용 예

• 프린터
• 콘서트 티켓팅 대기열

참고

윤성우의 열혈 자료구조 - 윤성우 [ORANGE MEDIA]

• 자료구조?

  • 데이터를 어떻게 효율적으로 조직, 관리, 저장할 것인지
  • 데이터 값의 모임, 또는 데이터 간의 관계, 데이터에 적용할 수 있는 함수

• 수도 코드(Pseudo Code)?

  • 프로그램을 작성할 때 프로그램이 작동하는 논리를 표현하기 위한 콬드
  • 특정 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드

1. Procedural Language, Object-Otiented language

1-1. 절차지향 언어(Procedural Language)

• 프로그램 안에 있는 것들의 관계를 설정하는 언어.

1-2. 객체지향 언어(Object-Otiented Language)

• 프로그램을 유지하는 모든 것이 오브젝트로 이루어지도록 만들어진 언어.
  • 컴퓨터 프로그램을 명령어의 목록으로 보는 시각에서 벗어나 여러 개의 독립된 단위인 객체들의 모임으로 파악하고자 하는 것.
• 유연하고 변경이 용이함.
• 배우기 쉽고, 개발과 보수가 간편하고, 보다 직관적인 코드 분성을 가능하게 함.

1) 객체 Object 란?

• 데이터와 기능을 논리적으로 묶어 놓은 것.
• 컨테이너
  • 컨테이너의 내용물은 시간이 지나면서 바뀔 수 있지만, 내용물이 바뀐다고 컨테이너가 바뀌는 건 아님. => 여전히 같은 객체
  • 재사용성이 높음

2) OOP?

• 인간이 사물을 이해하는 방식을 반영하도록 설계됨.

• Class를 기반으로 동일한 특성과 기능을 가진 instance 객체를 생성한다.

  • 예
  • 인스턴스(instance): 클래스를 기반으로 생성한 객체

2. OOP Basic Concepts

2-1. Encapsulation 캡슐화

• 속성들을 쌓아서 모아두는 것.
• Reduce complexity + increase reusability

2-2. Inheritance 상속

• 새로운 클래스가 기존의 클래스의 자료와 연산을 이용할 수 있게 하는 기능.
• 자식 클래스는 부모의 속성을 상속받는다.
• Reduce complexity + isolate impact of change

2-3. Abstraction 추상화

• 불필요한 정보는 숨기고 중요한 정보만을 표현함으로써 프로그램을 간단히 만드는 것.
• 추상화: 복잡한 상태이더라도 사용자의 사용은 간편하다.
• Eliminate redundant code

2-4. Polymorphism 다형성

• 어떤 한 요소에 여러 개념을 넣어 놓는 것.
  • 일반적으로 오버라이딩(같은 이름의 메소드가 여러 클래스에서 다른 기능을 하는 것)이나 오버로딩(같은 이름의 메소드가 인자의 개수나 자료형에 따라서 다른 기능을 하는 것)을 의미함.
• 여러 형태이다.
• Refactor ugly switch/case statements

3. JS에서 Object 생성하기

3-1. Functional

var Car = function() {
  var someInstance = {};
  someInstance.position = 0;
  someInstance.move = function() {
    this.position += 1;
  }
  return someInstance;
};

var car1 = Car();
var car2 = Car();
car1.move();
console.log(car1); // {position: 1, move: ƒ}
console.log(car2); // {position: 0, move: ƒ}

3-2.Functional Shared

3-3. Prototypal, Preudoclassical

1) Prototypal는 {}와 같다.

const obj1 = Object.create(Object.prototype);
const obj2 = {};

1) Prototypal, Preudoclassical 비교

// Preudoclassical
const Car = function (color) {
    this.color = color;
}

const car1 = new Car('red'); //생성자가 실행됨
const car2 = Object.create(Object.prototype); //생성자가 실행 안됨: Object의 prototype만 가져오는 것.

const Car = function (color) {
    this.color = color;
}

Car.prototype = {
    getColor() {
        return this.color;
    }
}

const ToyCar = function() {};

ToyCar.prototype = Object.create(Car.prototype);

const LegoCar = new ToyCar();

• object.create로 할 수 있는 것: 생성자의 확장.(상위클래스의 method가 하위클래스에 복사됨)

더 알아보기: prototype chain

4. JS에서의 Prototype

참고

1. CodeStates Immersive Course
2. 러닝 자바스크립트 - 이선 브라운 [한빛미디어]
3. YOU DON'T KNOW JS(this와 객체 프로토타입, 비동기와 성능) - 카일 심슨 [한빛미디어]
4. wikipedia[객체 지향 프로그래밍]
5. [Javascript ] 프로토타입 이해하기

1. Check Point3 문제풀이

[ o ] : 정답

[ x ] : 내가 선택한 답 = 틀림

Q1. 'this' 키워드

[ ] The function that is currently being invoked.

[ o ] An object that the invoked function points to when executing.

[ ] A variable used for lexical scope lookup.

1. this: 함수가 아님

2. 호출된 함수가 실행할 때 가리키는 특정 객체입니다.

3. 정적 스코프 lookup에 사용되는 변수가 아닙니다.

lexical scope: static scope(선언될 때 저장되는 스코프)

[lexical scope] https://stackoverflow.com/questions/1047454/what-is-lexical-scope

Q2. 코드 실행 후 result?

var x = 10;
var strangeAdd = function (y) {
  var x = 20;
  return this.x + y
};

result = strangeAdd(10);

[ ] 10

[ o ] 20

[ ] 30

[ ] NaN

this가 정의된 곳과는 무관하게 실행되는 지점이 글로벌영역이기 때문에 result 의 this는 window이다. 그렇기 때문에 window.x를 불러오기에 답이 20이 된다.

Q3. 내 프로그램에서 'this' 키워드의 의미 결정 방식?

[ x ] Look to the function in which it is defined — that’s what the context is bound to.

[ o ] Look to where the function is called at call time to determine how it is called and evaluate from there.

1. 함수가 정의되어있는 문맥이 아닌 실행 방식에 따라 결정됨.
2. this는 함수가 실행될 때 실행되는 방식에 따라 결정됨.

Q4. 'this'에 적용되는 다섯가지 패턴?

1. global this: window
2. function 호출: window
3. method 호출: 부모 object (function의 부모는 window이기 때문에 사실상 2와 3은 같음)
4. new 연산자로 생성된 function영역의 this: 새로 생성된 객체(Construction Mode)
5. .call()이나 .allpy()호출: 첫번째 인자로 명시된 객체

Q5. 코드 실행 후 콘솔?

function foo(){
  console.log(this);
}

foo();

[ ] foo

[ ] console

[ ] A reference error will be thrown.

[ o ] Window or the global object.

this: free function invocation

전역에서 foo를 불렀기 이 this는 window가 된다.

Q6. 코드를 실행 후 콘솔?

var obj = {
  foo: function(){
    console.log(this);
  }
}

obj.foo();

[ x ] foo

[ ] console

[ o ] obj

[ ] window or the global object.

여기서의 this: 부모 객체

(닷노케이션 기준 왼쪽의 객체가 this가 된다고 보면 됨.)

Q7. 코드 실행 후 콘솔?

var obj = {
  foo: function(){
    console.log(this);
  }
}

var fn = obj.foo;
fn();

[ x ] foo

[ ] console

[ ] obj

[ o ] Window or the global object.

free function invocation : this = window

fn이 function() { console.log(this); }가 되는것이기 때문에 이 this가 free function invocation이 됨.

obj.foo()의 경우에는 함수를 불러오는 것이 아니니 method invocation이다.

var fn = obj.foo 의 위치가 중요한게 아니고 fn()의 실행 시점이 중요함.

this에서는 실행 위치가 중요함

Q8. 코드 실행 후 콘솔?

var obj = {
  foo: function(){
    console.log(this);
  }
}

var obj2 = {
  foo: obj.foo
}

obj.foo.call(obj2);

[ x ] foo

[ ] console

[ o ] obj2

[ ] window or the global object.

.call()이나 .apply()의 경우 실행시점에서 this의 값이 정해지는 것이 아니라 명시적으로 값을 정할 수 있다.

QnA

Q. JS에서의 주소

A. js에서는 주소 관리를 GC에서 하기 때문에 주소의 개념보다는 레퍼런스 참조의 개념으로 이해하는게 나을 것이다.

Q. Arraw function

A.

// function scope를 발생시키지 않음
const fn = () => {
}

// function scope 발생
const fn2 = function () {  
}

2. Sprint Review

2-1. JS- runtime(node)

JS runtime: JS가 실행되는 환경(js가 실행되는 환경에 따라 조금씩 다름)

내가 하려고 하는 것이 실행되지 않으면 실행하고자 하는 환경에서 지원이 되는지를 확인해야 함.

대표적인 환경: node vs browser

​ version이 존재함.

2-2. nvm: node version manager

필요한 이유: 버전에 따라 실행되는 코드가

node관리매니저가 많은데도 nvm을 사용하는 이유: 가장 편리하기 때문

$nvm install > 다운

$nvm ls > 여러 노드 버전이 뜸

$nvm use > 바로 버전이 변경됨

use로 node의 버전을 바꾸더라도 터미널 종료 후 다시 켜면 default버전으로 변경됨.

​ => 쭉 변경해서 사용하고 싶다면 default를 변경해야함

최신버전을 사용하지 않고 LTS(longterm support)를 사용하는 이유: LTS가 안전화된 버전이기 때문이다.

​ => 하위호환성이 뛰어나다.

2-3. *gitflow

remote: 내 컴퓨터가 아닌 곳

​ github

local:

• $git remote -v => origin
  • clone 받아 온 repo를 기본적으로 오리진이라고 잡음.
• $git remote add pair
  • remote환경에 pair의 URL 추가
• $git push origin master
  • origin: remote 이름
  • $git push 1 master 식으로 해당 remote환경에 push 가능
    • github repository의 설정에서 권한을 주어야 push 가능
• $git pull remote pair(remote 이름) master
  • repo의 기본 권한이 read이기 때문에 별다른 권한이 없어도 읽어올 수 있다.

3명이서 pair프로그래밍을 진행할 때

• 항상 나는 내 remote에 올리고 다른 사람들이 그걸 받아오는 형식으로 진행해야 함.

2-4. linting

• lint: 코드 룰()

  • 따르지 않으면 오류를 냄(prettier처럼 강제로 바꿔주지는 않음)

• prettier: 코드 형식, 모양(같은 문법을 어떻게 보여줄지의 형식)

  • 오류를 내지는 않고 자동으로 그 모양으로 바꿔줌

=> 같이 연결해서 쓴다면 저장할 때 원하는 방식으로 코드가 저장이 된다.(lint대로 prettir가 고쳐줌)

'this' keyword

• 모든 함수 scope 내에서 자동으로 설정되는 특수한 식별자
• execution context의 구성 요소 중 하나로, 함수가 실행되는 동안 이용할 수 있다.

- this의 종류

외워둬야 함

1. global this

: window

this //=> Window {...}

2. function invocation(호출)

: window

function foo() {
    console.log(this);
}
foo() //=> Window {...}

3. method invocation

: 부모 object

var obj = {
    fn: function() { console.log(this); }
}
obj.fn() //=> {fn: f}

• var obj2 = {
      hello: {
          fn: function() { console.log(this); }
      }
  }
  obj.hello.fn() //=> {fn: f}
  //method invocation의 this: 바로 자기 위의 부모만 가져옴

3, 4는 사실상 같은 의미

4. construction mode(new 연산자로 생성된 function 영역의 this)

: 새로 생성된 객체

function Car(brand, name, color) {
    this.brand = brand;
    this.name = name;
    this.color = color;
}
Car.prototype.drive = function() {
    console.log(this.name + '가 운전을 시작합니다');
}
let myCar = new Car('chrysler', '300c', 'black');
myCar.color; //'black'
myCar.drive; //'300c가 운전을 시작합니다'

5. .call() or .apply() invocation

: .call(), .apply()의 첫번째 인자로 명시된 객체

function identify() {
    return this.name.toUpperCase();
}
function speak() {
    var greeting = "Hello, I'm " + identify.call(this);
    console.log(greeting);
}
var me = { name: "Rami" };
var you = { name: "Reader" };

identify.call( me ); // RAMI
identify.call( you ); // READER
speak.call( me ); // Hello, I'm RAMI
speak.call( you ; // Hello, I'm READER

1) .call()과 .apply()의 차이

var add = functrion (x, y) {
    this.val = x, y;
}
var obj = {
    val: 0
};

add.apply(obj, [2, 8]);
console.log(obj.val); // 10
add.call(obj, 2, 8);
console.log(obj.val); // 10

* .apply()를 사용하는 이유

var arr = [2, 10, 1, 0, 4];
Math.max(2, 10, 1, 0, 4); // 10
Math.max.apply(null, arr); //10

1. QnA

Q. 함수선언부에 있는 변수는 파라미터고 함수호출할때 넣는값을 아규먼트인가요?

A. 네.

Q. 크롬의 개발자 도구를 사용하지 않고 간단히 콘솔창을 실행할 수 있는 프로그램?

A. runjs

Q. 클로저 설명(외부의 context에 접근할 수 있는 함수를 클로저라고 함)에서 변수라고 쓰지 않고 context라고 사용하는 이유?

A. context: 변수는 좁은 의미이기 때문에

• 커링: 함수 하나가 n개의 인자를 받는 대신, n개의 함수를 만들어 각각 인자를 받게 하는 방법.

• 클로저 단점: 변수가 참조되고 있으면 계속 그 메모리를 유지하게 되어서, 필요하지 않을 때 참조를 끊어줘야 합니다

2. 깃

2-1. 깃의 장점

1. 버전 관리가 편리하다

2. 백업이 용이하다

3. 협업하기에 좋다

   • 한 번 보면 좋을 URL: [github에서 설명한 github] https://youtu.be/w3jLJU7DT5E

2-2. 간단한 깃 워크플로우

• 각자 하나의 코드를 포크해오기

• 페어의 원격 저장소와 내 로컬 저장소 연결

• 코드를 push

• 코드를 pull

• 레포지토리의 구조

• 더 공부해보기

  • git init

  • branching에 대해 알아보기

  • 자주 쓰이는 git 명령어

    • merge, fetch, stesh ...

3. Linting & Testing

3-1. linter

​ 일관적 코딩을 위해. ​ 읽기 좋은 코드 = 유지, 보수하기 좋은 코드

3-2. Tester

​ 작성한 코드가 제대로 동작하는지 자동화하여 테스트해주는 툴 ​ mocha, jest, ... ​ => 프로젝트의 의도를 확인할 수 있음

1) Jest 사용

• test커맨드 지정

• test명령어 만들기 & 사용하기

  { ...
  
  "test:recursion": "jest recursion-review",
  
  "test:watch": "jest --watch",
  ...}

  • "test:recursion": "jest recursion-review"를 사용하는 방법

    1. $npm test recursion
    2. $npm run test:recursion

  • test:watch의 --watch : cli옵션 중 하나.

• toBe : === toEqual : ==

2) QnA

Q. 글로벌에 Jest, 혹은 ESlint가 설치되어 있는지 확인하는 방법

*A.

$npm list -g --depth=0*

Q. global로 설치한 jest 언인스톨 하는 방법

*A.

$nom uninstall -g jest*

4. Tip

• .eslintrc.js

  • 숨김파일: 터미널에서 ls로 볼 수 없음.
  • ls로 보고싶다면
    • $ls -a

• .eslintrc.json

  • 오류를 무시하는 방법: 마우스 갖다댔을 때 뜨는 부분에서 Quick Fix... 클릭 후 설정하면 됨.

• .gitignore

  • git을 사용할 때 무시할 파일들을 정리해 둠.

• yarn과 npm의 차이 in 2019