자료구조 [ Data Structure ]
1. Array [ 배열 ] : 조회 유리
∘ 컴파일 시점에 할당되어지는 정적 메모리 할당
∘ 논리적 저장 순서 == 물리적 저장 순서
∘ 메모리 공간 상에 연속적으로 저장
∘ immutable
∘ Random Access 가능 ⇨ index를 알고 있으면 O(1)의 시간복잡도로 원소에 접근 가능
∘ 삽입 & 삭제 : O(N)
2. ArrayList [ 동적 배열 ]
∘ 사이즈를 동적으로 생성할 수 있는 배열
∘ Object Element만을 담을 수 있다.
∘ Generic 사용 가능
3. Linked List : 삽입&삭제 유리
∘ runtime 시점에 할당되어지는 동적 메모리 할당
∘ 논리적 저장 순서 != 물리적 저장 순서
∘ 메모리 공간 상에 불연속적으로 저장 & 각각의 노드가 자신의 다음 노드를 알고 있는 형태
∘ 조회 : O(N)
∘ 삽입, 삭제 : O(N)이지만 Array보다 빠르다.
앞뒤에만 삽입하면 O(1)
4. Stack
∘ LIFO (Last In First Out)
∘ 시간복잡도, 공간복잡도 : O(N)
∘ 스택 포인터(SP) 필요 : default = -1
ex) 함수의 call 스택, 문자열 역순 출력, 연산자 후위 표기법
ex) 웹페이지 뒤로가기 / undo / 역순문자열 / 후위표기법 / 괄호 연산
5. Queue
∘ FIFO (First In First Out)
∘ 시간복잡도, 공간복잡도 : O(N)
ex) 버퍼, bfs
ex) 대기열 관리 / 스케줄러 / BFS / Cache 구현 / Buffer
6. Heap [ 우선순위 큐 ]
∘ 우선순위가 높은 데이터가 큐에서 먼저 빠져나가는 자료구조
∘ 배열을 기반으로 한 완전 이진 트리 (Complete Binary Tree) ⇨ index를 통한 Random Access 가능
∘ 최대힙 ( root가 최댓값 ) , 최소힙 ( root가 최솟값)
∘ root == arr[1] / arr[x] 의 자식 : arr[x*2], arr[x*2+1]
∘ 중복값 허용
∘ 조회 O(1)
∘ 삽입 O(logN) : 마지막 노드에 삽입 ⇨ 부모 노드와 비교해나가며 swap
∘ 삭제 O(logN) : 루트노드 삭제 ⇨ 힙의 마지막 노드를 root 노드로 가져옴 ⇨ 힙 재구성
ex) 시뮬레이션, 작업 스케줄링,
⁕ Heapify : 일반 배열을 heap 자료구조로 만드는 과정
7. Tree
∘ 계층적 관계를 표현하는 비선형 자료구조
∘ 각 노드의 부모 노드는 단 하나 ( root 제외 )
∘ 노드(Node) + 간선(Edge)
∘ 사이클이 없는 그래프
∘ 노드의 개수 N ⇨ 간선의 개수 N-1
∘ 순회 방식 : 전위 & 중위 & 후위 & 레벨 순회
∘ Binary Tree [ 이진 트리 ]
∘ 임의의 노드를 중심으로 나뉜 두 서브트리가 모두 이진트리
8. Binary Search Tree [ BST : 이진 탐색 트리 ]
∘ 이진 탐색 + 연결리스트 : 두 장점을 모두 얻기 위해 고안
∘ 노드의 키는 유일 ( 중복 X )
ⅰ. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
ⅱ. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
ⅲ. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
∘ 중위순회로 정렬된 데이터를 얻을 수 있다.
∘ 조회 : 평균 O(logN) / 최악(편향트리) O(N)
∘ 삭제
ⅰ. 단말노드 : 그냥 삭제
ⅱ. 자식이 1개인 노드 : 지워진 노드에 자식을 올린다.
ⅲ. 자식이 2개인 노드 : 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값으로 대체
∘ 편향트리에서의 조회 시간복잡도를 개선하기 위해 Rebalancing(트리 구조 재조정) 필요
⇨ AVL Tree, RB Tree 존재
⁕ 이진트리는 두개의 자식밖에 가지지 못하며, 균형이 맞지 않으면 검색 효율이 선형 검색급으로 떨어진다.
하지만 이진트리의 간결함과 균형이 맞을때의 성능O(logN) 등의 장점으로 이를 개선시키기 위한 노력이 이루어진다.
9. AVL Tree
∘ BST의 한계점을 보완하기 위해 만들어진 균형이진트리
∘ 항상 좌/우로 데이터를 균형잡힌 상태로 유지하기 위해 추가 연산 진행
10. Red-Black Tree
∘ depth를 최소화하여 시간 복잡도를 줄이고자 하는 BST 기반 트리
∘ 모든 노드를 빨간색, 검은색으로 칠하여 연결된 노드들의 색이 다르게 관리
∘ 삽입되는 노드의 색을 Red로 지정 → 조정
∘ 조회, 삽입, 삭제 : O(logN)
∘ 성질
ⅰ. 모든 노드의 색 : Red or Black
ⅱ. Root Node, Leaf Node : Black
ⅲ. Red Node의 자식은 모두 Black Node
ⅳ. Leaf Node → Root Node 경로(simple path)의 Black Node의 수(black height) 는 모두 같다.
11. B Tree
∘ DB, 파일 시스템에서 사용되는 트리의 일종 ( 보통 인덱스 저장 방법으로 사용 )
∘ 자식수 증가 + 트리 균형을 자동으로 맞춰주는 로직 ⇨ 단순하고 효율적인 균형트리
∘ 각 노드에 key, data 모두 들어갈 수 있다.
∘ 하나의 노드에 많은 데이터를 가질 수 있다 ⇨ 대량의 데이터 처리 유리
∘ 균일성 : 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다. O(logN)
∘ 성질
ⅰ. 노드의 자료수가 N개면 자식 수는 N+1
ⅱ. Root의 자식은 최소 2개
ⅲ. 각 노드의 자료는 정렬된 상태
ⅳ. 중복 X
12. B+ Tree
∘ B Tree + 연결리스트
∘ 데이터의 빠른 접근을 위한 인덱스 역할의 비단말 노드 추가
∘ 각 노드에는 key만 존재, Leaf Node에 data 존재
장점
ⅰ. key값에 대한 엑세스 주소가 없어 블럭 사이즈를 더 많이 이용할 수 있다.
ⅱ. Leaf 노드가 연결리스트로 이루어져 있어 범위 탐색 & 임의 접근 & 순차 접근 유리
단점
ⅰ. 탐색시 무조건 Leaf 노드까지 내려가봐야 한다.
13. Trie
∘ 텍스트 자동완성과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조
∘ key : 하나의 알파벳, value : 그 key에 해당하는 자식 노드
∘ 자식 노드를 Map<Key, value> 형태로 가지고 있다.
14. Hash
∘ 내부적으로 배열을 사용하여 데이터 저장
∘ 해시 알고리즘을 이용해 고유한 인덱스를 얻음
∘ 인덱스를 이용하여 빠른 검색속도를 갖는다. - 적은 자원으로 많은 데이터를 효율적으로 관리 가능
∘ 시간복잡도 : O(1) - Hash : 가변길이 데이터를 고정길이 데이터로 매핑한 값
∘ Hash Function : 수학적 연산을 통해 고정길이 데이터로 매핑하는 함수
∘ Hash Table : key-value를 매핑해둔 데이터 구조
∘ 데이터가 많아지면 다른 데이터가 같은 hash값을 가지게 된다 : 해시 충돌
∘ 충돌 해결 방법
∘ Seperate Chaining : key가 가리키는 자료구조를 LinkedList로 이용하는 방식
데이터 검색시 선형탐색을 하므로 느리다 O(N)
LinkedList 대신 Tree를 사용하면 성능 개선 가능
∘ Open Addressing : 해시 충돌이 발생하면 다른 주소 공간에 데이터를 저장하는 방식
1. 선형 탐사 : 현재 주소 + 고정 크기(x) 에 저장
2. 제곱 탐사 : 현재 주소 + 제곱수(x^2)에 저장
3. 이중 해싱 : 다른 해시함수를 한번 더 적용
4. 재해싱 : 해시 테이블 크기를 늘리고 모든 데이터를 다시 해싱
∘ HashTable : Map 인터페이 구현을 위해 HashTable을 사용한 클래스, key-value에 null O
∘ HashMap : 속도는 느리지만 동기화를 지원하며, key-value에 null X
15. Graph
∘ 정점과 간선의 집합
∘ Undirected vs. Directed (방향성 존재 여부)
∘ Weight vs. Sub (가중치 존재 여부)
∘ 구현방법 : 인접행렬, 인접리스트
∘ 탐색방법 : DFS (V+E), BFS (V+E)
∘ MST (Minimum Spanning Tree) : 최소비용 트리 => 크루스칼