[ C.S 지식 정리 : 자료 구조 ]
알고리즘 공부 하기 전 필요한,
자료구조 기초 지식들.
∇ 알고리즘을 위한, 자료구조 기초 지식.
목 차
1. 자료구조란??
2. 자료구조 분류
Ⅰ. 자료구조란?
- 데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며,
자료에 대한 처리를 효율적으로 수행가능하도록 자료를 구분해 표현한 것. !
∇ ex) 책장으로 본 자료구조 배치.
○ 1번 : 책장의 모든 공간을 사용 가능하지만,
처음 책(자료)을 배치한 후에,
추후에 새로운 책(자료)을 추가할 때 비집고 넣거나, 순서를 찾아야 하는 수고로움이 생깁니다.
○ 2번 : 분야별로 책(자료)을 쉽게 찾을 순 있지만, 공간배치의 비효율이 생깁니다.
○ 3번 : 2번보다는 더 효율적으로 공간을 사용할 수 있지만, 줄을 넘기면서 배치될 때, 헷갈림이 발생 가능 !
☆ 책장 == "메모리" // 책 == "데이터"
Ⅱ. 자료구조 분류
A . Primitive Data Structure ( 단순 구조 )
√ '단순구조'는 프로그래밍에서 사용되는 간단한 데이터 타입입니다.
√ Number, String, Boolean 등 기본적인 정보를 나타내는데 사용하고,
이러한 데이터 타입은 언어 자체에 내장되어 있어서 바로 사용 가능합니다.
[ Ex. Number - 6, String - 'Go Home' , Boolean - true ]
B . Non - Primitive Data Structure ( 비단순 구조 )
√ '비단순구조'는 여러개의 기본 데이터를 모아서 하나의 큰 단위로 다루는 방법입니다.
== 여러 종류의 재료를 사용해서 레고 블록을 만드는 것과 비슷.
√ 사용자가 필요에 따라 직접 정의해서 만들 수 있음.
[ Ex, 여러 정보를 담는 주소록, 학생 정보를 저장하는 데이터. ]
C . Linear Data Structure ( 선형 구조 )
√ '선형구조' 는 데이터가 일렬로 나열되어 있는 형태를 의미합니다.
√ 마치 책장에 책을 정리하는 것처럼, 데이터들 간에 순서를 만들어서 한 방향으로 연결하는 것을 의미.
D . Non - Linear Data Structure ( 비선형 구조 )
√ '비선형구조' 는 데이터가 계층적이거나 복잡하게 연결되어 있는 형태를 의미합니다.
√ 마치 나무의 가지처럼 여러 갈래로 뻗어나가거나, 이리저리 얽혀있는 땅의 길처럼 보이는 것과 비슷.
[ Ex, 가계도 구조, 등 ]
E . 시간 복잡도 & 공간 복잡도.
√ 시간 복잡도와 공간 복잡도는 알고리즘의 성능을 평가하는 중요한 지표입니다.
1. Arrays (배열구조)
○ 자료형을 원소로 취급해, 나열한 것! - 요소들을 일렬로 나열한 선형 구조.
○ 기본적으로 배열의 크기는 정해져있습니다.
○ 동일한 타입의 데이터들을 저장합니다.
○ '인덱싱'이 되어있어서 인덱스를 통해 빠르게 데이터에 접근 가능!
- 인덱스를 통해 접근하며, 같은 타입의 데이터를 저장 가능.
○ 총 갯수가 정해진 자료를 다룰 때 유용합니다.
● 배열 목록, 힙, 해시테이블, 벡터 및 행렬과 같은 기타 데이터 구조들을 구축하기 위한 빌딩 블록으로 사용합니다!
● 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘들에 활용됩니다.
2. Linked - Lists (리스트)
○ 하나의 자료가 다른 자료를 가리키면서, 자료를 축적해나가는 구조.
○ 총 갯수가 정해져 있지 않은 자료들을 다룰 때 유용합니다.
○ '배열'에 비해서, 빈 공간을 낭비하지 않습니다.
○ 인덱스가 없으므로, 접근시 배열과 달리 한 번에 원하는 자료를 찾아가기 어렵습니다.
○ 각 요소는 Node이고, Node 안에는 key와 다음 노드를 가리키는 포인터(next)가 포함.
== 노드들이 연결되어 있는 선형 구조.
○ 노드 추가/삭제가 상대적으로 편리함.
○ 첫 번째 요소는 Head, 마지막 요소는 Tail.
3. Stack ( 선형 자료구조 )
○ 데이터를 차곡차곡 쌓아 올리는 선형 구조.
○ "맨 위" 에 있는 데이터에만 접근 가능 !
○ 순서가 보존되는 선형 데이터 구조입니다.
○ 가장 마지막에 넣은 요소부터 처리하는 LIFO(Last In Fist Out) - 후입선출 구조.
4. Queue( 선형 자료구조 )
○ 데이터를 줄을 서서 기다리는 것처럼 관리하는 선형 구조.
○ "맨앞" & "맨뒤"에 데이터를 추가하거나 삭제하는 구조.
○ 가장 먼저 입력된 요소를 처리하는 FIFO(First In Frist Out) - 선입선출 구조.
○ 멀티 스레딩에서 스레드를 관리시 사용.
○ 대기열 시스템.
5. Hash Table
○ 해시 함수를 사용하여 변환한 값을 인덱스(index)로 삼아서,
키(key)와 데이터(값,value)를 저장하는 자료구조. [ 키 - 값 ]
○ 데이터의 크기에 관계 없이, 삽입 및 검색에 매우 효율적입니다. !
( 빠른 검색과 데이터 삽입을 위해 설계 )
6. Graph ( 비선형 자료 구조 )
○ 노드들이 서로 연결되어 있는 비선형 구조.
○ 각 노드는 다른 노드와의 관계성을 가지며, 다양한 형태의 그래프가 존재합니다.
7. Tree ( 비선형 자료 구조 )
○ 계층적인 구조를 가지고 있는 비선형 구조 입니다.
○ 부모-자식 관계성을 가지는 노드들로 이루어져 있습니다.
[ Ex, 이진 트리, 이진 탐색 트리, AVL 트리 등 ]
8. Heap
○ 완전 이진 트리의 한 종류로, 최댓값 혹은 최솟값을 빠르게 찾을 수 있도록 구현된 자료구조 입니다.
○ 주로, 우선순위 큐에 사용됩니다.
8. 해시 맵 ( Hash Map)
○ 해시 테이블의 구현 중 하나로, 키와 값을 저장하는데 사용됩니다.
○ 키를 해시 함수를 통해 인덱스로 변환하여 값에 접근합니다.
'면접준비[프론트,백,데이터,CS] > CS 정리' 카테고리의 다른 글
| [ C.S 지식 정리 : 자료 구조 ] 자료구조 & 알고리즘의 정의. (1) | 2024.12.13 |
|---|---|
| [ C.S 지식 정리 : 자료 구조 ] 배열(Array) & 연결-리스트(LinkedList) (0) | 2024.11.16 |
| [ C.S 지식 정리 : 자료 구조 ] 자료구조와 알고리즘, '시간 복잡도' 에 대한 이해 (Big-O 표기법) (3) | 2024.11.02 |
| [ C.S 지식 정리 : 디자인 패턴 ] 디자인 패턴 : MVC 패턴이란? (1) | 2024.11.02 |
| [ C.S 지식 : 디자인패턴 ] 디자인 패턴 [ Design Pattern ]이란? (0) | 2024.11.02 |