Algorithm_Training

link

• latex-문법

  • 수학-공식-테스트-하기live-web---latex
  • 마크-다운에-수학-공식-넣는-방법

• 사람의-눈보다-더-빨리-움직이는-걸-볼-수-있다면--우리-눈이-볼-수-없는-세계-1-초고속의-순간-bbc--세상의-모든-다큐

  • 프로그래머가-알아야-할-지연-시간-숫자를-시각적으로-표현
  • 무작위-속-질서-중심극한정리--확률과-통계--3blue1brown-한국어
  • 애니매이션으로-모든-물리학-공식과-같이-연관-되어-보기-진짜-대박-최고

• 수학-그래프를-그리는-도구

• 알고리즘-관련

  • 트위터-추천-알고리즘scala로-작성됨
  • 자료-구조Data Structure
    • 서울대 Data Structure자료 굿
  • 대표적인-알고리즘-정리
  • 알고리즘-정렬-이미지
  • structuredprogramming
  • 파이썬으로-알고리즘-구조-이해하기

• big-picture-of-calculus--mit-opencourseware

• amazon관련책-algorithms-4th-edition-kindle-edition

• algorithms--algorithms-design-and-analysis

---

• quantum-programming
  • visualization-of-quantum-physics-quantum-mechanics
  • 양자 코딩 여기에 정리 중...

---

유료강의[🔝]

• fastcampus(현실 세상의 컴퓨터공학 지식 with 30가지 실무 시나리오 초격차 패키지 Online
  • https://fastcampus.co.kr/dev_online_newcomputer
    • (맛보기무료)컴퓨터 구조 몰아보기(7hr)
      • https://youtu.be/kFWP6sFKyp0?si=IXbGZgn6jp_RRkg_

---

Latex 문법[🔝]

• https://junia3.github.io/blog/latex_symbols

---

사람의 눈보다 더 빨리 움직이는 걸 볼 수 있다면? | 우리 눈이 볼 수 없는 세계 (1) 초고속의 순간 #BBC | 세상의 모든 다큐[🔝]

• https://youtu.be/VCvS4MV0hEM?si=AYIByJl4ySYC2efv

  • part2

    • https://youtu.be/PWEVqrhTLro?si=TcDFRGpMOcb_uVOj

  • part3

    • https://youtu.be/jURoQtKgjqY?si=y7TF2kRO0I5uJh0P

---

프로그래머가 알아야 할 지연 시간 숫자를 시각적으로 표현[🔝]

GN⁺: 모든 프로그래머가 알아야 할 필수 숫자들

• https://samwho.dev/numbers/?fo
• L1 캐시 참조: 1나노초
• 분기 예측 실패: 3나노초
• L2 캐시 참조: 4나노초
• 뮤텍스 잠금/해제: 17나노초
• 1 Gbps 네트워크를 통한 1KB 데이터 전송: 44나노초
• 주 메모리 참조: 100나노초
• Zippy를 이용한 1KB 데이터 압축: 2마이크로초
• 메모리에서 1MB 순차 읽기: 3마이크로초
• SSD에서 4K 무작위 읽기: 16마이크로초
• SSD에서 1MB 순차 읽기: 49마이크로초
• 동일 데이터센터 내 왕복 시간: 500마이크로초
• 디스크에서 1MB 순차 읽기: 825마이크로초
• 디스크 탐색: 2밀리초
• 캘리포니아에서 네덜란드까지 패킷 전송 후 돌아오기: 150밀리초

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Notes
-----
1 ns = 10^-9 seconds
1 us = 10^-6 seconds = 1,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns

Credit
------
By Jeff Dean:               http://research.google.com/people/jeff/
Originally by Peter Norvig: http://norvig.com/21-days.html#answers

Contributions
-------------
'Humanized' comparison:  https://gist.github.com/hellerbarde/2843375
Visual comparison chart: http://i.imgur.com/k0t1e.png

• https://gist.github.com/jboner/2841832

• 이게 고화질 https://colin-scott.github.io/personal_website/research/interactive_latency.html

---

• https://norvig.com/21-days.html#answers

Answers

Approximate timing for various operations on a typical PC:

execute typical instruction	1/1,000,000,000 sec = 1 nanosec
fetch from L1 cache memory	0.5 nanosec
branch misprediction	5 nanosec
fetch from L2 cache memory	7 nanosec
Mutex lock/unlock	25 nanosec
fetch from main memory	100 nanosec
send 2K bytes over 1Gbps network	20,000 nanosec
read 1MB sequentially from memory	250,000 nanosec
fetch from new disk location (seek)	8,000,000 nanosec
read 1MB sequentially from disk	20,000,000 nanosec
send packet US to Europe and back	150 milliseconds = 150,000,000 nanosec

---

Operation	ns	µs	ms	note
L1 cache reference	0.5 ns
Branch mispredict	5 ns
L2 cache reference	7 ns			14x L1 cache
Mutex lock/unlock	25 ns
Main memory reference	100 ns			20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy	3,000 ns	3 µs
Send 1K bytes over 1 Gbps network	10,000 ns	10 µs
Read 4K randomly from SSD*	150,000 ns	150 µs		~1GB/sec SSD
Read 1 MB sequentially from memory	250,000 ns	250 µs
Round trip within same datacenter	500,000 ns	500 µs
Read 1 MB sequentially from SSD*	1,000,000 ns	1,000 µs	1 ms	~1GB/sec SSD, 4X memory
Disk seek	10,000,000 ns	10,000 µs	10 ms	20x datacenter roundtrip
Read 1 MB sequentially from disk	20,000,000 ns	20,000 µs	20 ms	80x memory, 20X SSD
Send packet CA -> Netherlands -> CA	150,000,000 ns	150,000 µs	150 ms

---

• https://ko.m.wikipedia.org/wiki/%EB%B0%80%EB%A6%AC

SI 접두어
v • d • e • h

10n	접두어	기호	배수	십진수
1030	퀘타 (quetta)	Q	백양	1 000 000 000 000 000 000 000 000 000 000
1027	론나 (ronna)	R	천자	1 000 000 000 000 000 000 000 000 000
1024	요타 (yotta)	Y	일자	1 000 000 000 000 000 000 000 000
1021	제타 (zetta)	Z	십해	1 000 000 000 000 000 000 000
1018	엑사 (exa)	E	백경	1 000 000 000 000 000 000
1015	페타 (peta)	P	천조	1 000 000 000 000 000
1012	테라 (tera)	T	일조	1 000 000 000 000
109	기가 (giga)	G	십억	1 000 000 000
106	메가 (mega)	M	백만	1 000 000
103	킬로 (kilo)	k	천	1 000
102	헥토 (hecto)	h	백	100
101	데카 (deca)	da	십	10
100			일	1
10−1	데시 (deci)	d	십분의 일	0.1
10−2	센티 (centi)	c	백분의 일	0.01
10−3	밀리 (milli)	m	천분의 일	0.001
10−6	마이크로 (micro)	µ	백만분의 일	0.000 001
10−9	나노 (nano)	n	십억분의 일	0.000 000 001
10−12	피코 (pico)	p	일조분의 일	0.000 000 000 001
10−15	펨토 (femto)	f	천조분의 일	0.000 000 000 000 001
10−18	아토 (atto)	a	백경분의 일	0.000 000 000 000 000 001
10−21	젭토 (zepto)	z	십해분의 일	0.000 000 000 000 000 000 001
10−24	욕토 (yocto)	y	일자분의 일	0.000 000 000 000 000 000 000 001
10−27	론토 (ronto)	r	천자분의 일	0.000 000 000 000 000 000 000 000 001
10−30	퀙토 (quecto)	q	백양분의 일	0.000 000 000 000 000 000 000 000 000 001

트위터 추천 알고리즘(scala로 작성됨)[🔝]

• https://github.com/twitter/the-algorithm

---

애니매이션으로 모든 물리학 공식과 같이 연관 되어 보기.. 진짜 대박 최고 !!❤[🔝]

• Animation vs. Physics | Alan Becker
  • https://youtu.be/ErMSHiQRnc8?si=mG-sttkOox6CS7Oq
    • 한글 버젼 애니메이션 vs 물리학 한글 자막 | 물리학과
      • https://youtu.be/qYJbrCQovzE?si=pBsAExRd1E3sVXBO
• Animation vs. Math | Alan Becker
  • https://youtu.be/B1J6Ou4q8vE?si=53zJzMx2_-mTXdbS

---

자료 구조[🔝]

https://github.com/YoungHaKim7/c_project/tree/main/exercise/002stack

• 영어 출처 https://en.wikipedia.org/wiki/Association_list

자료 구조(Well-known data structures)
유형(Type)	컬렉션(Collection) , 컨테이너(Container)
추상ADT Abstract Data Type	연관 배열(Associative array), 우선 순위 덱(Priority Deque), 덱(Deque), 리스트(List), 멀티맵, 우선순위 큐(Priority Queue), 큐(Queue), 집합 (멀티셋, 분리 집합), 스택(stack) Associative array(Multimap, Retrieval Data Structure), List, StackQueue(Double-ended queue), Priority queue(Double-ended priority queue), Set(Multiset, Disjoint-set)
배열(Array)	비트 배열(Bit Array), 환형 배열(Circular array), 동적 배열(Dynamic Array), 해시 테이블(Hash Table), 해시드 어레이 트리(Hashed Array Tree), 희소 배열(Sparse array)
연결형(Linked)	연관 리스트(Association list), 연결 리스트(Linked List) - 단일연결(Singly Linked List), 이중연결(Doubly Linked List), 원형 연결(Circular Linked List) Association list, Linked list, Skip list, Unrolled linked list, XOR linked list
트리(Trees)	B 트리, 이진 탐색 트리(AA, AVL, 레드-블랙, 자가 균형, splay) 힙(이진 힙, 피보나치) , R 트리( R*, R+, 힐버트), 트리(해시 트리) B-tree, Binary search tree(AA tree, AVL tree, Red–black tree, Self-balancing tree, Splay tree), Heap(Binary heap, Binomial heap, Fibonacci heap), R-tree(R* tree, R+ tree, Hilbert R-tree), Trie Hash tree
그래프(Graphs)	이진 결정 다이어그램 Binary decision diagram, Directed acyclic graph, Directed acyclic word graph

---

대표적인 알고리즘 정리[🔝]

1. 정렬(Sort)
2. 검색(Search)
3. 문자열 패턴 매칭(SPM: String Pattern Matching)
4. 계산(Calculation)

---

알고리즘 정렬 이미지[🔝]

• Random(Shell & Heap . 가 젤 빠름)
• Nearly Sorted(Insert 가 젤 빠름)
• Reverse(Shell 가 젤 빠름)
• Few Unique(Quick3 가 젤 빠름)

---

StructuredProgramming[🔝]

• 알고리즘을 기술할 목적으로 만들어진 언어 중 하나가 SPARKS(Structured Programming: A Reasonably Kimplete Set)
• 구성

- 선언문
- 지정문
- 조건문
- 반복문
- Procedure문
- 프로시져 사이 자료 전달 방법(process transaction)
- 입출력문
- 주석문

• https://en.wikipedia.org/wiki/Flow-based_programming

• https://web.archive.org/web/20180308114549/http://www.hit.ac.il:80/staff/leonidM/information-systems/ch63.html

• https://en.wikipedia.org/wiki/Structured_programming

• http://users.csc.calpoly.edu/~jdalbey/103/Lectures/StructuredProgramming/

---

Amazon관련책 Algorithms 4th Edition, Kindle Edition

https://www.amazon.com/Algorithms-Algorithms_4-Robert-Sedgewick-ebook/dp/B004P8J1NA/ref=tmm_kin_swatch_0?_encoding=UTF8&qid=&sr=

Algorithms & Algorithms design and analysis

• part 1 complete(12hr)
  • https://youtu.be/9diDWV-fOnE?si=r1YlAfOcIz0w5z_i
• Algorithms part 2 (1/2)
  • https://youtu.be/0qF7tPSQdCg?si=YuLJeuBTfgz_RWM9
• Algorithms part 2 (2/2)
  • https://youtu.be/6TW3JSVEJQE?si=sPBO7A70DYQcbhz9
    • Algorithms design and analysis part 1(1/2)
      • https://youtu.be/NqKkxQamroo?si=P5qxYCsWJ2hZEOqA
    • Algorithms design and analysis part 1(2/2)
      • https://youtu.be/ahvrc4tZbTE?si=RRO0j71_Pskv24rn
    • Algorithms design and analysis part 2(1/2)
      • https://youtu.be/nUIbHblMop4?si=2UHh66W__YNTWpKd
    • Algorithms design and analysis part 2(2/2)
      • https://youtu.be/M5JzG8oDicA?si=8bEI94JHkkcOAUA7

---

Big Picture of Calculus | MIT OpenCourseWare[🔝]

https://youtu.be/UcWsDwg1XwM

파이썬으로 알고리즘 구조 이해하기[🔝]

• 파이썬으로 알고리즘 공부하기 https://academy.cs.cmu.edu/

수학 그래프를 그리는 도구[🔝]

• Demos & GeoGebra

  • https://www.desmos.com/

  • GeoGebra 소개 영상 https://youtu.be/X_YT335w8Mc

    • https://www.geogebra.org/

• 비 전문가들이 고품질의 아름다운 다이어그램을 작성할 수 있게 도와주는 것을 목표로 개발

  • 세가지 프로그램을 이용하여 구성
    • Domain (.domain) 프로그램 : 해당 도메인의 다이어그램을 구성하는 객체, Predicates, 함수의 유형을 설명
    • Substance (.substance) 프로그램 : 다이어그램의 객체와 관계를 정의
    • Style (.style) 프로그램 : 객체와 관계를 디스플레이하는 방법을 지시
  • https://penrose.cs.cmu.edu/examples

• 러스트로 만든 LaTex업그레이드 버젼 A new markup-based typesetting system that is powerful and easy to learn.

  • https://github.com/typst/typst

• ALL of calculus 3 in 8 minutes.수학공식 전부 다 그래프로 그려보기 https://youtu.be/5kwz7ajxfyA

알고리즘 관련

• Rust https://github.com/TheAlgorithms/Rust
• 알고리즘 (1^8) 1초안에 승부를 보는 알고리즘의 세계 https://news.hada.io/topic?id=9459
  • 1억 = 1초 https://zoosso.tistory.com/883
  • MIT강의 MIT 6.006 Introduction to Algorithms, Spring 2020 https://youtube.com/playlist?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY
    • 1. Algorithms and Computation | MIT ♡Algorithm♡ https://youtu.be/ZA-tUyM_y7s
      2. Data Structures and Dynamic Arrays | MIT https://youtu.be/CHhwJjR0mZA
  • 서울대학교 SNUON_컴퓨터과학이 여는 세계_9.2 알고리즘의 예_이광근 https://youtu.be/39sJYroBZLs
  • 그림으로 공부❤️8Data Structures That Power Database https://youtu.be/W_v05d_2RTo

---

Quantum Programming[🔝]

• Quantum Programming Part 1(설명 굿👍)
  • https://youtu.be/2Eswqed8agg

Visualization of Quantum Physics (Quantum Mechanics)[🔝]

• 2분 21초 https://youtu.be/p7bzE1E5PMY
• 슈뢰딩거 방정식(영어: Schrödinger equation) 그림으로 이해하기
• 마크다운 수학 공식 정리 https://rayc20.tistory.com/151
• TeX_및_LaTeX_수식_문법 http://tomoyo.ivyro.net/123/wiki.php/TeX_%EB%B0%8F_LaTeX_%EC%88%98%EC%8B%9D_%EB%AC%B8%EB%B2%95
• Schrödinger equation

$$i \hbar \frac{\partial}{\partial t}\Psi(\mathbf{r},t) = \hat H \Psi(\mathbf{r},t)$$

• 동영상에 나오는 공식

$$i \hbar \frac{\partial}{\partial t}\Psi = -{\hbar^2 \over2m}\Delta\Psi$$

https://www.siue.edu/~mnorton/quantum.pdf

• 자바스크립트로 구현한 슈뢰딩거 방정식(-方程式, 영어: Schrödinger equation)

  • https://github.com/rreusser/schrodinger-equation-1d-demo

  • 슈뢰딩거 방정식(-方程式, 영어: Schrödinger equation) 정의

    • https://ko.wikipedia.org/wiki/%EC%8A%88%EB%A2%B0%EB%94%A9%EA%B1%B0_%EB%B0%A9%EC%A0%95%EC%8B%9D

---

마크 다운에 수학 공식 넣는 방법[🔝]

https://docs.github.com/en/get-started/writing-on-github/working-with-advanced-formatting/writing-mathematical-expressions

수학 공식 테스트 하기(live web - latex)[🔝]

https://www.mathjax.org/

The Cauchy-Schwarz Inequality

$$\left( \sum_{k=1}^n a_k b_k \right)^2 \leq \left( \sum_{k=1}^n a_k^2 \right) \left( \sum_{k=1}^n b_k^2 \right)$$

---

---

무작위 속 질서, 중심극한정리 | 확률과 통계 | 3Blue1Brown 한국어

https://youtu.be/SoKjCUcDBf0?si=wcx9mPCZf_MYG9_9