코드스테이츠 31,32일차 (06월 22일, 06월 23일)

N-Queens

(1) N-Queens 소감

코치님들께서 수강생분들이 가장 어려운 과제가 뭐였는 지 물으면 대답하던 게 N-Queens라고 했다. 확실히 어렵다. 이전 과제들과 달리 긴 코드들을 분석하는 게 힘들고 오래걸렸다. 겨우 파악했다고 생각했는데 막상 문제를 풀려고 하니 막힌다. 테스트 상에서 디버깅은 어떻게 하는 지 몰라 해맸다. 터미널창에서 왜 콘솔로그가 찍히지 않는가하고 고민했었는데, 알고보니 html의 크롬 콘솔로 나왔다. 콘솔창이나 체스판 html 상에서는 문제 없는데 테스트 html은 왜 통과가 안 되냐고 또 시간을 잡아먹었다. 한가지 케이스를 검토하는 함수는 테스트하지 않고 모든 케이스를 검토하는 함수만 호출해서 그런 거였다. 하...과제를 통과하지 못하고 제출한 게 이번이 처음이다. solvers까지 풀려고 애를 썼다면 모를까 board까지만 겨우 끝낸 게 자존심이 상한다. 자료구조, 알고리즘이 약하다고 핑계를 대며 끝내지 않을 생각이다. 이미 정답은 봤지만 혼자서 구현할 때까지 계속 코드 쳐봐야지. 다른 사람이 쓴 코드를 해석하는 게 여전히 힘들다는 걸 느꼈다. 현업에서 신입한테 코드 분석하라고 던져줄 텐데 과연 내가 잘 할 수 있을까 겁난다. 어쩔 수 있나? 그냥 묵묵히 할 뿐. 미리 겁먹지 말고 차근차근 해보자. 알잖아? 2년 전 변수 선언하고 값을 할당하는 게 무슨 소리인지 몰랐던 나에서 성장한 나를 보자. 하다보면 어느 새 깨닫게 된다.

코드스테이츠 33일차 (06월 24일)

CS Hiring Assessment 오답노트

(1) Object.create

let person1 = { name: 'mina', age: 18 };
let person2 = Object.create(person1); // 생성자함수할 때 prototype만 넘겨줘봐서 
				      //일반 객체를 넘겨주면 어떻게 되는지 헷갈렸다. 

person1.name = 'josh';
console.log(person2.name); // 'josh' 이걸 보고 처음엔 person2가 person1의 참조값을 그대로 가리키는 줄 알았다. 
			   //이상하다고 생각했다. prototype 넘길 때 참조값이 다르다고 들었는데??

person2.name = 'ben';
person1.name = 'hans';
console.log(person2.name); // 'ben' 이 나왔다??!! 앞에서는 person1을 변경하면 
			  // person2도 따라 변경되었는데 person2에 name을 직접 수정하니 이제는 변경되지 않는다. 

• console창에서 확인해 본 결과, person1을 기반으로 생성된 person2는 person1에 직접적으로 참조하지 않고 있다. __proto__에 할당한 것 뿐. 이때 person2.name은 prototype chain에 의해 person1의 name의 값을 가져온다.

person1 === person2 // false

• person2에 name 속성을 추가하면 person2.name은 prototype chain에 의해 자신의 속성부터 탐색하는데, person2의 속성에 name이 있기 때문에 더이상 탐색을 중지하고 'ben' 값을 가져온다.

(2) bind

• bind 메소드를 호출 후 그 반환값인 함수를 변수에 저장해주지 않으면 binding해준 함수를 사용할 수 없다.

let person1 = { 
  	name: 'mina',
  	sayHello(){
           console.log(`hello ${this.name}`);
        }
};

let person2 = {
	name: 'josh'
};

person1.sayHello.bind(person2); // bind 한 이유가 없잖어...
person2.sayHello(); // TypeError: person2.sayHello is not a function

(3) Reference Type

• 참조값을 인자로 넘겨줬으니 참조값을 변경하면 원본도 손상될거야하고 잘못 생각했다

let person = { name: 'josh' };

function foo(obj) {    // 파라미터 obj에 person의 참조값 할당
  obj = { age: 10 };   // 파라미터 obj는 person의 참조값 대신 { age: 10 } 객체의 참조값을 가리킴 
}

foo(person); 

Weekend Study

(1) DFS and BFS with undirected, unweighted Graph

아래 내용은 freeCodeCamp_How to Implement 8 Essential Graph Algorithms in JavaScript 중 일부를 번역 정리한 글입니다.

Breadth First Search

• BFS는 한 번에 한 레벨(depth)를 방문한다.
• 이미 탐색한 노드에 재방문을 막기 위해 방문 기록을 Object에 저장한다.
• FIFO 처리를 위해 queue 자료구조를 이용한다.
• 시간 복잡도는 O(V+E)이다.

function BFS
	초기화 : 빈 queue, 빈 result 배열, 빈 visited 객체
    	queue와 visited 객체에 시작 vertex를 추가
    	반복문 시작, queue가 empty가 아닐 때까지 :
    		- 현재 vertex를 queue에서 꺼내고 변수에 보관
        	- 현재 vertex를 result 배열에 추가
        	- 현재 vertex의 인접리스트를 순회
        		- 각각의 인접 vertex가 visited에 없다면 :
            		- 인접 vertex를 visited에 추가
                	- queue에 인접 vertex 추가
   	result 배열 반환 
    

  Graph.prototype.bfs = function(start) {
    const queue = [start]; // 방문한 vertex에 연결된 인접 vertex 중 미방문 여부 확인용
    const result = []; // queue를 거치고 나온 vertex 추가 
    const visited = {}; // 한 번 방문한 vertex 추가 (무방향이기 때문에 중복 체크가 됨)
    visited[start] = true;
    let currentVertex;
    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
}

Depth First Search

• DFS는 깊이(depth)만큼 방문한다.
• LIFO 처리를 위해 stack 자료구조를 이용한다.
• 이웃 vertex들을 stack에 넣고 stack에서 꺼낼 때 방문 기록을 Object에 저장한다.
• DFS를 재귀적으로 호출하여 구현할 수도 있다.
• 시간 복잡도는 O(V+E)이다.

function DFS
	초기화: 빈 stack, 빈 result 배열, 빈 visited 객체
    	stack과 visited 객체에 시작 vertex를 추가
   	 반복문 시작, stack이 empty가 아닐 때까지 :
    		- 현재 vertex를 stack에서 꺼내고 변수에 보관
        	- 현재 vertex를 result 배열에 추가
        	- 현재 vertex의 인접리스트를 순회
        		- 각각의 인접 vertex가 visited에 없다면 :
            		- 인접 vertex를 visited에 추가
                	- 인접 vertex를 stack에 추가 
   	result 배열 반환

Graph.prototype.dfsRecursive = function(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;
    (function dfs(vertex){
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
          if (!visited[neighbor]) {
            return dfs(neighbor);
          }
      })
    })(start);
    return result;
}
Graph.prototype.dfsIterative = function(start) {
    const result = [];
    const stack = [start];
    const visited = {};
    visited[start] = true;
    let currentVertex;
    while (stack.length) {
      currentVertex = stack.pop();
      result.push(currentVertex);
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
}