하루 마무리
DFS 자료구조 & 알고리즘 문제 복습
코어자바스크립트 챕터 7 공부
네트워크 공부 (ip계층)
익스프레스 미들웨어 만들기
DFS, 재귀함수
리트코드 데일리 문제 풀이
https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/
In-order: left child → parent → right child
https://blog.bitsrc.io/depth-first-search-of-a-binary-tree-in-javascript-874701d8210a
- Node 구조 정의
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
/**
* param {TreeNode} root
* return {number[]}
*/
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);- 문제 풀이 1 (while 문, stack으로 풀이)
무슨 재귀든간에 stack을 써서 반복문으로 바꿀 수 있다.
C, rust에서는 stack이 더 빠름 (어차피 재귀함수도 stack으로 돌아가기 때문에 좀더 native함)
// In-order: left child → parent → right child
const inorderTraversal = (root) => {
let stack = [];
let traversed = [];
let currentNode = root;
while (stack.length > 0 || currentNode) {
while (currentNode) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
traversed.push(currentNode.val);
currentNode = currentNode.right;
}
return traversed;
};
console.log(inorderTraversal(root));
- 문제 풀이 2 (DFS 알고리즘 사용)
const inorderTraversal = (root) => {
let result = [];
dfs(root);
function dfs(root) {
if (root != null) {
dfs(root.left);
result.push(root.val);
dfs(root.right);
}
}
return result;
};_재귀함수때문에 돌아뿜
재귀함수 꿀팁
프로그램의 복잡한 실행 순서(함수 호출이 있으니까 제어가 다른 함수로 넘어가서 실행된 다음 다시 돌아오고 어쩌구)를 생각하지 말자.
호출되는 모든 함수가 완벽하게 짜여 있다는 가정 하에, 코드에 함수 호출이 있으면 "호출이 이런 값을 돌려주겠구나"하고 끝까지 읽자.
우리가 console.log 호출한다고 흐름이 console.log 함수 소스코드로 들어가는 걸 다 생각하지 않듯이, 코드 읽을 때 함수 호출은 더 나눌 수 없는 하나의 명령어로 생각하면 뇌가 터지는 걸 막을 수 있다.
강의 영상 참고함
- 모든 게 완벽하다는 가정 하에 코드 읽기
- 재귀 호출에 순환이 없고 종료 조건이 맞는지 확인해서 결국 끝나는 알고리즘임을 정당화 (이때는 코드 자체를 보지 않고 의존 관계만 봄)
이렇게 두 가지를 별개로 하는 것!
재귀 호출이 아니라 그냥 코드 짤 때도 함수 호출의 내부는 생각 안 해요
값을 반환하는 게 아니라 별찍기 같이 동작(부작용)이 있는 재귀 호출도 일단 완벽하다는 가정 하에 생각
재귀함수로 너무 헤매서.. 보면 좋은 글 https://blog.encrypted.gg/943
정리 겁나 대충 했는데.. 키워드로만 보기..
계산 가능성 이론: 컴퓨터 기계 나오기 전에 어떤 수를 계산할 수 있는가를 연구하는 엘런 튜링 -> 계산가능한 문제들을 예측해놓은 것들이 있음
가상의 기계 튜링머신 -> 물리적으로 계산할 수 있게 할 수 있다 (튜링머신 할 수 있으면 튜링 완전하다) 대부분의 언어가 튜링 완전하다 ~~~
밈) 홈페이지 CSS 튜링완전하면 프로그래밍언어다 어쩌구 ~ -> 튜링완전한 기계를 2가지로 생각함 (1. 주로 쓰는 컴퓨터 랜덤 엑세스 머신, 2. 람다 칼큘러스 ~ 함수형 언어의 기본)
계산 가능한 것은 C언어로 유한한 시간안에 계산 가능하면 람다 칼큘러스 기반으로 유한시간으로 끝낼 수 있다 ~ 프로그래밍 사상 싸움
반복문이라는 것은...명령문 언어들이 반복문을 기반으로 함 > 람다 칼큘은 반복문을 잘 안씀 (재귀를 씀)
함수형 언어들은 주로 재귀를 많이 쓴다.
반복하고 재귀는 서로 대체 가능한 관계
반복문 -> 재귀: 꼬리재귀
꼬리재귀 -> 반복문: 스택
명령형 선언형 대비는 나중에 찾아보기
점화식:피보나치, 병합정렬
subproblem이 지수적 감소: 이분탐색 (꼬리재귀라서 반복문으로 많이 씀)
subproblem이 나눠짐: 분할정복
subproblem이 여러번 필요: dynamic program (동적계획법) ~ 이름 멋잇어서 적은 알고리즘 (피보나치가 가장 대표적인 예 일반 재귀도 좋지만 동적계획법이 더 빠름)
상수시간 안에 피보나치 푸는 법도 있음.. https://suhak.tistory.com/81
익스프레스 미들웨어 만들기
https://expressjs.com/en/guide/writing-middleware.html
이전 코드.. https://bit.ly/3RumpE7
fs.readdir("./data", function (error, filelist) {
}글 목록 표현하는 로직 반복적 사용함 -> 미들웨어 사용
- 모든 요청 시마다 미들웨어 실행 (
use메서드)
app.use(function (request, response, next) {
fs.readdir("./data", function (error, filelist) {
request.list = filelist;
next();
});
});그러나 파일 목록 읽어오는건 get 메서드일 때 씀 (xx_process 일 경우엔 안씀.. 비효율적)
app.get("*", function (request, response, next) {
fs.readdir("./data", function (error, filelist) {
request.list = filelist;
next();
});
});코어자바스크립트 챕터 7: 클래스
자바스크립트는 상속 개념이 없음 (프로토 타입 기반 언어)
ES6에서 클래스 문법 나타남
그러나 클래스에서 일정 부분은 프로토타입을 활용하기 때문에 ES5 체제 하에서 클래스를 흉내하기 위한 구현 방식을 학습하는 것은 중요하다
개발자를 위한 검색 팁
https://gist.github.com/robertpainsi/b632364184e70900af4ab688decf6f53
하루 마무리
-
완료한 것 ❌ 🔺 ✅
DFS 자료구조 & 알고리즘 문제 복습 ✅
코어자바스크립트 챕터 7 공부 ❌
네트워크 공부 (ip계층) ❌
익스프레스 미들웨어 만들기 ✅ -
하루 반성
자꾸 딴 길로 샌다.
주별/월별 계획을 세워도 진도가 어느정도 수준으로 빠지는지 객관적으로 파악을 못해서 진도가 늘어진다. -
피드백
아 이거 한번 독학 멘토랑 얘기를 해봐야할 듯. (중간 점검)
구현 중심으로 하루 계획표를 세우자.
과한 욕심 부리지 말고 내가 느림을 인정하고 계획은 간결하고 핵심적인 것을 위주로 적자.
- 내일 할 것
익스프레스 (10~14)공부
코어자바스크립트 챕터 7 공부
네트워크 (ip계층) 공부
알고리즘 1 문제 풀이
