• 호눅스의 자료구조와 알고리즘 3번째 시간
  • 트리
    • 탐색시간 최적 오메가(logn), 최악 O(n)
    • 순회: 전위 중위 후위 / 계산식은 중위에서 후위로
    • BTS의 단점 한쪽으로만 계속달림 => 개선 Balanced BTS (삽입시 기존트리 회전시켜 균형)
    • 균형트리, 불균형트리, 포화이진트리, 완전이진트리
    • 구현방법: 참조객체 or 배열
    • 자식갯수에 따른 삭제방법 비교
  • 그래프
    • vertex, edge, (direction), (weight)
    • 표현: Adjacency Matrix, Adjacency List
    • 페이스북 친구 추천 알고리즘 / 지하철 최단거리 노선 찾기
    • 그래프 순회 : 깊이우선탐색 DFS (재귀or스택사용,방문체크), 넓이우선탐색 BFS (인접이웃먼저/큐사용)
• 생각
  • 모든 자료구조는 invariant(불변성)이 있다는 것.
  • 자료구조가 자료구조를 표현하는 구나 / 그리고 모든 것의 기초는 배열과 포인터이다
  • 알고리즘(특히 재귀)가 코드 구현에 많이 쓰이는 구나
  • 어떤 자료 구조를 구현할 때 어렵다? 하면
    • 배열스택큐해시테이블 이런걸 좀 더 쓰면 해결할 수 있을까 고민하면 쉬워짐.