INTRO

[자료구조란]
컴퓨터에서 자료들을 정리하고 조직화하는 다양한 구조
목적 : 데이터의 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행

선형 자료구조 목차

항목들을 순서적으로 나열하여 저장하는 구조

• 리스트: 자유로운 선형 자료구조, 임의의 위치에 항목을 삽입, 삭제 가능
• 스택, 큐, 덱: 항목의 접근이 맨 앞이 나 맨 뒤로 제한됨

배열

연결 리스트

스택, 큐

데크, 우선순위 큐 learn

• deque
• list와 차이점, 장점
• collections.deque의 메소드(method)들

해시 테이블(해시 맵) learn

• 해싱 Hashing
• 비둘기집 원리(서랍 원리) Pigeonhole Principle
  • 생일 문제 Birthday Problem
• 로드 팩터 Load Factor
• 충돌 Collision의 처리 방법
  • 개별 체이닝 Separate Chaining
  • 오픈 어드레싱 Open Addressing

비선형 자료구조 목차

항목들이 보다 복잡한 연결 관계를 갖는 구조

• 트리 : 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조
  • 힙 트리 : 우선순위 큐의 효율적인 구현
  • 이진 탐색트리, AVL트리 : 탐색을 위한 트리 구조
• 그래프 : 가장 복잡한 연결 관계를 표현
  • 다양한 문제를 해결하기 위한 기본 구조로 사용됨

그래프 learn

• 그래프 이론 유래
• 오일러의 경로(Eulerian path)
• 해밀턴 경로(Hamiltonian Path)

그래프 순회_깊이 우선 탐색:DFS/넓이 우선 탐색: BFS learn

• 그래프 순회 Graph Traversals
• 순회를 위한 그래프 준비
• 깊이 우선 탐색(Depth First Search : DFS)
  • 재귀 구현
  • 스택 구현
• 백트래킹 Backtracking
  • 제약 충족 문제 Constraint Satisfaction Problems
• 넓이 우선 탐색(Breadth-First Search : BFS)
  • 큐 구현
  • BFS의 장점
  • BFS의 단점
  • 재귀 구현 불가

다익스트라 알고리즘(Dijkstra algorithm) learn

• 외판원 문제 Travelling Salesman Problem(TSP)
• 최단 경로(shortest path)
• 다익스트라 알고리즘(Dijkstra algorithm)
• 구현

NP learn

최단경로

TREE

트리 기본개념, 이진트리 learn

• 트리
• 트리의 기본 개념
  • 그래프 vs 트리
• 이진트리 Binary Tree
• 탐방
  • 중순위 탐방 LDR
  • 전순위 탐방 DLR
  • 후순위 탐방 LRD

이진 탐색 트리 learn

• 이진 탐색 트리 Binary Search Tree (BST)
• 자가 균형 이진 탐색 트리 Self-Balancing Binary Search Tree
  • AVL tree
  • 레드-블랙 tree

트리 노드 삭제 learn

• 트리 노드 삭제
  • leaf 노드 삭제
  • single child를 갖은 노드 삭제
  • two child를 갖은 노드 삭제
• 구현
  • python 구현
  • java 구현