[Data Structure] 자료구조란?

Mintaek·2023년 11월 20일

algorithm 자료구조

Algorithm study

목록 보기

2/3

자료구조란 무엇일까?

여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것 또는 자료를 효율적으로 관리하는 기법

여러 '데이터'.. 그렇다면, 데이터는 무엇일까?

실생활을 구성하고 있는 모든 값
데이터는 목적에 따라 형태를 구분하고, 분류해서 사용해야한다.
데이터는 그 자체만으로 어떤 정보를 가지기 힘들다
- 예를 들어, 나이라는 데이터만 가지고 있다면, 그것이 사람의 나이인지, 나무의 나이인지 알 수 없다.

= 그러므로, 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

자료구조로 뭘 할 수 있고 왜 배우는가?

자료구조로 할 수 있는 것

대규모 데이터를 쉽게 관리하고 활용하는 데에 어려움이 줄어든다.
DB에서 원하는 데이터를 찾기도 쉬워진다.
필요한 맞춤 알고리즘을 설계할 수 있다.
사용자들의 여러 요청을 한번에 처리할 수 있으며, 그 처리 과정을 단순화하여 처리 속도를 향상시킬 수 있다.

왜 배우는가?

자 위의 설명들로 자료구조가 중요한 것은 알겠다. 근데 진짜 왜 배워야할까?

자료구조는 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서 배운다.
자료구조는 특정 상황에 놓인 문제를 해결 하는 데에 특화되어있다.

그렇기 때문에, 특정 문제 상황에 가장 적합한 자료구조를 빠르게 찾아서 데이터를 정리하고 활용해서 문제를 해결할 수 있다.

다시말해서, 문제를 해결하기 위해 배운다 (내 생각에 개발자는 문제를 정의하고 그 문제를 해결하는 사람이다)

그렇다면 이제 기본적인 7가지의 자료구조를 알아보고 장점과 단점 그리고 어디에 사용하는 지 알아보자.

기본적인 7가지의 자료구조

1. 배열 (Array)

동일한 데이터 타입의 요소를 순차적으로 저장하는 선형 자료구조, 가장 기본적인 자료구조

❗️ 주의 : 밑에 코드처럼 JavaScript 같은 동적 타입 언어에서는 배열에 여러 타입의 요소를 포함할 수 있습니다. 혼합된 타입의 배열은 코드를 이해하기 어렵게 만들고 예측할 수 없는 동작을 초래할 수 있으므로 주의가 필요하다.

let arr = [1, "2", 3, "4"]

이미지 출처 : 자료구조-배열

배열은 생성시 설정된 셀의 수가 고정되고, 각 셀에는 인덱스 번호가 부여된다.

장점

인덱스를 통한 빠른 직접 접근이 가능하다.
구현이 쉽다.
정렬에 용이하다.
원하는 데이터를 효율저긍로 탐색/가져올 수 있다.

단점

삽입, 삭제 등에 대한 연산에 필요한 비용이 높다
- 데이터가 삭제되고 나면 남는 셀을 빈 공간이 되므로 메모리 낭비가 심하다.
데이터를 저장할 수 있는 메모리 크기가 고정되어 있다. (크기를 변경하기 어려움)

사용 예시

빠른 검색 또는 순차적인 데이터에 접근이 필요한 경우
ex. 전화번호부

2. 연결 리스트 (Linked List)

연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.

이미지 출처 : 개발자라면 알아야할 7가지 자료구조

배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
연결 리스트에는 단일 연결 리스트(Singly-Linked List), 이중 연결 리스트(Doubly-Linked List)등의 종류가 있다

장점

새로운 데이터를 추가하고 삭제하는 것이 용이하고 효율적
구조의 재구성이 필요 없음.
대용량 데이터의 처리에 적합하다
동적인 메모리 크기를 가지고 있다.

단점

배열보다 메모리를 더 사용한다.
처음부터 끝까지 순회하기 떄문에 원하는 값을 비효율적으로 검색하고 가져온다.

사용 예시

메모리 크기가 정해져 있지 않거나, 데이터를 연속적으로 빠르게 삽입/제거가 필요한 경우.
ex. 이미지 뷰어, 갤러리, 음악 플레이어

3. 스택 (Stack)

순서가 보존되는 선형 데이터 구조. 후입선출 (LIFO) 구조로 간단하고 효율적인 구현이 가능하다.

이미지 출처 : Stack 구현

장점

데이터가 받는 순서대로 정렬된다
빠른 런타임

단점

가져오기 시에 가장 최신 요소만 가져온다
한번에 하나의 데이터만 처리 가능하다

사용 예시

가장 마지막으로 입력된 것을 바로 처리하고 싶을 때
ex. 브라우저 뒤로가기, 실행 취소, 재귀 알고리즘
ex2. 괄호 유효성 검사

4. 큐 (Queue)

선입선출 (FIFO) 구조로 간단하고 효율적인 구현이 가능하다

장점

동적인 메모리 크기
데이터를 받는 순서대로 정렬된다
빠른 런타임

단점

가장 오래된 요소만 가져온다
한번에 하나의 데이터만 처리 간으하다

사용 예시

반복적이고 자주 받는 데이터를 비동기적으로 처리하는 경우 효율적
순서에 민감한 데이터를 처리하는 경우
대기열 관리, BFS(너비 우선 탐색), 캐시 구현

5. 트리 (Tree)

비선형 자료구조로, 계층적 구조를 표현하는 자료구조

Node (노드) : 트리를 구성하고 있는 원소 그 자체를 말한다.
Edge (간선) : 노드와 노드사이를 연결하고 있는 선을 말한다.
Root(Node) : 트리에서 최상위 노드를 말한다.
Terminal(Node) : 트리에서 최하위 노드를 말한다. Leaf Node라고도 한다.
Internal(Node) : 트리에서 최하위 노드를 제외한 모든 노드를 말한다.

이미지 출처 : 나무위키

장점

계층적 데이터를 표현하기에 적합하다
검색 및 정렬 작업에 효율적

단점

비교적 높은 메모리 사용

사용 예시

이진 탐색 트리(BST), 문서 구조, 파일 시스템 등

❗️ 참고

트리의 구조는 다양하므로, 여기 그리고 여기를 참고하기 바랍니다.

6. 해시 테이블 (Hash Table)

대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 복잡한 데이터 구조

해시 테이블은 키/값 쌍을 저장하기 위한 자료구조로, 테이블 내의 작은 서브그룹인 버킷에 데이터를 저장한다. 이를 위해 키는 해시 함수를 통해 숫자값인 해시로 변환되어 저장되며, 이 해시는 버킷의 인덱스를 나타낸다. 테이블은 필요 시 메모리 크기를 동적으로 조절하며, 효율적인 검색을 위해 키를 해시값으로 변환하여 해당 버킷에서 값을 찾아 반환한다.

이미지 출처 : Hash table

장점

빠른 검색, 삽입, 삭제
키-값 쌍을 효율적으로 저장한다

단점

충돌이 일어날 수 있다 (입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있다)
충돌이 자주 일어날 수 있으며 해시함수의 정비가 필요한 경우가 많다.
메모리 사용이 높을 수 있다.

사용 예시

사용자 로그인 인증
DB : 주소, 이름, 번호 등 찾기

7. 그래프 ( Graph )

그래프는 노드들 간의 연결을 나타내는 자료구조로, 방향성에 따라 Directed(방향 그래프) 또는 Undirected(무방향 그래프)로 나뉜다. Directed 그래프는 일방향으로 향하는 edge로 구성되어 있어 일방통행과 유사하며, Undirected 그래프는 양방향 도로와 같이 방향이 지정되지 않은 구조를 갖는다. 그러나 그래프로 구성된 데이터는 다양한 형태와 관계를 가질 수 있다.