자료구조(Data Structure)
1. 문자열
둘 이상의 결합된 문자
- 불변성 : 기존 객체의 값을 바꾸는 것이 아닌 수정된 값을 가진 객체를 생성
- 문자열 끝에는 널 문자(종단문자, '\n') 반드시 들어감
없다면 출력시 쓰레기값이 같이 출력됨
2. 배열
연속된 메모리 공간에 순차적으로 저장된 데이터 모음
| 작업 | average case | worst case |
| 접근(read) | O(1) | O(1) |
| 삽입 및 추가(insert) | O(n) | O(n) |
| 삭제(delete) | O(n) | O(n) |
| 조회(search) | O(n) | O(n) |
- 동일한 데이터 유형을 가짐
- 각 요소에 접근하는 시간은 O(1) => 인덱스로 바로 접근 가능
- 연속된 메모리에 단일 블록화하여 데이터 저장(낭비되는 공간이 적음)
- 삽입 및 삭제시 모든 요소를 움직여줘야 하기 때문에 비용이 많이 들게 됨 O(n)
- 물리적으로 데이터가 순차적으로 저장되기 때문에 순서와 index가 있으며, 인덱싱과 슬라이싱이 가능
- indexing : index를 사용해 특정 요소를 리스트로부터 읽어들이는 것
- slicing : 요소에 특정 부분을 따로 분리해 조작하는 것
3. 연결 리스트(Linked List)
데이터를 감싼 노드에 포인터를 연결한 공간적인 효율성 좋은 자료구조
동적 추가, 삭제 효율적 / 특정 위치의 노드 검색 비효율적(차례대로 접근)
- 단순 연결 리스트 : Head에서 부터 Tail까지 다음 노드의 위치를 가리키면서 이동하는 구조(마지막 포인터는 NULL)
- 이중 연결 리스트 : 각 노드가 이전 노드와 다음 노드를 모두 참조하는 링크드 리스트
- 원형 연결 리스트 : Tail이 Head를 참조하는 링크드 리스트
4. 스택(Stack)
후입선출(LIFO : Last In, First Out) : 가장 나중에 들어온 데이터가 가장 먼저 나감(ex. 웹 페이지 뒤로가지, 문서작업 되돌리기 기능)
- 상단(stack top) : 스택에서 입출력이 이루어지는 부분
- 하단(stack bottom): 반대쪽 바닥 부분
- 요소(element): 스택에 저장되는 것
- 공백 스택(empty stack): 공백 상태의 스택
- 포화 스택(full stack): 포화 상태의 스택(풀스택)
스택의 연산
| 연산 | 기능 |
| top() | 스택 맨 위에 있는 데이터 값 반환 |
| push() | 스택에 데이터 삽입 |
| pop() | 스택에서 데이터 삭제하여 반환 |
| isempty() | 스택에 원소가 없으면 'True', 있으면 'False' 값 반환 |
| isfull() | 스택에 원소가 없으면 'False', 있으면 'True' 값 반환 |
5. 큐(Queue)
선입선출(FIFO : First In, First Out / LILO : Last In, Last Out) : 가장 먼저 들어온 데이터가 가장 먼저 나감 / 가장 나중에 들어온 데이터가 가장 나중에 나감(ex. 은행 대기표, 수강신청 등)
데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나는 구조
데이터는 front에서 삭제, rear에서 삽입
- enqueue() - 큐에 끝(rear)에 항목을 추가
- dequeue() - 큐에 맨 앞(front)에 항목을 제거
- peek() - 큐에 맨 앞(front)에 있는 항목을 반환
- isfull() - 큐가 가득 찼는지 확인
- isempty() - 큐가 비어 있는지 확인
| 작업 | Average | Worst |
| 접근(Access) | Θ(n) | O(n) |
| 검색(Search) | Θ(n) | O(n) |
| 삽입(Insert)(enqueue) | Θ(1) | O(1) |
| 삭제(Delete)(dequeue) | Θ(1) | O(1) |
6. 우선순위 큐(Priority Queue)
먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조
힙(Heap)을 이용해 구현
더보기
최대 힙(Max Heap)
최소 힙(Min Heap)
힙이란?
힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조
특징
- 완전이진트리의 형태로 이루어짐(완전이진트리랑 비슷하지만 노드간 대소관계 명확함)
- 부모노드와 서브트리간의 대소 관계가 성립함(반정렬 상태)
- 이진탐색트리(BST)와 달리 중복된 값이 허용됨
종류
- 최대 힙(Max Heap)
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리
📝 key(부모노드) ≥ key(자식노드)
- 최소 힙(Min Heap)
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리
📝 key(부모노드) ≤ key(자식노드)
[출처]
7. 맵(Map)
Map은 Key와 Value 한 쌍으로 이루어진 자료형(딕셔너리와 동일)
- Key는 중복을 허용하지 않음(Unique)
- List와는 다르게 순서가 없고 key로 매핑해 value를 반환함
- 객체의 속성(Property)을 자주 변경해야 할 때 유리함
[출처]
8. 해시 테이블(Hash Table)
key, value로 데이터를 저장하는 자료구조
빠르게 데이터를 검색할 수 있는 자료구조
- 각각의 key값에 해시함수(hash function)를 적용해 배열에 고유한 index를 생성하고, 이것을 버킷(슬롯)에 저장
- 고유한 index를 통해 값을 저장하거나 검색함
- key값으로 데이터를 찾기 때문에 함수를 한 번만 수행하면 됨 O(1)
[출처]
'크래프톤 정글 - TIL' 카테고리의 다른 글
| 크래프톤 정글 5기 TIL - Day 6(CS:APP) (0) | 2024.03.23 |
|---|---|
| 크래프톤 정글 5기 TIL - Day 5-3 (0) | 2024.03.22 |
| 크래프톤 정글 5기 TIL - Day 5-1 (2) | 2024.03.22 |
| 크래프톤 정글 5기 TIL - Day 4 (0) | 2024.03.21 |
| 크래프톤 정글 5기 - 에세이 (0) | 2024.03.21 |
