Big-O
big-O에는 다양한 실행 시간이 존재하지만 자주 사용 되는 것들은 아래와 같습니다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
시간복잡도 구하는 요령
하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n m) -> O (n²)
컬렉션 정렬을 사용하는 경우 : O(nlog(n))
Array vs Linked List
배열 (Array)
배열은 선형 자료구조의 대표적인 예로, 동일한 데이터 타입의 요소들이 연속적인 메모리 공간에 저장됩니다. 배열의 특징과 사용법은 다음과 같습니다:
- 고정된 크기: 배열은 생성 시 크기가 고정되며, 이후에는 크기를 변경할 수 없습니다.
- 빠른 접근: 인덱스를 통해 O(1) 시간 복잡도로 요소에 접근할 수 있습니다.
- 비효율적인 삽입/삭제: 배열의 중간에 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동해야 하므로 O(n)의 시간 복잡도가 발생합니다.
배열은 데이터의 크기가 고정되어 있고, 인덱스를 통한 빠른 접근이 필요한 상황에 적합합니다.
연결 리스트 (Linked List)
연결 리스트는 배열과 달리 각 요소가 데이터와 다음 요소를 가리키는 포인터를 함께 저장하는 구조입니다. 연결 리스트는 크기가 가변적이며, 삽입 및 삭제가 용이합니다.
종류에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있습니다.
연결 리스트는 삽입과 삭제가 빈번하게 발생하는 상황에서 유리합니다.
그러나 특정 인덱스의 요소에 접근하기 위해 처음부터 탐색해야 하므로, 접근 속도는 배열보다 느립니다.
백터 (Vector)
백터는 동적 배열로, 크기가 자동으로 조정되는 배열입니다.
자바에서의 ArrayList가 백터의 대표적인 예입니다.
백터는 다음과 같은 특징을 가지고 있습니다:
- 동적 크기: 요소가 추가될 때 자동으로 크기가 조정됩니다.
- 빠른 접근: 배열과 마찬가지로 인덱스를 통한 O(1) 시간 복잡도로 요소에 접근할 수 있습니다.
- 메모리 오버헤드: 크기가 동적으로 조정되기 때문에 메모리 사용량이 비효율적일 수 있습니다.
백터는 크기가 자주 변하는 데이터를 관리할 때 유용하며, 배열보다 유연한 대안입니다.
Stack and Queue
스택 (Stack)
스택은 후입선출(LIFO) 구조를 가지며, 마지막에 삽입된 요소가 가장 먼저 제거됩니다.
주요 연산으로는 push(요소 추가), pop(요소 제거), peek(요소 조회) 등이 있습니다.
스택은 재귀적인 알고리즘, 괄호 짝 맞추기, 웹 브라우저의 뒤로 가기 기능 등에서 자주 사용됩니다.
큐 (Queue)
큐는 선입선출(FIFO) 구조를 가지며, 먼저 삽입된 요소가 먼저 제거됩니다.
주요 연산으로는 enqueue(요소 추가), dequeue(요소 제거), peek(요소 조회) 등이 있습니다.
큐는 데이터가 순차적으로 처리되어야 하는 상황에서 사용되며, BFS(너비 우선 탐색)와 같은 알고리즘에서 활용됩니다.
Tree
트리 (Tree)
트리는 계층적 구조를 표현하기 위한 비선형 자료구조입니다.
트리는 루트 노드를 중심으로 여러 자식 노드를 가지며, 이 자식 노드들 또한 자신의 자식을 가질 수 있습니다.
트리는 이진 트리, 이진 탐색 트리, AVL 트리 등 다양한 종류가 있습니다.
트리를 구성하고 있는 구성요소들(용어)
- Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
- Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
- Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
- Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
- Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
Binary Tree (이진 트리)
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 트리의 특징은 다음과 같습니다:
- 완전 이진 트리: 모든 레벨이 꽉 찬 이진 트리입니다.
- 포화 이진 트리: 모든 노드가 두 개의 자식 노드를 가지며, 마지막 레벨을 제외한 모든 레벨이 꽉 차 있습니다.
- 이진 탐색 트리: 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큽니다.
이진 트리는 데이터 탐색, 정렬, 효율적인 데이터 저장을 위해 자주 사용됩니다.
AVL 트리 (AVL Tree)
AVL 트리는 자가 균형 이진 탐색 트리로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 자동으로 균형을 맞춥니다. 삽입이나 삭제 시 트리의 균형이 깨지면 회전 연산을 통해 균형을 복원합니다.
AVL 트리는 삽입, 삭제, 탐색 연산에서 O(log n)의 시간 복잡도를 유지하기 때문에, 효율적인 검색과 정렬이 요구되는 상황에서 유리합니다.
레드블랙 트리 (Red-Black Tree)
레드블랙 트리는 또 다른 자가 균형 이진 탐색 트리로, 노드에 색깔(레드 또는 블랙)을 부여하여 트리의 균형을 유지합니다.
레드블랙 트리는 AVL 트리보다 조금 덜 엄격하게 균형을 유지하기 때문에, 삽입과 삭제가 더 빠르게 이루어질 수 있습니다.
레드블랙 트리는 주로 데이터베이스나 파일 시스템에서 사용됩니다.
힙 (Heap)
힙은 완전 이진 트리의 일종으로, 부모 노드가 자식 노드보다 크거나 작은 특성을 가집니다.
이 특성에 따라 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉩니다.
힙은 주로 우선순위 큐의 기본 자료구조로 사용됩니다.
힙은 정렬된 데이터를 관리하거나, 가장 큰/작은 요소를 빠르게 찾는 경우에 유용합니다.
우선순위 큐 (Priority Queue)
우선순위 큐는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다. 우선순위 큐는 힙을 사용하여 구현되는 경우가 많습니다.
우선순위 큐는 작업 스케줄링, 시뮬레이션 시스템 등에서 자주 사용됩니다.
맵 (Map)
맵은 키-값 쌍으로 데이터를 저장하는 자료구조로, 해시 테이블을 이용해 구현됩니다.
각 키는 유일하며, 키를 통해 값에 빠르게 접근할 수 있습니다.
자바에서는 HashMap, TreeMap 등이 맵의 대표적인 구현체입니다.
맵은 데이터베이스 인덱싱, 캐싱, 집합 연산 등에서 사용됩니다.
셋 (Set)
셋은 유일한 요소들로 이루어진 집합을 표현하는 자료구조로, 중복된 값을 허용하지 않습니다.
해시 테이블을 기반으로 한 HashSet, 정렬된 순서를 유지하는 TreeSet 등이 자바에서의 셋 구현체입니다.
셋은 집합 연산, 중복 제거 등에서 유용하게 사용됩니다.
해시 테이블 (Hash Table)
hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Search 하는데 데이터 고유의 인덱스로 접근하게 되므로 average case 에 대하여 Time Complexity 가 O(1)이 되는 것이다.(항상 O(1)이 아니고 average case 에 대해서 O(1)인 것은 collision 때문이다.)
해시 테이블은 키를 해시 함수로 변환하여 값을 저장하는 자료구조로, 매우 빠른 검색 속도를 제공합니다. 해시 테이블의 주요 특징은 다음과 같습니다:
- O(1)의 시간 복잡도: 평균적으로 O(1) 시간 내에 데이터에 접근할 수 있습니다.
- 해시 충돌 처리: 동일한 해시 값을 가진 키가 존재할 수 있으므로, 이를 처리하기 위한 방법이 필요합니다.
해시 테이블은 데이터베이스, 캐시, 검색 알고리즘 등에서 널리 사용됩니다.
해시 충돌을 해결방법
1. Open Address 방식 (개방주소법)
해시 충돌이 발생하면, (즉 삽입하려는 해시 버킷이 이미 사용 중인 경우)
다른 해시 버킷에 해당 자료를 삽입하는 방식 이다.
버킷이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.
공개 주소 방식이라고도 불리는 이 알고리즘은 Collision 이 발생하면 데이터를 저장할 장소를 찾아 헤맨다. Worst Case 의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다. 이 과정에서도 여러 방법들이 존재하는데, 다음 세 가지에 대해 알아보자.
Linear Probing 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.
Quadratic probing 2 차 함수를 이용해 탐색할 위치를 찾는다.
Double hashing probing 하나의 해쉬 함수에서 충돌이 발생하면 2 차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구하게 된다.
2. Separate Chaining 방식 (분리 연결법)
일반적으로 Open Addressing 은 Separate Chaining 보다 느리다. Open Addressing 의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다. Java 7 에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다. Separate Chaining 방식으로는 두 가지 구현 방식이 존재한다.
-
연결 리스트를 사용하는 방식(Linked List) 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다. 또 다른 특징으로는, 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.
-
Tree 를 사용하는 방식 (Red-Black Tree) 기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 개수가 적다면 링크드 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터 개수가 적을 때 Worst Case 를 살펴보면 트리와 링크드 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 링크드 리스트를 사용한다.
데이터가 적다는 것은 얼마나 적다는 것을 의미하는가? 앞에서 말했듯이 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 이 키-값 쌍의 개수가 6 개, 8 개를 기준으로 결정한다. 기준이 두 개 인것이 이상하게 느껴질 수 있다. 7 은 어디로 갔는가? 링크드 리스트의 기준과 트리의 기준을 6 과 8 로 잡은 것은 변경하는데 소요되는 비용을 줄이기 위함이다.
한 가지 상황을 가정해보자. 해시 버킷에 6 개 의 key-value 쌍이 들어있었다. 그리고 하나의 값이 추가되었다. 만약 기준이 6 과 7 이라면 자료구조를 링크드 리스트에서 트리로 변경해야 한다. 그러다 바로 하나의 값이 삭제된다면 다시 트리에서 링크드 리스트로 자료구조를 변경해야 한다. 각각 자료구조로 넘어가는 기준이 1 이라면 Switching 비용이 너무 많이 필요하게 되는 것이다. 그래서 2 라는 여유를 남겨두고 기준을 잡아준 것이다. 따라서 데이터의 개수가 6 개에서 7 개로 증가했을 때는 링크드 리스트의 자료구조를 취하고 있을 것이고 8 개에서 7 개로 감소했을 때는 트리의 자료구조를 취하고 있을 것이다.
Open Address vs Separate Chaining
일단 두 방식 모두 Worst Case 에서 O(M)이다. 하지만 Open Address방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다.
따라서 데이터의 개수가 충분히 적다면 Open Address방식이 Separate Chaining보다 더 성능이 좋다.
한 가지 차이점이 더 존재한다. Separate Chaining방식에 비해 Open Address방식은 버킷을 계속해서 사용한다. 따라서 Separate Chaining 방식은 테이블의 확장을 보다 늦출 수 있다.
보조 해시 함수
보조 해시 함수(supplement hash function)의 목적은 key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다. Separate Chaining 방식을 사용할 때 함께 사용되며 보조 해시 함수로 Worst Case 에 가까워지는 경우를 줄일 수 있다.
