구버전/CS Study
[Careerthon] 선형자료구조
고래강이
2023. 11. 10. 11:30
개요
- 자료구조란?
- 비선형자료구조
자료구조란?
전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법
효율적인 알고리즘을 사용할 수 있게 해준다.
분류)
선형자료구조란 : 데이터를 순차적으로 나열시킨 형태
비선형자료구조 : 하나의 데이터 뒤(안)에 여러개의 자료가 존재한다.
선형자료구조
- 많은 수의 데이터를 사용할 때 index와 데이터의 1 : 1 구조이기에 자주 활용 된다
- index를 이용하여 데이터에 접근이 빠르다
- 추가 삭제시 번거롭다.
Array
- 가장 기본적인 자료구조 논리적 저장순서와 물리적 저장순서가 일치한다.
- index로 해당 element에 접근한다
- 삽입, 삭제 과정에서 해당요소를 삭제하는 작업 + 빈공간에 대해 index를 shift해줘야하는 작업까지 요구 됨 O(n)의 시간을 요구한다. (index의 크기가 클수록 비례적으로 step이 증가한다.)
Linked List
- Array의 삽입, 삭제과정의 문제를 해결하기 위한 자료구조 (실패)
- 각 element는 자기 자신 다음에 어떤 element가 오는지 기억하기에 삽입, 삭제시에 이 부분만 다른 값으로 바꾸면 됨 O(1)의 시간을 요구한다
- 원하는 위치를 Search하는 과정에서 O(n)의 시간이 추가적으로 발생하기에 사실상 O(n)의 시간을 요구한다. (논리적 저장순서와 물리적 저장순서가 일치하지 않기에 Serach과정에서 O(n)이 된다.)
- 자주 사용되는 자료구조는 아니지만 Tree구조의 근간이 되는 구조
Stack
- Last In First Out (LIFO) 구조이기에 맨마지막 원소가 먼저 나온다 ( ex array.push()이후 array.pop() )
- 차곡차곡 쌓이는 구조
- 함수의 콜스택, 깊이 우선 탐색(DFS)
Queue
- First In Last Out (FILO) 구조이기에 맨 처음 원소가 먼저 나온다
- 밑에서부터 뺄 수 있는 구조
- 프린터 출력, 너비 우선 탐색(BFS)