자료구조 : 효율적으로 데이터를 관리하고 수정 삭제 탐색 저장하는 데이터 집합
빅오표기법 : 시간복잡도 : 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
-효율적인 코드로 개선하는데 쓰이는 척도
공간복잡도 : 프로그램을 실행시켰을때 필요로 하는 자원의양
연결리스트 : 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조
삽입학세 0(1), 탐색 O(n)
배열 : 같은 타입의 변수들로 이루어져 있고 크기가 정해져있으며 메모리 위치에 있는 데이터를 모아놓은 집합, 중복 허용하고 순서가 있다.
연결리스트는 상자를 선으로 연결한 데이터 구조, 상자 안의 요소를 확인할때 내부 확인해야한다.
배열은 랜덤접근가능 O(1), 연결리스트 랜덤접근 불가능 O(n)
백터 : 동적으로 요소를 할당하는 동적배열, 컴파일이시 개수 모르면 벡터사용, 중복허용 순서있고 랜덤접근 가능
스택: 가장 마지막으로 들어간 데이터가 첫번째로 나온다. LIFO
삽입삭제 O(1), 탐색 O(n)
큐: 먼저넣은게 먼저 나온다. FIFO, 삽입삭제 O(1), 탐색 O(n)
그래프 : 정점과 간선으로 이루어진 자료구조
가중치 : 간선과 정점사이에 드는 비용
트리 : 그래프중 하나,정점과 간선, 계층적 데이터의 집합
특징: 부모 자식 계층 구조, 간선수 = 노드수 -1
루트 노드 : 가장위에 잇는 노드
내부 노드 : 루트 노드와 내부 노드 사이 노드
리프노드 : 자식 노드가 없는 노드
깊이, 높이, 레벨, 서브트리
이진트리 : 자식 노드 수가 두개 이하
정이진 트리 , 완전 이진트리, 변질이진트리, 포화이진트리, 균형이진트리
이진 탐색 트리 : 오른쪽 노드값보다 큰거, 왼쪽 노드값보다 작은가,검색하기 용이하다 검색시 O(logn) 최악 O(n)
AVL트리 : 최악의 경우 선형적 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진탐색트리 , 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다.
탐색 삽입삭제 시간복잡도 O(logn)
레드블랙트리: 균형 이진탐색트리, 탐색 삽입 삭제 모두 시간복잡도 O(logn)
힙: 완전 이진 트리기반의 자료구조
최대힙, 최소힙
우선순위 큐: 우선순위 대기열, 우선순위 높은 요소가 낮은 요소보다 먼저 제공된다.
맵: 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
셋: 특정 순서에 따라 고유한 요소를 저장하는 컨테이너, 중복 없고 유니크값만 저장
해시테이블 : 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑
O(1)
Q1. 시간복잡도란 무엇인가. -> 공간복잡도란 무엇인가
Q2. 배열이란? ->연결리스트란? -> 둘의 차이는? 둘의 시간복잡도는?
Q3. 이진탐색트리의 특징,
