- 복잡도
- 시간 복잡도
- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.
- 빅오 표기법
- 어떠한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내는데 쓰인다.
- 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것인데, 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없애서 표기한다. 예를 들어 어떤 알고리즘의 복잡도가 10n^2+5n이라면 O(n^2)이 된다.
- 시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
- 크게 O(n^2), O(n), O(log n), O(1) 순으로 입력 크기가 커질수록 효율적이다.
- 공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다.
- 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다.
- 자료 구조에서의 시간 복잡도
- 보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려해서 쓴다.
- 시간 복잡도
각 자료 구조의 평균 시간 복잡도
자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
배열(array) | O(1) | O(n) | O(n) | O(n) |
스택(stack) | O(n) | O(n) | O(1) | O(1) |
큐(queue) | O(n) | O(n) | O(1) | O(1) |
이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
이진 탐색 트리(BST) | O(log n) | O(log n) | O(log n) | O(log n) |
AVL 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
레드 블랙 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
각 자료 구조의 최악의 시간 복잡도
자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
배열(array) | O(1) | O(n) | O(n) | O(n) |
스택(stack) | O(n) | O(n) | O(1) | O(1) |
큐(queue) | O(n) | O(n) | O(1) | O(1) |
이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
해시 테이블(hash table) | O(n) | O(n) | O(n) | O(n) |
이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
AVL 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
레드 블랙 트리 | O(log n) | O(log n) | O(log n) | O(log n) |
- 선형 자료 구조
- 요소가 일렬로 나열되어 있는 구조를 말한다.
- 연결 리스트
- 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다.
- prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이며, 싱글, 이중, 원형이 있다.
- 싱글 연결 리스트 - next 포인터만 가진다.
- 이중 연결 리스트 - next 포인터와 prev 포인터를 가진다.
- 원형 이중 연결 리스트 - 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
- 맨 앞에 있는 노드를 헤드라고 한다.
- 배열
- 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
- 중복을 허용하고 순서가 있다.
- 정적 배열을 기반으로 랜덤 접근이 가능하다.
- 랜덤 접근 - 직접 접근이라고도 하며 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능이다. 이와 반대로 데이터를 저장된 순서대로 검색해야 하는 순차적 접근이 있다.
- 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용한다.
- 데이터 추가와 삭제를 많이 할 때는 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
- 벡터
- 동적으로 요소를 할당할 수 있는 동적 배열이다.
- 컴파일 시점에 개수를 모른다면 벡터를 써야 한다.
- 중복을 허용하고 순서가 있고 랜덤 접근이 가능하다.
- 스택
- 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조이다.
- 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.
- 큐
- 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 가진 자료 구조이다.
- 스택과는 반대되는 개념을 가진다.
- CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용한다.
- 연결 리스트
- 요소가 일렬로 나열되어 있는 구조를 말한다.
- 비선형 자료 구조
- 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 자료 구조를 말한다.
- 그래프
- 정점과 간선으로 이루어진 자료 구조를 말한다.
- 정점과 간선 - 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때 어떠한 곳이 정점, 무언가는 간선이 된다.
- 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 indegree라고 한다.
- outdegree만 있거나 indegree만 있다면 단방향 간선이고, 둘 모두 있다면 양방향 간선이 된다.
- 가중치 - 간선과 정점 사이에 드는 비용을 말한다.
- 정점과 간선으로 이루어진 자료 구조를 말한다.
- 트리
- 그래프 중 하나로 그래프처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합이다.
- 루트 노드, 내부 노드, 리프 노드 등으로 구성된다.
- 루트 노드 - 가장 위에 있는 노드를 뜻한다. 보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다.
- 내부 노드 - 루트 노브와 리프 노드 사이에 있는 노드를 뜻한다.
- 리프 노드 - 자식 노드가 없는 노드를 뜻한다.
- 부모, 자식 계층 구조를 가진다. 같은 경로상에서 어떤 노드보다 위에 있으면 부모, 아래 있으면 자식 노드가 된다.
- 간선 수는 노드 수 - 1 이다.
- 임의의 두 노드 사이의 경로는 하나만 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다.
- 깊이 - 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리를 말한다. 레벨이라고도 한다.
- 높이 - 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리를 의미한다.
- 서브트리 - 트리 내의 하위 집합을 말한다. 트리 내의 부분집합이라고도 보면 된다.
- 이진 트리
- 자식의 노드 수가 2개 이하인 트리를 의미하며, 아래와 같이 구분된다.
- 정이진 트리 - 자식 노드가 0 또는 두 개인 이진 트리를 말한다.
- 완전 이진 트리 - 왼쪽에서부터 채워져 있는 이진 트리를 말한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
- 변질 이진 트리 - 자식 노드가 하나밖에 없는 이진 트리를 말한다.
- 포화 이진 트리 - 모든 노드가 꽉 차 있는 이진 트리를 말한다.
- 균형 이진 트리 - 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 말한다. map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나이다.
- 이진 탐색 트리
- 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다. 이 특성은 하위 트리에도 적용되어있다.
- 이와 같은 특성은 검색에서 용이하다.
- AVL 트리
- 트리가 최악의 경우인 선형적 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다.
- 두 자식 서브트리의 높이는 항상 최대 1만큼 차이나는 특징이 있다.
- 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡는다.
- 레드 블랙 트리
- 균형 이진 탐색 트리로 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용된다.
- "모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 등의 규칙을 기반으로 균형을 잡는 트리이다.
- 힙
- 완전 이진 트리 기반의 자료 구조이며, 최소힙과 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다.
- 최대힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한, 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
- 최소힙 - 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
- 어떠한 값이 들어와도 특정 힙의 규칙을 지키게 만들어져 있다. 최대힙을 기반으로 예시를 살펴보자.
- 최대힙의 삽입
- 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
- 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환해서 힙의 성질을 만족시킨다.
- 최대힙의 삭제
- 최대힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성된다.
- 우선순위 큐
- 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조이다.
- 힙을 기반으로 구현된다.
- 맵
- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조이다.
- 셋
- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 unique한 값만 저장하는 자료구조이다.
- 해시 테이블
- 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다.
- 그래프
- 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 자료 구조를 말한다.
'TIL > CS' 카테고리의 다른 글
조인 (0) | 2023.10.25 |
---|---|
데이터베이스의 종류/ 인덱스 (0) | 2023.10.25 |
트랜잭션과 무결성 (0) | 2023.10.25 |
ERD와 정규화 과정 (0) | 2023.10.24 |
데이터베이스 (0) | 2023.10.24 |