자료구조 (Data Structure)
효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법
배열 (Array)
동일한 자료형의 데이터를 일렬로 나열하는 구조
연결 리스트 (Linked List)
각 노드가 데이터와 포인터를 가지고 일렬로 연결되어 있는 방식으로 데이터 저장
스택(Stack)
삽입, 삭제연산이 한 방향에서 이루어짐
LIFO(Last In First Out) 구조
스택에 데이터가 삽입될 위치를 Top 이라고 함
큐(Queue)
한 방향에서는 삽입연산, 한 방향에서는 삭제연산이 이루어짐
FIFO(First In First Out) 구조
데이터가 삭제될 위치를 First/Head, 마지막 데이터가 삽입된 위치를 Rear/Tail 이라고 함
덱(Deque)
양 방향에서 삽입, 삭제연산이 모두 이루어지는 큐
트리(Tree)
자료 사이의 계층적 관계 나타낼때 사용(부모-자식 관계)
1개 이상의 노드를 갖는 집합
-
다음의 조건 만족
- 루트 노드 존재
- 트리의 부분트리 또한 트리 구조 따름
-
주요 개념
- 루트 노드 : 트리의 최상위 노드
- 부모 노드 : 부모 자식 관계에서 상위 계층에 있는 노드
- 자식 노드 : 부모 자식 관계에서 하위 계층에 있는 노드
- 형제 노드 : 부모가 동일한 노드
- 깊이(Depth) : 루트 노드에서 해당 노드까지 도달하는데 사용된 간선 개수(루트 노드의 깊이는 0)
- 레벨(Level) : 노드의 깊이 + 1
- 높이(Height) : 루트 노드에서 해당 노드까지 도달하는데 지나간 정점 개수
- 노드의 분지 수(차수, Degree) : 노드의 자식 수
이진 트리(Binary Tree)
트리의 분지 수가 2 이하인 트리
자식이 최대 2개
높이가 N인 이진 트리의 최대 노드 개수는 2^N -1개
- 정 이진 트리 (Full Binary Tree)
모든 노드의 차수가 0 또는 2인 이진 트리
- 포화 이진 트리 (Perfect Binary Tree)
정 이진 트리에서 모든 단말 노드의 깊이가 같은 이진 트리- 높이가 h인 포화 이진 트리의 노드 개수는 2^h-1
- 노드개 n개인 포화 이진 트리의 높이는 log₂(n+1)
- 깊이가 d인 포화 이진 트리의 단말 높이 개수는 2^d개
- 완전 이진 트리 (Complete Binary Tree)
마지막 레벨은 노드가 왼쪽에 몰려있고, 마지막 레벨을 제외하면 포화 이진 트리 구조를 띄고 있는 이진 트리
힙(Heap)
완전 이진트리 형태의 자료구조
데이터의 삽입, 삭제 연산의 수행시간이 O(logN)
- 최소 힙(Min Heap)
부모노드의 키 값이 자식노드의 키 값보다 항상 작음
트리 내에서 가장 작은 키 값을 가지는 노드는 항상 루트 노드
- 최대 힙(Max Heap)
부모노드의 키 값이 자식노드의 키 값보다 항상 큼
트리 내에서 가장 큰 키 값을 가지는 노드는 항상 루트 노드
- 우선순위 큐(Priority Queue)
각 데이터에 우선순위를 부여, 큐에 넣은 데이터를 꺼낼 때 우선순위가 높은 데이터를 먼저 꺼내는 자료구조
인덱스트리 (Indexed Tree)
포화 이진트리 형태의 자료구조
탐색과 수정이 모두 O(logN)
리프노드가 n개 이상인 포화 이진트리의 높이는 최소 logN
-
각 노드가 아래와 같은 의미 가짐 (ex. 구간합 트리)
- 리프노드 : 배열에 적혀있는 수
- 내부노드 : 왼쪽 자식과 오른쪽 자식의 합
-
인덱스트리 만들기
- 리프 노드의 개수가 배열 크기 이상이 되도록 높이가 t인 트리 배열을 만들기(배열 크기는 2^t)
- 리프 노드에 데이터 입력
- 내부 노드의 데이터 채우기 → 양쪽 자식 값 참조
- 부모 노드의 인덱스가 index일때
- left child 인덱스 = index * 2
- right child 인덱스 = index * 2 +1
부모 노드와 자식 노드의 관계는 합, 최대/최소 등으로 설정할 수 있음
해싱 (Hashing)
입력된 데이터(Key)를 해시 함수를 통해 얻은 주소로부터 그 위치를 직접 참조하는 방법
탐색, 삽입, 삭제 연산 모두 O(1)
셋 (Set)
집합을 정의하는 자료구조
집합의 모든 원소는 유일 → 중복이 허용되지 않음
맵 (Map)
key와 value로 이루어진 객체를 저장하는 자료구조
key 값의 중복 허용X, value는 제약 없음
