Data Structure & Algorithm
-
왜 자료 구조, 알고리즘을 배워야 할까? : 블로그
-
알고리즘 테스트로 뽑으려는 회사는? : 블로그
-
대학생이 참여할 수 있는 알고리즘 대회 : 블로그
-
포스팅 계획 : 블로그
-
queue
-
deque
-
Linked List
- Single Linked List
- Double Linked List
- Circular Linked List
-
Hash Table
-
Tree
- Basic Concept of Tree
- BST(Binary Search Tree)
- Max Heap & Max Priority Queue
- MST(Minimum Spanning Tree)
- Prim's method
- Kruskal's method
- Selection Tree
- AVL Tree
- B+ Tree
- Segment Tree
-
Graph
- Basic Concept of Graph
- Tree Traversal
-
Shortest Path (Algorithm 강의자료도 참고해서 구현)
- Dijkstra's algorithm (추가적으로 BFS)
- Bellman-ford's algorithm
- Floyd's Algorithm
-
Disjoint Set
-
Sorting
-
Complexity
- Space complexity
- Time complexity
-
Asymptotic Notation
- O-notation, Ω-notation, Θ-notation
- ο-notation, ω-notation
-
Recurrences
- Substitution method
- Iterating the recurrence (참고: https://www.youtube.com/watch?v=TEzbkIggJfo)
- Recursion Tree
- Master method
-
Divide and Conquer
- Binary Search && Parametric search
- Powering a number
- Fibonacci numbers
- Matrix Multiplication
- Strassen's algorithm
- Quick sort (위에 sorting과 겹치게 된다.)
- Randomized quicksort (randomized algorithm의 이해가 필요) (참고: https://ko.wikipedia.org/wiki/%ED%99%95%EB%A5%A0%EC%A0%81_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)
-
Sorting Lower Bounds
- Decision trees
-
Dynamic Programming
- LCS(Longest Common Sequence)
- Optimal substructure
- Overlapping subproblems
-
Greedy Algorithms
- Greedy 관점으로 MST ( 위에 Data Structure와 겹친다. )
- Optimal substructure
- Greedy choice
-
Linear Programming Algorithm
-
NP-Completness
- Tractable vs Intractable Problems
- P & NP class
- Desicion Problem vs Optimization Problem
- NP-Completeness
- CNF Satisfiability
- Hamiltonian-Cycle Problem
- Traveling-Salesman Problem
-
Tower of Hanoi (하노이의 탑)
-
Numerical Method (수치해석)
- bisection method
- ternary search
- Simpson's method
-
Number Theory Algorithm (정수론 알고리즘)
- 소수 판별
- prime factorization (소인수 분해)
- Sieve of Eratosthenes (에라토스테네스의 체)
- Euclidean algorithm (유클리드 알고리즘)
- Modular arithmetic (모듈라 연산)
- Extended Euclidean algorithm (확장 유클리드 알고리즘)
- Chinese Remainder Theorem (중국인 나머지 정리)
- Lucas's Theorem (루카스 정리)
-
Computational geometry (계산 기하)
-
문자열 검색 알고리즘
- KMP(Knuth–Morris–Pratt)
- Suffix Array(접미사 배열)
-
NetWork Flow (네트워크 유량)
- vector
- stack
- queue
- deque
- map - Red Black Tree
- set
- priority_queue
- sort
- greater, less - sort와 priority queue 다른 점 비교
-
수업
-
광운대학교 / 2-1 객체지향프로그래밍및 설계 / 김영민 교수님
-
광운대학교 / 2-2 데이터 구조 수업 / 이기훈 교수님
-
광운대학교 / 3-2 알고리즘 수업 / 황호영 교수님
-
-
서적
-
THOMAS H.CORMEN, CHARLES E. LEISERSO,N RONALD L.RIVEST, & CLIFFORD STEIN (2009) Introduction to algorithm
-
구종만 지음, 인사이트 (2014) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
-
-
Github
- jwasham's coding-interview-university
-
Youtube
-
블로그