목차
1. 복잡도
1. 시간 복잡도
- 입력에 대해 어떤 동작이 실행되는 데 걸리는 시간.
- 주요 로직의 반복 횟수를 중점으로 측정되며, 통상 빅 오 표기법으로 나타냄.
- 알고리즘(혹은 코드)의 효율성을 측정하는 척도임.
- 여러 자료 구조에서 시간 복잡도는 최악, 평균, 최선의 시나리오에 따라 다른데, 통상 효율성을 얘기할 땐 평균 시나리오를 상정한 시간 복잡도를 말함.
2. 공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.
- Java 자료형별 크기 및 메모리 용량별 저장 가능 개수는 아래와 같음.
| 정수 자료형 | 크기 | 128MB 기준 | 256MB 기준 |
|---|---|---|---|
| byte | 1바이트 | 약 1.3억개 저장 가능 | 약 2.6억개 저장 가능 |
| short | 2바이트 | 약 6,500만개 저장 가능 | 약 1.3억개 저장 가능 |
| int | 4바이트 | 약 3,300만개 저장 가능 | 약 6,700만개 저장 가능 |
| long | 8바이트 | 약 1,600만개 저장 가능 | 약 3,300만개 저장 가능 |
| 실수 자료형 | |||
| float | 4바이트 | 약 3,300만개 저장 가능 | 약 6,700만개 저장 가능 |
| double | 8바이트 | 약 1,600만개 저장 가능 | 약 3,300만개 저장 가능 |
| 논리/문자 자료형 | |||
| boolean | 1바이트 | 약 1.3억개 저장 가능 | 약 2.6억개 저장 가능 |
| char | 2바이트 | 약 6,500만개 저장 가능 | 약 1.3억개 저장 가능 |
3. 빅 오 표기법
- 데이터 증가량에 따른 알고리즘의 실행 단계 증가량을 수학적으로 나타낸 것.
- 엄밀한 수학적 정의: 함수 T(n)이 O(f(n))이라는 것은, 충분히 큰 n에 대해 T(n) ≤ C·f(n)을 만족하는 양의 상수 C와 n0가 존재함을 의미함.
- 대표적인 빅 오 복잡도(빠른 순):
O(1): 상수 시간 (constant)O(log n): 로그 시간 (logarithmic)O(n): 선형 시간 (linear)O(n log n): 선형 로그 시간 (linearithmic)O(n^2): 이차 시간 (quadratic)O(2^n): 지수 시간 (exponential)
- 단, 실제 효율성은 상황에 따라 다를 수 있음 (즉, 상수 시간이라고 반드시 선형 시간보다 빠른 건 아님).
4. 자료 구조별 시간 복잡도
[평균 시나리오]
| 자료 구조 | 접근 (Access) | 탐색 (Search) | 삽입 (Insertion) | 삭제 (Deletion) |
|---|---|---|---|---|
| 배열(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) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | 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) |
| 힙(Heap) | O(n) | O(n) | O(log n) | O(log n) |
| 그래프(Graph) (인접 리스트) |
O(1) | O(V + E) | O(1) | O(V + E) |
[최악 시나리오]
| 자료 구조 | 접근 (Access) | 탐색 (Search) | 삽입 (Insertion) | 삭제 (Deletion) |
|---|---|---|---|---|
| 배열(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) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | 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) |
| 힙(Heap) | O(n) | O(n) | O(log n) | O(log n) |
| 그래프(Graph) (인접 리스트) |
O(1) | O(V + E) | O(1) | O(V + E) |
핵심 포인트: 효율성을 논할 때는 주로 평균 시나리오를 기준으로 하지만, 최악의 경우(Worst Case)도 반드시 고려해야 함.
2. 자료 구조
- 자료 구조란 메모리 상에 저장된 데이터와 그 데이터들 간의 관계를 정의한 집합임.
- 선형 자료 구조: 데이터가 일렬로 나열된 집합을 말함.
- 비선형 자료 구조: 데이터가 일렬로 나열되지 않고 특정 규칙에 따라 배치된 집합을 말함.
2.1 선형 자료구조
1) 배열 (Array)
- 동일한 데이터 타입의 요소들을 연속적인 메모리 공간에 나열해 모아놓은 집합.
- 임의 접근(Random Access)이 가능해서 데이터 접근이 매우 빠름.
- 임의 접근: 자료를 순차적으로 조사하지 않고도 특정 부분을 곧바로 검색할 수 있는 접근 방식.
- 삽입, 삭제는 O(n)이라 데이터 추가, 삭제가 잦다면 연결 리스트를 사용하는 게 더 나음.
2) 연결 리스트 (Linked List)
- 데이터와 다음 데이터의 주소(포인터)를 담은 노드(Node)들을 일렬로 연결시켜 모아놓은 집합.
- 실제 데이터들은 메모리상에 불연속적으로 분포하지만, 포인터 덕분에 연속된 것처럼 보임.
- 데이터를 추가, 삭제할 때 다음 데이터의 주소만 잘 적어주면 되니 O(1)로 매우 빠름.
- 다만 데이터를 읽을 땐 앞에서부터 순차적으로 포인터를 타며 찾아가야 하니 O(n)으로 느린 편임.
- 종류: 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트.
- Java에선
LinkedList가 유명함.
3) 스택 (Stack)
- 가장 나중에 들어간 데이터가 가장 먼저 나오도록 만든 집합 (LIFO).
- 삽입, 삭제는 O(1)이지만 탐색은 O(n)이 걸림.
- 구조적으로 특별하다기보단, 데이터를 다루는 규칙(제약)이 특별한 것뿐임.
- 실제로 Java에선 평범한
ArrayList도 스택처럼 사용할 수 있음.
4) 큐 (Queue)
- 가장 먼저 들어간 데이터가 가장 먼저 나오도록 만든 집합 (FIFO).
- 삽입, 삭제는 O(1)이지만 탐색은 O(n)이 걸림.
- Java에선
LinkedList나ArrayDeque를 큐처럼 쓸 수 있음.
2.2 비선형 자료 구조
1) 그래프 (Graph)
- 데이터를 담고 있는 정점(Vertex)과 그 정점들을 연결하는 간선(Edge)들로 이루어진 집합.
- 정점 A → 정점 B 처럼 일방적으로 이어진 간선을 단방향 간선, A ↔ B 양방향으로 이어진 간선을 양방향 간선이라고 부름.
- Java 기준, 그래프를 구현한 클래스는 별도로 존재하지 않고 2차원 배열이나 인접 리스트(
List<List>)를 사용해 구현함. - 데이터 추가는 정점에 데이터를 담고, 간선으로 잇기만 하면 되니 O(1).
- 데이터 탐색은 간선을 왕복하며 데이터가 담긴 정점을 찾아야 하니 O(V+E) (정확히는 V+2E인데 빅 오 표기법에선 상수를 무시함).
- 가중치: 정점과 정점 사이의 간선을 이동하는 데 드는 비용을 말함.
2) 트리 (Tree)
- 하나의 루트 노드에서 시작해 데이터들이 부모-자식 관계를 맺으며 계층적으로 연결된 노드들의 집합.
- 그래프의 종류 중 하나지만, 엄격한 제약 조건이 달린 집합임.
- 모든 노드는 부모(상위)와 자식(하위)의 서열을 가진 계층형 집합임.
- 집합 내부의 연결이 순환 구조를 띄면 안 됨 (비순환 구조).
- 집합에 접근하는 입구는 오직 하나, 루트뿐임 (단일 진입점).
- 관련 개념
- 노드: 트리라는 집합을 구성하는 개별 데이터(원소) 하나하나를 지칭. 값과 하위 노드를 가리키는 주소(포인터)로 구성됨.
- 루트 노드: 부모가 없는 최상위 노드.
- 내부 노드: 자식 노드를 하나 이상 가지고 있는 노드.
- 리프 노드: 자식 노드가 없는, 트리 집합의 가장 말단에 위치한 노드.
- 트리 종류
- 이진 트리: 각 노드에 딸린 자식 노드가 두 개 이하로만 구성된 트리. (종류: 정이진 트리, 완전 이진 트리, 변질 이진 트리, 포화 이진 트리, 균형 이진 트리)
- 완전 이진 트리(Complete Binary Tree): 왼쪽부터 채워져 있는 이진 트리. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 채워져 있어야 함.
- 이진 탐색 트리(BST): 왼쪽 서브 트리 집합 < 부모 노드 < 오른쪽 서브 트리 집합의 대소 관계 규칙을 모든 노드에서 만족하는 트리. 데이터 크기에 따라 좌, 우로 명확하게 배치되므로 검색이 O(log n)으로 매우 빠름. 단, 삽입 순서가 꼬이면 O(n)까지 늘어나기도 함.
- AVL 트리: 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차가 1 이하인 이진 탐색 트리. 항상 균형 잡힌 상태를 유지하므로 삽입, 삭제, 탐색 모두 O(log n)임.
- 레드 블랙 트리: 각 노드에 색상(Red or Black)을 나타내는 비트를 저장해 대략적인 균형을 유지하도록 만든 트리. 삽입, 삭제, 탐색 모두 O(log n)이지만, AVL 트리 대비 조건이 덜 빡빡해 삽입, 삭제가 상대적으로 빠른 편. 삽입, 삭제, 탐색 효율성이 최적의 타협을 이루기 때문에 Map, Set 구현에 주로 사용됨. (Java 기준, TreeMap, HashMap이 레드 블랙 트리로 구현돼 있음)
3) 맵 (Map)
- 고유한 식별자(Key)와 데이터(Value)가 한 쌍을 이룬 객체들의 집합.
- 모든 Key는 집합 내에서 유일해야 한다는 규칙을 가짐 (Value는 중복돼도 상관없음).
- 해시 테이블 구현 시 사용됨.
- Java 기준,
HashMap,LinkedHashMap,TreeMap,ConcurrentHashMap구현체가 있음.
4) 셋 (Set)
- 데이터의 순서와 상관없이 중복된 값을 허용하지 않는다는 규칙을 가진 집합.
- Map을 사용해 구현하는 경우가 많은데, 이는 Map의 ‘모든 Key는 유일하다’는 성질을 활용한 것임 (Key에 데이터를 넣고 Value는 더미로 아무 값이나 채워서 중복 방지 기능만 사용함).
5) 힙 (Heap)
- 부모 노드가 자식 노드보다 항상 크거나(또는 작거나) 같아야 한다는 규칙을 만족하는 완전 이진 트리 형태의 집합.
- 최대힙: 부모 노드가 자식 노드보다 항상 크거나 같은 경우.
- 최소힙: 부모 노드가 자식 노드보다 항상 작거나 같은 경우.
- 줄 세우기(정렬)보단 대장(1등)을 빨리 뽑는 것이 목적인 집합.
6) 우선순위 큐
- 각 데이터의 우선순위(Priority)가 높은 순서대로 나가는 규칙을 가지는 집합.
- 통상 힙(Heap)을 기반으로 구현됨.
- Java 기준,
PriorityQueue구현체가 가장 흔하게 쓰임.
7) 해시 테이블
- (Key, Value) 쌍으로 이루어진 데이터들의 집합으로, Key에 특별한 함수(해시 함수) 처리를 통해 데이터가 저장될 메모리 주소를 얻어내고, 해당 메모리 주소에 데이터를 저장하는 자료 구조.
- 삽입, 삭제, 탐색이 O(1)으로 매우 효율적임.
- 다만, 해시 충돌이란 물리적 한계가 존재함 (세상의 데이터는 무한하지만, 메모리의 저장공간은 유한하기 때문 → 비둘기집 원리).
핵심 포인트: 데이터의 형태와 사용 목적에 따라 적합한 자료 구조를 선택하는 것이 성능 최적화의 첫걸음임.