(2022.01.03) node.js 공부를 시작해보려고 한다. 일단은 node.js 교과서라는 책을 바탕으로 하여 구글링하면서 공부할 계획이다. 공부해둔거 기록하고, 나중에 보면 쉽게 떠오르도록 적어두는 것이라 자세하게 적지 않으려고한다. (사실 조금 귀찮기도...) 공식 홈페이지에 따르면, 노드는 자바 스크립트 런타임이라고 정의되어있다. 노드를 통해서 다양한 자바스크립트 애플리케이션을 실행할 수 있지만, 노드는 서버 애플리케이션을 실행하는데 가장 많이 사용한다. Node.js는 이벤트 기반, 논 블로킹, 싱글 스레드 모델이다. 1. 이벤트 기반 모델 이벤트가 발생하면 이벤트 리스너에 등록해둔 함수(콜백함수)를 실행한다. 호출 스택, 백그라운드, 테스트 큐를 돌면서 노드가 종료될 때까지 이벤트 처리를 ..

(2021.12.14) 알고리즘 수업 들으면서 정리하기 26탄 w15-2 녹강 + 보충강의 정리 저번 시간에 배우던 solvable problem 나머지 부분에 대해서 배웠따 개념이 너무 뒤죽박죽함 ▷ solvable problems > provably intractable problems (infeasible) : 해결하기 어려움이 입증된 문제 > probably intractable problems : 아마도 해결하기 어려울 것 같은 문제 ---> NP > tractable problems (feasible) : 다루기 쉬운 문제 --> P ▷ deterministic turing machine(DTM) : 주어진 state, 주어진 input 에 대해서 하나의 possible action만 존재하는..

(2021.12.08) 알고리즘 수업 들으면서 정리하기 25탄 w15-1 실강 정리 halting problem 을 배웠다. NP 정의도 배웠다. 교수님이 이 부분을 굉장히 자세하게 천천히 많이 설명해주셔서 오늘도 진도를 많이 안나갔다 교수님 추천 영상 https://www.youtube.com/watch?v=92WHN-pAFCs&feature=youtu.be Halting Problem (unsolvable problem) 프로그램 P와 input i 가 있고, 프로그램 P에 input i 를 넣는다. 그러면 두가지의 상황이 발생한다. > P halts on i > P runs forever on i 프로그램 P와 input i 가 있을 때, P가 i에 halt인지 아닌지를 알아낼 수 있는 프로그램 H..

(2021.12.07) 알고리즘 수업 들으면서 정리하기 24탄 w14-2, w14-3 녹강 정리 TM transition function, crashing, halting 에 대해 배웠다 저번 실강이랑 겹치는 내용이 많아서 정리할 내용이 거의 없다 TM transition function (여기서 Q의 정의부분이 틀렸다. halt 를 포함하지 않는다고 되어있는데 halt state도 포함한다) 이렇게 표현할 수 있다 example) Processing a string > string의 가장 왼쪽과 가장 오른쪽에는 blank symbol을 두고, blank가 아닌 string의 가장 첫번째 cell에 tape head를 두고 과정을 진행한다. > input string w에서 transition 과정이 진..

(2021.12.03) 이번에 정리할 부분 목차 13.1 비교 13.1.1 포함 13.1.2 확인 방법 13.1.3 관계 13.1. 복제 13.2 과정 13.2.1 키의 필요성 13.2.2 다이제스트에 서명하기 13.3 서비스 13.3.1 메시지 인증 13.3.2 메시지 무결성 13.3.3 부인봉쇄 13.3.4 기밀성 13.4 디지털 서명에 대한 공격 13.4.1 공격 유형 13.4.2 위조 유형 13.5 디지털 서명 구조 13.5.1 RSA 디지털 서명 구조 13.5.2 RSA 서명에 대한 공격 13.5.3 EIGamal 디지털 서명 구조 13.5.5 디지털 서명 표준 교수님이 설명하신 부분에 대해서만 정리 서명의 유형 전자 서명: Electronic Signature Biometric signatur..

(2021.12.01) 이번에 정리할 부분 목차 12.1 개요 12.1.1 반복 해시 함수 12.1.2 압축 함수의 두가지 유형 12.2 SHA-512 12.2.1 개요 12.2.2 압축 함수 12.2.3 분석 12.3 WHIRLPOOL 12.3.1 Whirlpool 암호 12.3.2 요약 12.3.3 분석 이전 단원들 내용이 나와서 더 헷갈리고 어려웠다.. 이해하기 위해 이전 단원들을 여러 번 읽어봄 그나마 이번 단원은 짧다.. 암호학적 해시 함수 해시함수: 입력되는 메시지의 크기에 상관없이 일정한 크기의 출력 생성 압축함수: 입력되는 메시지의 크기 고정, 일정한 크기의 출력 생성 --> 압축함수는 (n>m) n-비트 스트링을 m-비트 스트링으로 만든다. 이 구조를 반복 암호학적 해시 함수라고 한다. ..

(2021.12.01) 알고리즘 수업 들으면서 정리하기 23탄 w14 실강 NP-completeness 내용 시작 계산 복잡도, 튜링 기계에 대해 배웠다 NP-completeness Computational Complexity > 알고리즘은 특정 알고리즘의 performance 특성 (성능 특성)에 대한 연구이다. > 계산 복잡도(계산 이론)은 알고리즘보다는 문제의 특성에 대한 연구이다. 우리는 문제를 solvable problem과 unsolvable problem으로 나눌 수 있다. > unsolvable problem은 다시 세가지로 나뉜다. 1. Unsolvable problems ---> halting problem 2. Solvable problems a. Provably intractable..

(2021.11.30) 알고리즘 수업 들으면서 정리하기 22탄 w13-2 녹강 N-Queens problem에 관한 내용이다 지금까지 배운 것 중에서 개념은 정말 쉬운 것 같은데 구현하는게 어려울 것 같다.. 시간나면 구현해봐야지.. N-Queens problem : backtracking 기본형 problem이다 n x n의 체스보드에서 n개의 서로다른 queen들이 서로 공격하지 않는 자리에 어떻게 둘 수 있는지를 물어본다. 예를 들어 n=4 라고 했을 때, 4개의 Queen들이 위치할 수 있는 전체 경우의 수는 16 x 15 x 14 x 13 = 43680 가지이다. 그러나 우리는 이를 더욱 간단하게 알아 볼 수 있다. --> search space를 줄여나가면서!! 기본적인 sketch idea는..

(2021.11.23) 알고리즘 수업들으면서 정리하기 21탄 w12-2 녹강, w12-3 녹강, w13-1 실강 maximum flow, network flow 내용이다. Flow network Maximum-flow problem : flow network G가 주어지고, source s, target t, capacity c 가 주어질 때, value가 최대인 flow를 찾는 문제 Max-flow min-cut theorem : max-flow의 값과 min-cut의 값이 같다. The Ford-Fulkerson method The Ford-Fulkerson method가 the maximum-flow problem을 해결한다. input: a flow network G, source s, targe..

(2021.11.20) 이번에 정리할 부분 목차 11.1 메시지 무결성 11.1.1 문서와 핑거프린트 11.1.2 메시지와 메시지 다이제스트 11.1.3 차이점 11.1.4 무결성 확인 11.1.5 암호학적 해시 함수 기준 11.2 랜덤 오라클 모델 11.2.1 비둘기 집 원리 11.2.2 생일 문제 11.2.3 랜덤 오라클 모델에 대한 공격 11.2.4 구조에 대한 공격 11.3 메시지 인증 11.3.1 변경 탐지 코드 11.3.2 메시지 인증 코드 11.1 메시지 무결성 무결성 점검(checking Integrity) : 암호학적 해쉬함수를 이용해서 생성된 새로운 message digest와 그 이전의 message digest를 비교하여 message가 바뀌었는지 바뀌지않았는지를 확인할 수 있다. ..

(2021.11.17) 알고리즘 수업들으면서 정리하기 20탄 w11-2 녹화강의, w12-1 실강 minimum spanning tree와 prim algorithm 내용이다. Minimum Spanninng Tree 최소 신장 트리 --> 줄여서 MST input: 방향성 없는 연결 그래프 connected, undirected graph G=(V,E) (각 edge 들에 weigth가 있음) output: acyclic subset T of the edges of G (G의 모서리들의 cycle 없는 subset) Model은 undirected graph G=(V,E) 임 각 edge (u,v) ∈ E 에는 weight w(u,v) 가 있음 (u,v ⊂ V) acyclic T⊆E 에 대해서 모든 노..

(2021.11.14) 이번에 정리할 부분 목차 10.1 대칭 키 암호 시스템과 비대칭 키 암호시스템의 차이점 10.1.1 키 10.1.2 일반적인 아이디어 10.1.3 양쪽에 필요한 것 10.1.4 트랩도어 일방향 함수 10.1.5 배낭 암호 10.2 RSA 암호시스템 10.2.1 개요 10.2.2 절차 10.2.3 간단한 예제 10.2.4 RSA에 대한 공격 10.2.5 권장 사항 10.2.6 최적 비대칭 암호 패딩(OAEP) 10.3 Rabin 암호 시스템 10.3.1 절차 10.3.2 Rabin 시스템의 보안성 10.4 EIGamal 암호시스템 10.4.1 EIGamal 암호시스템 10.4.2 절차 10.4.3 키 생성 10.4.4 EIGamal의 보안성 10.5 타원 곡선 암호 시스템 (교수님이..

(2021.11.07) 이번에 정리할 부분 목차 9.4 중국인의 나머지 정리 9.4.1 응용 9.5 2차 합동 9.5.1 모듈로가 소수인 2차 합동 9.5.2 모듈로가 합성수인 2차 합동 방정식 풀기 9.6 지수와 로그 9.6.1 지수 9.6.2 로그 9.4 중국인의 나머지 정리(CRT: Chinese remainder theorem) 9.5 2차 합동(quadratic congruence) 9.5.1 모듈로가 소수인 2차 합동 9.5.2 모듈로가 합성수인 2차 함동 방정식 풀기 모듈로가 합성수인 2차 합동 방정식은 모듈로가 소수인 2차 합동 방정식으로 분해해서 x에 대한 k쌍의 해를 구할 수 있다. --> k쌍의 해로부터 2^k개의 연립방정식을 중국인의 나머지 정리를 이용해 풀면 x에 대한 2^k개의 ..

(2021.11.12) 알고리즘 수업들으면서 정리하기 19탄 w10-3 녹화강의, w11-1 실강 BFS,DFS 내용이다. Network flow graph 알고리즘 - Breadth-first search - Depth-first search - Minimum spanning tree (Prim's algorithms) - Maximum flow (The Ford-Fulkerson method) graph G=(V,E) 로 표현한다. - V는 vertices 의 집합 (G.V) - E는 edges 의 집합 (G.E) G는 방향성일 수도 있고, 무방향성일 수도 있다. (directed, undirected) 보통 graph는 인접리스트나 인접행렬로 표현한다. BFS(Breadth-first search)..

(2021.11.08) 알고리즘 수업들으면서 정리하기 18탄 w10-2 녹화강의 huffman code 개념, 만드는 방법, greedy 알고리즘 Huffman codes each character를 binary charcter code로 디자인하는 것 optimal prefix code 라고도 한다. huffman code는 빈도수에 따라서 설정해준다. huffman code는 variable-length code이며, fixed-length code보다 효율적이다. (fixed-length code는 3비트로 표현한다--> 많은 저장용량을 차지한다.) prefix-free code (prefix code) huffman code의 가장 큰 특징은 prefix-free code(prefix code)이..