자료 구조와 알고리즘은 컴퓨터 공학에서 가장 중요한 부분 중의 하나이다.
자료구조란?
- Data Structures는 데이터를 구성, 저장, 조작하는 방법을 의미하고, 데이터의 관리 효율성을 조절하기 위한 여러가지 구조에 대한 내용이라고 할 수 있다.
추상 자료형(Abstract Data Type)이란?
- 복잡한 데이터나 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것으로 특성을 나타내는 변수, 필요한 연산등이 포함된다. 이렇게 필요한 데이터의 구조를 따로 정의해서 만들게 되면, 코드에서 데이터를 다루기 편해진다.
스택(Stack)과 큐(Queue) 자료 구조
<Stack>
Stack(스택)은 LIFO(Last-In, First-Out) 구조를 가진 자료구조이다. 먼저 들어간 데이터가 먼저 나온다는 의미이다.
구조적으로 보면 List와 비슷해 보이지만 실제 작동하는 원리에는 차이가 있다.
Stack은 삽입과 삭제가 항상 제일 뒤(최근) 요소에서 이루어진다. 그리고 가장 최근에 삽입한 요소를 top이라고 지칭한다.
- Stack에 대한 기본적인 기능에는 push, pop, top, isFull(배열로 구현된 경우), isEmpty 가 있다.
<push: stack의 가장 뒤에 요소를 삽입>
stack = [] stack.append(1) # push operation
stack.append(3)
<pop: stack의 가장 뒤 요소를 제거 후 return>
stack.pop(-1) # pop operation ## 10
<top: stack의 가장 뒤 요소를 지칭하며 삭제 없이 접근하기 위해서 사용. 파이썬에서는 리스트 인덱스를 통해 접근>
top = stack[-1]
<Queue>
Queue는 FIFO(First-In, First-Out) 구조를 가진 자료구조이다. Stack 과는 반대로 먼저 들어온 요소를 먼저 내보낸다.
Queue의 기능에는 Enqueue 와 Dequeue가 있다.
Enqueue는 queue에 원소를 삽입하고, Dequeue는 queue에서 원소를 삭제한다.
<예시코드>
L = []
# 4개의 원소를 enqueue
L.append(1) # [1]
L.append(2) # [1, 2]
L.append(3) # [1, 2, 3]
L.append(4) # [1, 2, 3, 4]
# 2개의 원소를 dequeue
L.pop(0) # [2, 3, 4]
L.pop(0) # [3, 4]
print(L)
Array vs Linked List?
Array(배열)은 연속된 메모리 공간에 같은 타입의 데이터를 순차적으로 저장하는 자료구조이다.
인덱스를 통해 빠르게 데이터에 접근할 수 있다.
크기가 고정되어 있기 때문에 배열을 생성할 때에 크기를 지정해주어야 한다.
Linked List는 array와 다르게 생성 후에 자유롭게 원소를 추가/삭제할 수 있는 자료구조이다.
가변적인 길이를 가지고 있어서 새로운 데이터 생성에 거의 제한이 없다.
<Hash Table>
Hash Table은 데이터의 key를 hash function을 통해 hash value으로 변환하고, 이 값을 인덱스로 사용하여 데이터를 저장하거나 검색하는 효율적인 자료 구조이다.
Python의 dict가 hash table로 구현되어 있다.
Hash table의 사용 목적은 정해진 메모리에 여러 원소를 효율적으로 저장하여 indexing 성능을 O(1)에 가깝게 만드는 것에 있다.
<Trees and Graphs>
Tree는 데이터 속 항목을 계층적으로 구조화하는 자료구조이다.
#패스트캠퍼스 #패스트캠퍼스AI부트캠프 #업스테이지패스트캠퍼스 #UpstageAILab #국비지원 #패스트캠퍼스업스테이지에이아이랩 #패스트캠퍼스업스테이지부트캠프