[Data Structure] 자료 구조 개념 및 종류

📌 목차 

  -  자료구조란 무엇일까?

  -  자료구조의 특징 및 사용

  -  자료구조의 종류

 

 

📌 자료구조란 무엇일까? 

Data Structure (자료 구조) 란,

데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며

자료 (Data)에 대한 처리를 효율적으로 수행 할 수 있도록 자료를 구분하여 표현한 것이다.

 

즉, 자료 구조는 메모리와 데이터를 정리하는 것을 의미하는데

쉽게 말해 책장(메모리)에서 책(데이터)을 정리하는 방식 (제목 정렬, 분야 정렬 등)이라고 볼 수 있다.

 

예를 들어, 책을 아무 규칙 없이 꽂아두게 되면 원하는 책을 찾는데 시간이 소요된다.

그것을 제목 정렬, 분야 정렬 등으로 정리하게 되면 원하는 책을 찾고 정리하는 것이 좀 더 효율적으로 되는 것과 같다.

 

 

📌 자료구조의 특징 및 사용 

자료 (Data)를 더 효율적으로 저장하고, 관리하기 위해 사용하며

실행 시간을 단축하거나 메모리 용량을 절약 할 수 있다.

 

Algorithm (알고리즘)은 어떠한 문제에 대해서 문제 해결 방법을 정의한 '일련의 단계적 절차' 이자 해결하기 위한 동작, 방법으로

문제 해결에 필요한 계산 절차 또는 처리 과정의 순서를 의미한다.

 

알고리즘은 자료구조와 밀접한 관계를 가질 수 밖에 없는데,

그 이유는 적절한 자료 구조의 선택을 통해 효율적인 알고리즘이 될 수 있기 때문이다.

 

프로그램은 특정 문제를 해결하기 위한 처리 방법과 과정의 순서로 짜여진 명령어 (코드, 소스)의 모음이다.

이 프로그램이 실행되기 위해서는 메모리에 올릴 데이터가 필요하며 이 데이터들을 담아내는 방식이 자료 구조이다.

 

넓은 의미에서 [ 자료구조 + 알고리즘 + α = 프로그램 ] 으로 볼 수 있다.

 

 

📌 자료구조의 종류 

자료 구조의 종류는 크게 아래와 같이 존재한다.

자료 구조별로 시간복잡도 차이가 나며, 상황에 따라 선택해야 효율적으로 사용할 수 있다.

 

❓ 시간복잡도 : 알고리즘이 문제를 해결하기 위한 시간(연산의 횟수)를 의미한다.

 

< 자료구조의 종류 >

< 자료 구조별 시간 복잡도 ( Big O 표기법 ) >

자료 구조별, 시간복잡도 참고 : @bangu4 - [알고리즘] 알고리즘별, 자료구조별, 시간복잡도 - 총정리

[알고리즘] 알고리즘별, 자료구조별, 시간복잡도 - 총정리

 

⚡ 자료구조의 분류

자료구조는 크게 선형 자료구조와 비선형 자료구조로 구분된다.

선형 자료 구조는 데이터가 일렬로 나열되어 있는 것을 뜻하고,

비 선형 자료 구조는 특정한 형태를 띄고 있는 것을 뜻한다.

 

선형 자료 구조 : Array ( 배열 ) / Linked List ( 연결 리스트 ) / Stack ( 스택 ) / Queue ( 큐 )

비 선형 자료 구조 : Tree ( 트리 ) / Graph ( 그래프 )

 

⚡ Array ( 배열 )

  ▪ 특징

  -  동일한 탑입의 데이터들을 저장하며, 고정된 크기를 가지고 있다. ( 정적 자료구조라고 불린다. )

  -  인덱스 번호로 데이터에 접근할 수 있다.

 

  ▪ 용도

  -  특정 요소를 빠르게 읽을 때, 다차원 데이터를 다룰 때 사용된다.

  -  삽입 정렬, 퀵 정렬, 버블 정렬, 병합 정렬 등 다양한 정렬 알고리즘에 사용된다.

 

⚡ Linked List ( 연결 리스트 )

  ▪ 특징

  -  각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

  -  첫 번째 노드의 포인터를 통해 두 번째 데이터를 찾을 수 있다.

  -  배열의 크기를 미리 선언해야하는 배열 리스트와 달리 연결 리스트는 데이터의 개수만큼 메모리를 사용하므로
     동적인 데이터 추가/삭제에 유리하다. ( 동적 자료구조라고 불린다. )

 

  ▪ 용도

  -  Alt + Tab 을 통해 프로그램 간 전환, 갤러리 사진 넘기기 등에 사용된다.

 

⚡ Stack ( 스택 )

▪ 특징

  -  순서가 보존되는 선형 데이터 구조로,

     입력된 순서 반대로 처리되는 LIFO ( Last In First Out ) 형태이다.

 

  ▪ 용도

  -  브라우저의 뒤로가기, 실행 취소, 재귀 프로그램의 함수 호출 등에 사용된다.

 

⚡ Queue ( 큐 )

▪ 특징

  -  스택과 반대로 양 방향으로 입력과 출력이 진행되는 구조이다.
     입력된 순서로 처리되는 FIFO ( First In First Out ) 형태이다.

  -  입력되는 데이터를 Enqueue, 출력되는 데이터를 Dequeue 라고 한다.

 

  ▪ 용도

  -  프로세스 관리, 멀티스레딩에서 스레드를 관리, 대기열 시스템, 캐시, 너비 우선 탐색 등에 사용된다.

 

⚡ Hash Table ( 해시 테이블 )

▪ 특징

  -  Hash Function ( 해시 함수 )를 사용하여 변환한 값을 인덱스로 삼아 키와 데이터를 저장하는 자료 구조이다.
     예를 들어, 전화번호부의 이름(Key)를 통해 전화번호(Value)를 찾을 수 있는 것과 같다.

  -  데이터 크기에 관계없이 삽입 및 검색에 효율적이다.

 

  ▪ 용도

  -  데이터베이스 인덱스 구현, 사용자 로그인 인증 등에 사용된다.

 

⚡ Graph ( 그래프 )

▪ 특징

  -  그래프는 데이터 간의 관계를 표현하기 위한 자료 구조이며
     정점( Vertex = Node : 데이터가 저장 )과 간선( Edge : 링크라고도 하며 노드 사이 관계를 나타냄 )으로 이루어져 있다.

  -  정점마다 간선이 없을 수도 있고, 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다.

 

  ▪ 용도

  -  GPS에서 위치와 경로를 나타냄, 검색 엔진에 의해 웹 페이지 및 링크를 나타냄

 

[자료구조 1] 그래프(Graph) 이해하기

 

⚡ Tree ( 트리 )

▪ 특징

  -  그래프가 계층적 구조로 만들어진 비선형 자료 구조이다.

  -  최상위 노드인 루트가 있고, 상위 노드를 부모( Parent ) 노드, 하위 노드를 자식( Child ) 노드라고 한다.

 

  ▪ 용도

  -  Binary Trees( 이진 트리 ), Binary Search Tree( 이진 검색 트리 ), Heap( 힙 )

  -  컴퓨터의 디렉터리 구조, 조직도 등에 사용된다.

 

⚡ Heap ( 힙 )

▪ 특징

  -  Heap( 힙, 더미 )은 완전 이진 트리의 형태로 만들어진 자료 구조이다.

  -  최대 힙( Max Heap ) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

  -  최소 힙( Min Heap ) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

  ▪ 용도

  -  최댓값 혹은 최솟값을 빠르게 찾아내기 위해 사용한다. ( 우선순위 큐, 힙 정렬 )

 

 

 

 

📌 Reference

@on1ystar - 자료 구조(Data Structure) 개념 및 종류 정리

https://bnzn2426.tistory.com/

@jin-network - [자료구조] 자료구조 종류

https://jin-network.tistory.com/