section 2를 시작했다. 이제 고작 5일 공부했는데 정말 많은 내용들이 쏟아졌다. 재귀는 처음 접했을 때 이게 무엇인가 싶었는데 배우면 배울수록 재미있었다. 하지만 내 맘대로 돌아가지는 않아서 아주 밀당의 천재인 것 같다😱 알듯 말듯 애간을 태우는게 공부를 많이 해서 뿌셔야될 것 같다. 하지만 여기서 끝나지 않고 자료구조의 늪에 빠져버렸다. 공부하면 할 수록 점점 더 어려워지는게 아주 골치아팠다. 그래도 어느정도 이해는 되고 코드를 조금씩 쓸 수 있을 정도는 된 것 같지만, 여기서 끝내면 나중에 따라가지 못할 것 같으니 공부를 더 해서 뿌셔할 것 같다. 뿌셔야할게 정말 많은 일주일이였다😡
앞으로 더 많은 내용들을 배우고, 어렵겠지만 공부량을 더 늘려서 확실하게 잡고 가야겠다. 스터디에 들어가게 되었는데 정말 좋은 선택이였다. 몰랐던 부분들을 서로 알려주면서 혼자 공부할 때 보다 훨씬 깨우치는 부분이 많은 것 같다. 덕분에 자극제가 되니 공부를 section1 보다 더 열심히 하게 되는 것 같다. 좌절하지말고 계속해서 복습하다보면 내것이 될테니 포기하지 않도록😐
6주차 배운 내용 중 정리하고 싶은 내용
[JS/Node] 객체 지향
-
객체향프그래밍이란?
하나의 모델이 되는 청사진(class)를 만들고, 청사진을 바탕으로 한 객체(instance)를 만드는 프로그래밍 패턴
-
인스턴스를 만들 때에는 new 키워드 사용 - 각각의 인스턴스는 클래스의 고유한 속성을 갖음
-
prototype: 모델의 청사진을 만들 때 쓰는 원형객체
-
constructor: 인스턴스 초기화될 때 실행하는 생성자 함수 -
this: 함수가 실행될 때, 해당 scope마다 생성되는 고유한 실행 context (인스턴스 객체)
class 활용
[부모로부터 상속받을 때]
const Grub = require('./Grub')
class Bee extends Grub { => 상속받는 곳을 extends뒤에 작성
constructor(age, color, food, job) {
super(food) => 상속받는 속성 작성
this.age = 5;
this.color = 'yellow';
this.job = 'keep on growing'; => 각각의 속성 작성
}
}
module.exports = Bee;
[메소드 부여]
class HoneyMakerBee extends Bee {
constructor(age, job, color, food, honeyPot) { => 속성은 상속받는 것도 다 작성 (but, 메소는 작성X)
super(color, food)
this.age = 10;
this.job = 'make honey';
this.honeyPot = 0;
}
makeHoney() {
this.honeyPot++
}
giveHoney() {
this.honeyPot--
}
}
[인스턴스의 __proto__를 이용하면, 부모클래스의 프로토타입(메소드 등) 탐색 가능 => 메소드는 전달되지 않음]
[자료구조/알고리즘] 재귀
-
재귀: 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법
=> 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 / 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운경우 사용문제 풀 때 base condition(탈출조건), recursive condition(재귀조건) 설정
- 배열을 입력받아 길이 리턴
ex) [1, -2, 1, 3] -> 4
function arrLength(arr) {
const tail = arr.slice(1);
if(arr.isEmpty()) { => isEmpty는 js 내장 메소드X
return 0;
}
return 1 + arrLength(tail);
}- 수와 배열을 입력받아 수의 갯수 요소만 포함된 새로운 배열 리턴
ex) (2, [1, -2, 1, 3]) -> [1, -2] / (5, [1, -2, 1, 3]) -> [1, -2, 1, 3]
function take (num, arr) {
if(num === 0 || arr.length === 0) {
return [];
}
const head = arr[0]
const tail = arr.slice(1);
return [head].concat(take(num-1, tail))- 마트료시카
function findMatryoshka (matryoshka, size) {
if(matryoshka.size === size) {
return true;
}
else if (matryoshka.matryoshka === null) {
return false;
}
else if(matryoshka.matryoshka) {
return findMatryoshka(matryoshka.matryoshka, size)
}
return false;
}
다른 풀이
function findMatryoshka (matryoshka, size) {
const {size: head, matryoshka: tail} = matryoshka
if(head === undefined) {
return false;
}
if(head === size) {
return true;
}
if(tail === null) {
return false;
}
return findMatryoshka(tail, size);
}
*별도*
stringifyJSON : 직렬화 객체의 형태를 변환 => 서로 다른 프로그램 사이에서 데이터교환을 위해
JSON.stringify : object type -> JSON
JSON.parse : JSON -> object type
사용 시 코드 작성 => JSON.stringify(message)
[자료구조/알고리즘] 자료구조 기초
자료구조: 데이터를 효율적으로 다룰 수 있는 방법을 모음 => Stack, Queue, Tree, Graph
Stack => 데이터를 순서로 쌓는 자료구조 (가장 먼저 들어간 데이터가 제일 늦게 나옴 = FILO)
대표적으로 브라우저 뒤로 가기, 앞으로 가기 기능
[브라우저 앞으로 가기 뒤로 가기]
function browserStack(actions, start) {
let prev = [];
let next = [];
let cur = start;
for(let el of actions) {
if(typeof el === 'string') {
prev.push(cur);
cur = el;
next = [];
}
else if(el === -1 && prev.length !== 0) {
next.push(cur);
cur = prev.pop();
}
else if(el === 1 && next.length !== 0) {
prev.push(cur);
cur = next.pop();
}
}
return [prev, cur, next]
}
Queue => Stack와 반대되는 개념. 먼저들어간 데이터가 먼저 나옴 = FIFO
대표적으로 프린터 작업
[프린터]
function queuePrinter(bufferSize, capacities, documents) {
let Q = new Array(bufferSize).fill(0);
let sec = 0
while(documents.length !== 0) {
Q.shift()
let sum = Q.length ? Q.reduce((acc, cur) => acc + cur) : 0
if(sum + documents[0] <= capacities) {
Q.push(documents[0])
documents.shift()
} else {
Q.push(0)
}
sec++;
}
return sec+bufferSize
}
Graph => 여러개 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
하나의 점(정점-vertex), 하나의 선(간선-edge)
깊이 우선 탐색(DFS, Deph-First Search)
-> 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없는 경우 옆으로 이동
-> 스택 or 재귀함수로 구현
-> 총 경우의 수를 구할 때
너비 우선 탐색(BFS, Breath-First Search)
-> 최대한 넓게 이동한 다음, 더이상 갈 수 없을 때 아래로 이동
-> Queue를 이용해서 구현
-> 최당 경로 구할 때
[DFS/BFS 연결된 정점]
function connectedVertices(edges) {
let max = Math.max(...edges.flat())
let matrix = new Array(max + 1).fill(0).map(e => new Array(max + 1).fill(0))
edges.forEach(e => {
matrix[e[0]][e[1]] = 1
matrix[e[1]][e[0]] = 1
})
let visited = new Array(matrix.length).fill(false);
let count = 0;
for (let i = 0; i < matrix.length; i++) {
if(visited[i] === false) {
bfs(matrix, i, visited); => dfs도 가능
count++
}
}
return count;
}
function dfs(matrix, vertex, visited) {
visited[vertex] = true;
for (let i = 0; i < matrix[vertex].length; i++) {
if(matrix[vertex][i] === 1 && visited[i] === false) {
dfs(matrix, i, visited)
}
}
}
function bfs(matrix, v, visited) {
let Q = [v];
visited[v] = true;
while(Q.length !== 0) {
let cur = Q.shift()
for (let i = 0; i < matrix[cur].length; i++) {
if(matrix[cur][i] === 1 && visited[i] === false) {
Q.push(i);
visited[i] = true;
}
}
}
}
Tree => 데이터가 바로 아래 있는 하나 이상의 데터에 무방향으로 연결된 계층적 자료 구조
하나의 꼭짓점 루트(root)를 시작으로 각 데이터를 노드(Node)라고 함
이진트리 : 자식노드가 최대 두개인 노드로 구성된 트리
이진탐색트리(BST) : 모든 왼쪽 자식의 값이 루트 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐
[[Graph] adjacency matrix 구현]
class GraphWithAdjacencyMatrix {
constructor() {
this.matrix = [];
}
addVertex() {
//버텍스를 추가합니다.
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {
this.matrix[i].push(0);
}
this.matrix.push(new Array(currentLength + 1).fill(0));
}
contains(vertex) {
//버텍스가 있는지 확인합니다.
return !!this.matrix[vertex]
}
addEdge(from, to) {
const currentLength = this.matrix.length;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
else {
this.matrix[from][to] = 1;
}
}
hasEdge(from, to) {
if(this.matrix[from][to] === 1 ) {
return true;
}
return false;
//두 버텍스 사이에 간선이 있는지 확인합니다.
}
removeEdge(from, to) {
const currentLength = this.matrix.length;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
return;
}
else {
this.matrix[from][to] = 0;
}
//간선을 지워야 합니다.
}
}
[[Binary Search Tree] 구현]
class BinarySearchTree {
constructor(value) {
// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
this.value = value;
this.left = null;
this.right = null;
}
// 이진 탐색 트리의 삽입하는 메서드를 만듭니다.
insert(value) {
// 입력값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 있어야 합니다.
// 보다 작다면, Node의 왼쪽이 비어 있는지 확인 후 값을 넣습니다.
if (value < this.value) {
if (this.left === null) {
this.left = new BinarySearchTree(value);
} else {
return !!(this.left !== null && this.left.insert(value))
// 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어본다.
}
// 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣습니다.
} else if (value > this.value) {
if (this.right === null) {
this.right = new BinarySearchTree(value);
} else {
return !!(this.right !== null && this.right.insert(value))
// 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어본다.
}
//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
} else {
// 아무것도 하지 않습니다.
}
}
// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// 값이 포함되어 있다면 true를 반환.
if (this.value === value) {
return true;
}
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문이 있어야 합니다.
if (value < this.value) {
return !!(this.left !== null && this.left.contains(value))
// 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
// TODO:일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색합니다.
}
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
if (value > this.value) {
return !!(this.right !== null && this.right.contains(value))
// 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
// TODO:일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다.
}
// 없다면 false를 반환합니다.
}
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
preorder(callback) {
callback(this.value);
if (this.left) {
this.left.preorder(callback)
};
if (this.right) {
this.right.preorder(callback)
};
}
// 이진 탐색 트리를 중위 순회하는 메서드를 만듭니다.
inorder(callback) {
if(this.left) {
this.left.inorder(callback)
}
callback(this.value)
if(this.right) {
this.right.inorder(callback)
}
}
// 이진 탐색 트리를 후위 순회하는 메서드를 만듭니다.
postorder(callback) {
if(this.left) {
this.left.postorder(callback)
}
if(this.right) {
this.right.postorder(callback)
}
callback(this.value)
}
}
전위순회(Preorder) : 가장 먼저 루트를 순회 루트 => 왼쪽노드 => 오른쪽노드
중위순회(Inorder) : 루트를 가운데에 두고 순회 제일 왼쪽 끝 노드 => 루트 => 오른쪽노드
후위순회(Postorder) : 루트를 가장 마지막 제일 왼쪽 끝 노 => 오른쪽 순회 => 루트
