데이터 구조란?
데이터를 저장하고 구성하는 데 사용되는 저장소.
컴퓨터에서 데이터를 정리해 효율적으로 액세스하고 업데이트할 수 있는 방법.
데이터를 구성할 때 뿐만 아니라, 데이터를 처리, 검색 및 저장하는 데에도 사용됨.
데이터 구조의 분류
1. 선형 데이터 구조
데이터 요소가 순차적으로 또는 선형적으로 배열되고, 각 요소가 이전 및 다음 인접 요소에 연결된 데이터 구조
예) 배열, 스택, 큐, 연결 리스트 등
2. 정적 데이터 구조
고정된 메모리 크기를 갖고, 해당 요소에 액세스하기 쉬움
예) 배열
3. 동적 데이터 구조
크기가 고정되지 않고, 코드의 메모리(공간) 복잡도와 관련해 효율적이라고 판단되면 런타임 중에 무작위로 업데이트 가능
예) 큐, 스택 등
4. 비선형 데이터 구조
데이터 요소가 순차적으로 또는 선형적으로 배치되지 않는 데이터 구조
단일 실행으로 모든 요소를 순회할 수 없음
예) 트리 및 그래프
1. 배열
- 동일한 데이터 유형의 요소 컬렉션을 함께 저장하는 선형 데이터 구조
- 연속된 메모리 위치에 저장된 데이터 항목의 모음
- 각 요소는 연속된 메모리에 할당되어 일정한 시간 액세스(constant-time access)가 가능
- 각 요소에는 고유한 인덱스 번호가 존재
2. 행렬(매트릭스/그리드)
- 행렬은 행과 열로 배열된 요소의 2차원 배열.
- 각 요소가 행과 열의 교차점에 있는 직사각형 그리드로 표현.
- 행렬의 요소를 괄호나 대괄호로 묶어야 함.
3. 문자열
- 일반적으로 텍스트를 나타내는 데 사용되는 문자 시퀀스
- 컴퓨터 프로그램에서 텍스트 데이터의 조작 및 처리를 허용하는 데이터 유형으로 간주됨
4. 스택
- 후입선출(LIFO) 원칙을 따르는 선형 데이터 구조
- 연산이 수행되는 특정 순서를 따르고, 모든 삽입과 삭제는 목록의 한쪽 끝에서만 허용됨
- 함수 호출, 메모리를 관리하는 데 중요한 역할을 하며 알고리즘, 웹 개발, 컴파일러 및 브라우저와 같은 시스템에서 널리 사용
스택 연산:
- push(): 스택에 요소 삽입
- pop(): 스택 맨 위의 요소가 제거되어 반환
- top(): 맨 위에 삽입된 마지막 요소를 제거하지 않고 반환
- size(): 스택의 크기, 즉 스택에 있는 총 요소의 개수 반환
- isEmpty(): 스택이 비어있는지 여부 반환
5. 대기열(큐)
- 선입선출(FIFO) 원칙을 따르는 선형 데이터 구조
- 큐에서 요소는 한쪽 끝에 삽입되고 다른 쪽 끝에서 삭제됨
- 작업이나 데이터를 순서대로 관리하고, 스케줄링하고, 메시지 처리 시스템에서 중요한 역할
큐 연산:
- Enqueue(): 큐의 끝에 요소 추가
- Dequeue(): 큐에서 요소 제거
- Peek() 또는 front(): 큐의 앞부분 노드에 있는 데이터 요소를 삭제하지 않고 반환
- rear(): 요소를 제거하지 않고 뒷부분 노드에 있는 요소 반환
- isFull(): 대기열이 가득 찼는지 확인
- isNull(): 큐가 비어있는지 확인
6. 연결 리스트
- 포인터로 연결된 노드에 데이터를 저장하는 선형 데이터 구조
- 배열과 달리 연결 리스트의 노드는 연속된 메모리 위치에 저장되지 않으며 리스트의 헤드부터 순차적으로만 액세스 가능
각 요소는 포인터를 사용하여 연결됨
7. 해시
- 해시 함수라고 하는 수학 공식을 사용해 가변 크기의 입력에서 고정 크기의 출력(해시 값)을 생성하는 기술.
- 주어진 값을 특정 키와 매핑하여 요소에 더 빠르게 액세스할 수 있도록 함.
- 매핑의 효율성은 사용된 해시 함수의 효율성에 따라 달라짐.
- 해싱은 일반적으로 효율적인 검색, 삽입 및 삭제를 위한 데이터 구조에서 사용되며 보안 데이터 검색, 암호 저장, 암호화, 디지털 서명 등과 같은 소프트웨어 애플리케이션에서 핵심적인 역할.
8. 트리
- 엣지로 연결된 노드로 구성된 비선형 계층적 데이터 구조.
- 루트라고 하는 최상위 노드와 자식 노드가 있는 노드로 구성.
- 검색 복잡도를 최적의 한계(키 길이)로 줄일 수 있고, O(M) 시간 안에 키를 검색할 수 있음.
그러나, 스토리지 요구사항에 대한 패널티가 있음.
- 파일 시스템, 데이터베이스, 의사 결정 알고리즘 등에서 널리 사용.
9. 이진 트리
- 각 노드가 최대 두 개의 자식(왼쪽 자식과 오른쪽 자식)을 갖는 비선형적이고 계층적인 데이터 구조.
- 주로 링크를 사용하여 구현.
- 이진트리는 트리의 최상위 노드를 가리키는 포인터로 표현.
- 트리가 비어있으면 루트의 값은 NULL.
- 이진 트리 노드에는 1. 데이터, 2. 왼쪽 자식에 대한 포인터, 3. 오른쪽 자식에 대한 포인터가 포함됨.
10. 이진 탐색 트리(BST, Binary Search Tree)
- 각 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값만 포함되고, 각 노드의 오른쪽 서브 트리에 노드보다 큰 값만 포함되는 이진 트리.
- 해당 속성은 재귀적으로 적용되므로 모든 노드의 왼쪽 및 오른쪽 서브 트리도 이진 탐색 트리의 조건을 충족해야 함.
- 중복된 키가 존재하지 않음.
- 키를 저장하는 경우 균형 잡힌 BST는 M*logN에 비례하는 시간이 필요. (M: 최대 문자열 길이, N: 트리의 키 수)
11. 힙
- 힙 속성을 만족하는 완전 이진 트리 데이터 구조.
- 일반적으로 우선순위 큐를 구현하는 데 사용하고, 가장 작거나 가장 큰 요소는 항상 트리의 루트에 위치.
- 최대 힙: 최대 힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 하고, 동일한 속성이 해당 이진 트리의 모든 하위 트리에 대해 재귀적으로 참이어야 함
- 최소 힙: 최소 힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 하고, 동일한 속성이 해당 이진 트리의 모든 하위 트리에 대해 재귀적으로 참이어야 함
12. 그래프
- 유한한 정점(또는 노드) 집합과 노드 쌍을 연결하는 엣지(또는 링크) 집합으로 구성된 비선형 데이터 구조.
- 엔티티 간의 관계를 나타내는 데 널리 사용되며, 컴퓨터 과학, 수학 및 기타 분야에서 널리 사용.
- 소셜 네트워크, 교통 네트워크 및 컴퓨터 네트워크와 같은 다양한 실제 시스템을 모델링하는 데 사용 가능.
13. 고급 데이터 구조
- 복잡한 알고리즘을 더 빠르고 효과적인 처리를 가능하게 하는 복잡한 데이터 배열.
- 데이터를 효율적으로 구성, 저장 및 조작하는 데 사용.
- 배열 및 연결 리스트와 같은 기본 데이터 유형과 달리 세그먼트 트리, 트라이(Trie), 이진 인덱스 트리, 접미사 배열 등과 같은 보다 정교한 옵션을 포함.
'자료구조, 알고리즘' 카테고리의 다른 글
| 프로그래머스 코딩테스트 연습 [두 수의 연산값 비교하기] (0) | 2025.02.21 |
|---|---|
| 프로그래머스 코딩테스트 연습 [더 크게 합치기] (0) | 2025.02.21 |
| 프로그래머스 코딩테스트 연습 [문자열 섞기] (0) | 2025.02.20 |
| 프로그래머스 코딩테스트 연습 [문자열 겹쳐쓰기] (0) | 2025.02.19 |
| 프로그래머스 코딩테스트 연습 [대소문자 바꿔서 출력하기] (0) | 2025.02.19 |