자료구조
자료구조는 데이터를 효율적으로 저장하고 관리할 수 있는 방식이나 구조를 말한다. 데이터가 어떻게 저장되느냐에 따라 처리 성능이 달라지므로, 다양한 문제를 해결하기 위해 여러 종류의 자료구조가 사용된다.
자료구조의 중요성
자료구조는 두 가지 주요 요소에 영향을 미친다.
1. 시간 복잡도
데이터에 접근하거나 수정하는 데 걸리는 시간을 말한다. 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
시간 복잡도는 최악일 때의 연산 횟수를 나태낸 빅-오 표기법을 사용한다.
상수는 시간 복잡도 계산에서 제외되며 , 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
2. 공간 복잡도
데이터를 저장하는 데 필요한 메모리의 양을 말한다.
자료구조의 종류
1. 선형 구조
선형 구조는 데이터가 일렬로 나열된 형태이다. 데이터 간의 순서가 중요하며, 각 원소는 하나의 이전 원소와 하나의 다음 원소를 가진다.
배열(Array)
고정된 크기를 가지며, 인덱스를 통해 데이터에 접근한다. 장점은 인덱스를 이용한 빠른 접근이 가능하지만, 크기를 미리 지정해야 하고, 중간에 데이터를 삽입하거나 삭제하는 것이 비효율적이다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 잇는 값을 이동시키는 과정이 필요하기 때문이다.
배열 A: [10, 20, 30, 40, 50]
인덱스: 0 1 2 3 4리스트(List)
값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다. 배열과 비슷하지만, 크기를 동적으로 조정할 수 있다. 배열처럼 연속적인 메모리 공간에 데이터를 저장하는 것과 다르게, 연결리스트(Linked List)에서는 각 요소가 이전과 다음 요소에 대한 포인터를 가지고 있어, 삽입과 삭제가 더 효율적이다. 하지만 배열처럼 인덱스로 바로 접근할 수 없어서, 데이터를 찾기 위해 처음부터 끝까지 순차적으로 탐색해야한다.
단일 연결리스트(Singly Linked List): 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가진다.이중 연결리스트(Doubly Linked List): 각 노드가 데이터와, 이전 및 다음 노드를 가리키는 두 개의 포인터를 가진다.
연결리스트: 10 -> 20 -> 30 -> 40 -> 50스택(Stack)
후입선출(LIFO, Last In First Out) 방식으로 동작한다. 데이터를 한 쪽에서만 삽입하거나 삭제할 수 있다.
예를 들어, 책 더미를 쌓을 때 제일 위에 놓은 책이 나중에 제일 먼저 꺼내진다. 브라우저의 뒤로가기 기능 버튼을 누르면 마지막으로 방문한 페이지가 먼저 나온다.
큐(Queue)
선입선출(FIFO, First In First Out) 방식으로 동작한다. 데이터가 한 쪽 끝에서 삽입되고, 다른 쪽 끝에서 삭제된다.
예를 들어, 줄을 서면 먼저 온 사람이 먼저 티켓을 살 수 있다. 프린터 대기열은 여러 명이 프린터를 사용할 때, 문서가 대기하는 순서대로 출력된다.
우선순위 큐
큐의 일종으로, 일반적인 FIFO(선입선출) 방식과 달리, 각 요소가 우선순위를 가지고 있다. 우선순위가 높은 요소가 먼저 처리된다.
- 특징
우선순위 큐에서는 데이터를 삽입할 때, 각 데이터에 우선순위를 부여한다. 데이터가 큐에서 꺼내질 때는 우선순위가 높은 데이터가 먼저 나온다. - 구현 방법
우선순위 큐는 일반적으로 힙을 이용해서 구현된다. 힙을 사용하면 우선순위 큐의 삽입과 삭제 연산이O(log n)의 시간 복잡도를 가진다. - 힙을 이용해서 구현하는 이유
우선순위 큐에서 가장 우선순위가 높은 데이터(가장 작은 값이나 가장 큰 값)를 빠르게 꺼내야 할 때, 힙을 사용하면 매우 효울적이다. 힙은O(log n)시간 복잡도로 데이터를 삽입하고 삭제할 수 있기 때문이다. 반면 배열을 사용하면 최솟값을 찾기 위해O(n)의 시간 복잡도가 걸린다. 따라서 배열이나 연결리스트를 사용해서 우선순위 큐를 구현할 수 있지만, 삽입/삭제 시 효율성이 떨어지기 때문에 힙을 사용한다.
우선순위 큐: [(10, 1), (20, 3), (30, 2)]해시 테이블(Hash Table)
파이썬에서는 딕셔너리 자료형이 해시 테이블과 같은 방식으로 작동한다. 데이터를 키(key)와 값(value) 쌍으로 저장하는 자료구조로, 데이터를 빠르게 검색할 수 있는 매우 효율적인 방법을 제공하다. 키를 해시 함수에 넣어서 그 키에 해당하는 인덱스를 계산하고, 해당 인덱스에 값을 저장한다.
- 특징
해시 테이블은 충돌(Collision)을 처리하는 방식이 중요하다. 두 개 이상의 키가 동일한 해시 값을 가질 경우 충돌이 발생하는데, 이를 해결하기 위한 방법으로 체이닝(Chaining)이나 오픈 주소법(Open Addressing)을 사용한다. - 해시 함수
해시 함수는 키를 특정한 크기의 배열 인덱스로 변환하는 함수이다. 좋은 해시 함수는 가능한 한 키가 균등하게 분포되도록 해야 충돌을 최소화할 수 있다. - 시간 복잡도
검색, 삽입, 삭제가 평균적으로O(1)의 시간 복잡도를 가진다. 다만, 최악의 경우에는 충돌이 심할 경우O(n)이 될 수 있다. - 딕셔너리(dict)나 맵(Map) 자료구조, 중복 요소 체크 등에 사용한다.
- 해시맵과의 차이점
-해시 테이블: 해시 테이블은 고전적인 자료구조로, 키를 해시 함수로 해시하여 배열에 저장하는 방식이다. 기본적으로 동기화가 되어 있으며, 병렬 처리를 고려한 설계가 필요할 때 스레드 안전한 방식으로 구현된다. null값을 허용하지 않는다. 멀티스레드 환경에서 안전하게 사용할 수 있다.
-해시 맵: 해시 맵은 해시 테이블의 변형으로, 스레드 안전성을 고려하지 않는 경우가 많다. 기본적으로 스레드가 안전하지 않으며, 멀티스레드 환경에서는 동기화를 별도로 추가해야 할 수 있다. null값을 허용한다. 단일 스레드 환경에서 최적화된 성능을 보인다.
해시 테이블:
키: 10 -> 값: "apple"
키: 20 -> 값: "banana"
# 예를 들어 해시함수가 키 % 5로 설정되었다면 10 % 5 == 0 , 20 % 5 == 0 이므로
# 모두 인덱스 0에 저장된다. -> 충돌
# 충돌 해결 방법: 체이닝(Chaining): 같은 인덱스를 가진 데이터들을 연결리스트(Linked List) 형태로 저장
해시 테이블:
인덱스 0: [(10, "apple") -> (20, "banana")]
인덱스 1: []
인덱스 2: []
인덱스 3: []
인덱스 4: []
# 해시 테이블
table = {1: "One", 2: "Two", 3: "Three"}
# 키를 None으로 삽입 시 오류 발생
try:
table[None] = "Null Key" # None은 키로 사용할 수 없습니다.
except TypeError as e:
print("오류:", e) # TypeError: unhashable type: 'NoneType'
# 값에 None을 사용할 수는 있습니다
table[4] = None
print(table) # {1: 'One', 2: 'Two', 3: 'Three', 4: None}
# 해시 맵
hash_map = {1: "One", 2: "Two", 3: "Three"}
# 정상적으로 키와 값으로 None을 사용할 수 있음
hash_map[4] = None # 값으로 None을 넣는 건 허용
hash_map[None] = "Null Key" # 키로 None도 넣을 수 있음
print(hash_map) # {1: 'One', 2: 'Two', 3: 'Three', 4: None, None: 'Null Key'}2. 비선형 구조
비선형 구조는 데이터들이 일렬로 연결되지 않고, 여러 방향으로 확장되는 형태이다. 데이터 간의 관계가 더 복잡하다.
트리(Tree)
트리는 계층적인 구조로, 각 노드는 부모 노드와 자식 노드를 가질 수 있다. 트리는 탐색, 삽입, 삭제 등의 연산이 효율적으로 수행될 수 있는 구조이다. 가장 많이 사용되는 트리 자료구조는 이진트리이다.
-
특징
- 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
- 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
- 트리의 부분 트리 역시 트리의 모든 특징을 따른다.
- 트리에서 임의의 두 노드를 이어주는 경로는 유일하다. -
구성 요소
-노드: 데이터의 index와 value를 표현하는 요소
-에지: 노드와 노드의 연결 관계를 나타내는 선
-루트 노드: 트리에서 가장 상위에 존재하는 노드
-부모 노드: 두 노드 사이의 관계에서 상위 노드에 해당하는 노드
-자식 노드: 두 노드 사이의 관계에서 하위 노드에 해당하는 노드
-리프 노드: 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
-서브 트리: 전체 트리에 속한 작은 트리
이진 탐색 트리(Binary Search Tree, BST)
이진 트리에서 왼쪽 자식은 부모보다 작은 값을 가지며, 오른쪽 자식은 부모보다 큰 값을 가진다.
10 # 루트 노드
/ \ # 에지
# 부모노드 20 30
/ \ / \
# 자식노드 40 50 60 70 # 리프 노드 - 이진 트리(Binary Tree): 각 노드가 최대 2개의 자식을 가질 수 있는 트리이다.
- `편향 이진 트리`: 노드들이 한쪽으로 편향돼 생성된 이진 트리
- `포화 이진 트리`: 트리의 높이가 모두 일정하며 **리프 노드가 꽉 찬 이진 트리**
- `완전 이진 트리`: 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리이다.
```python
# 편향 이진 트리 # 포화 이진 트리 # 완전 이진 트리
A A A
/ / \ / \
B B C B C
/ / \ / \ / \
C D E F G D F
```힙(Heap)
힙은 완전 이진 트리의 일종으로, 트리 구조에서 부모 노드와 자식 노드 사이에 특정한 관계를 유지하는 자료구조이다. 힙은 주로 우선순위 큐를 구현할 떄 사용된다.
- 특징
최대힙(Max Heap: 부모 노드가 자식 노드보다 크거나 같음)과 최소힙(Min Heap: 부모 노드가 자식 노드보다 작거나 같음)을 갖는다. 힙은 완전 이진 트리이기 때문에, 트리의 모든 레벨이 꽉 차고, 마지막 레벨을 왼쪽부터 차례대로 채워진다. - 주요 연산
- 삽입: 새로운 요소를 힙에 추가할 때, 트리의 마지막에 삽입하고, 부모와 자식을 비교하면서 위치를 조정한다.
- 삭제: 힙에서 가장 큰 값(최대 힙의 경우) 또는 가장 작은 값(최소 힙의 경우)을 제거한다. 제거 후 트리 구조를 다시 맞추기 위해 힙화(Heapify)라는 과정을 거친다.
- 시간 복잡도: 삽입과 삭제 연산의 시간 복잡도는O(log n)이다.
그래프(Graph)
그래프는 노드(정점)와 이들을 연결하는 간선(엣지)으로 구성된 자료구조이다. 그래프는 유향(Directed) 또는 무향(Undirected)으로 나타낼 수 있으며, 여러 경로를 통해 데이터나 정보를 전달할 때 사용된다. 소셜 네트워크, 지도상의 위치 관계 등에 사용된다.
그래프의 표현 방법에는 에지 리스트, 인접 행렬, 인접 리스트가 있다.
에지 리스트: 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.인접 행렬: 2차원 배열을 자료구조로 이용하여 그래프를 표현한다. 인접 행렬은 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.인접 리스트: 인접 리스트는 ArrayList로 그래프를 표현한다. 노드 개수만큼 ArrayList를 선언한다.
# 유향 그래프
A → B → C
↓ ↑
D ← E
# 무향 그래프
# 1. 인접 행렬
Alice Bob Charlie Dave
Alice 0 1 1 0
Bob 1 0 1 1
Charlie 1 1 0 1
Dave 0 1 1 0
# 2. 인접 리스트
graph = {
"Alice": ["Bob", "Charlie"],
"Bob": ["Alice", "Charlie", "Dave"],
"Charlie": ["Alice", "Bob", "Dave"],
"Dave": ["Bob", "Charlie"]
}