컴퓨터 과학에서 효율적인 접근 및 수정을 하도록 하는 자료의 조직, 관리, 저장을 의미한다.
더 정확히, 자료 구조는 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
보통 추상 자료형의 선택으로 시작하는 자료구조는 잘 선택하면 효율적인 알고리즘이 가능하다. 효과적으로 설계된 자료구조는 실행 시간, 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행한다.
--- > 즉, 자료구조란 'DATA' 말 그대로 데이터(자료)의 집합을 말하며 해당 자료들이 나열되는 특정 규칙에 따라 여러 종류로 나눠진다. 그리고 자료 구조를 정확히 파악하고 잘 선택한다면 궁극적으로 모든 에너지를 절약할 수 있다 !
자료구조의 목적
자료를 효율적으로 저장하고 잘 관리하고 사용하기 위해
---> 실행시간을 단축시켜 메모리의 절약, 자원의 절약이 가능하다.
자료구조가 중요한 이유
자료구조는각각의 연산 및 목적을 가진 여러 종류로 이루어져있다. 예를 들면 B-트리는 데이터베이스에 효율적이고 라우팅 테이블은 Network (인터넷, 인트라넷)에 일반적이다. 한 프로그램을 설계할 때, 어떠한 자료구조를 사용할지 먼저 고려해야 한다. 큰 시스템 제작의 경우 구현의 난이도나 최종 결과물의 성능이 자료구조에 크게 의존한다는 것을 많은 경험이 뒷바침 하기 때문이다.자료구조가 선택된다면 적용할 알고리즘 또한 명확해진다. 특정 알고리즘이 반드시 필요한 경우, 알고리즘 --> 자료구조 선택으로 순서는 뒤바뀔 수도 있다. 어느 경우든 적절한, 좋은 성능을 위한적절한 자료구조의 선택은 필수적이다.
자료구조의 선택 기준
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 자료의 처리 시간
- 프로그램의 용의성
자료구조의 종류
자료의 특성, 크기, 사용법 그리고 수행하는 연산의 종류와 구현에 필요한 기억 공간 크기에 따라 자료구조의 종류를 선택할 수 있다. 자료구조의 종류는 아래와 같다.
- 자료형에 따라 분류하는 단순 구조
- 단순 구조와 자료 간 관계가 1 : 1 인 선형 구조
- 1 : N 또는 N : N 구조인 비선형 구조
- 파일 구조
구현 기준으로 나눈 자료구조
1) 배열, Array
- 가장 일반적인 구조
- 메모리 상에 같은 타입의 자료가 연속적으로 저장됨
- 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위
2) 튜플, Tuple
- 둘 이상의 자료형을 묶음으로 '세트로' 다루는 구조
3) 연결 리스트, Linked List
- 노드를 단위로 함
- 노드는 다음 노드를 가리키는 참조값으로 구성되어 있음
- 노드가 다음 노드를 가리키지 않으면 리스트의 끝이다.
4) 원형 연결 리스트 ( 뱀의 꼬리물기 st )
- 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트
5) 이중 연결 리스트 ( 손에 손잡고 st - 하지만 처음과 끝 사람은 떨어져 있음 )
- 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성
-> 처음 노드의 이전 노드, 마지막 노드의 다음 노드는 없다.
6) 환형 이중 연결 리스트 ( 손에 손잡고 st - 처음 사람과 끝 사람이 손 잡음 )
- 처음 노드가 이전 노드로 마지막 노드를 가리키고 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트
7) 해시 테이블, Hashing Table
- 개체가 해시값에 따라 인덱싱 된다.
형태 기준으로 나눈 자료구조
형태 기준으로 나눈 자료구조는 선형 구조와 비선형 구조가 있다. 선형 구조는 데이터가 일렬로 배열과 같이 나열되어 있는 것을 뜻하고 비선형 구조는 특정한 형태를 가지고 있는 구조를 의미한다.
1) 선형 구조
1-1. 스택, Stack
- First in Last Out
- 스택 자료구조에 먼저 저장된 것이 쓸 때는 가장 나중에 나옴
== 가장 마지막에 넣은 것은 쓸 때는 가장 먼저 나옴
- 자료들의 나열 순서를 역순으로 바꾸고 싶을 때 스택에 집어 넣었다가 꺼내면 된다.
1-2. 큐, Queue
- First in First Out
- 스택과 반대, 먼저 넣은 것이 제일 먼저 나옴
== 가장 마지막에 넣은 것은 쓸 때 가장 마지막에 나옴
* 환형 큐, Circular queue : 한정된 길이 안에서 부수적 작업없이 읽고 쓰기를 할 수 있는 큐, 빙 돌려가며 이용
-정한 길이의 큐가 가득 차면 -> 더이상 자료를 넣을 수 없다. => 길이를 기억하고 있어야 함.
1-3. 덱, Deque
- 양쪽에서 자료를 넣고 뺄 수 있다.
2) 비선형 구조
2-1. 그래프
- 꼭짓점과 꼭짓점을 잇는 변으로 구성
* 유향 그래프 (방향이 有 있는) vs 무향 그래프 (방향이 無 없는)
- 변이 방향성의 여부에 따라 다름
- 무향 그래프 : 순환이 없는 연결 그래프
- 유향 그래프 : 변이 방향은 부모를 가리키도록 구현
2-2. 트리, Tree
- 뿌리와 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조
- 부모 자식 관계는 변으로 표현
* 이진 트리, Binary Tree
- 자식이 최대 두 개인 트리
* 힙, Heapq
- 이진 트리의 일종으로 이진트리에 어떠한 특성을 부여한 것
자료 구조에 대해 조금 이해가 되었다. 이제 자료구조와 밀접한 관련이 있는 코딩테스트의 알고리즘 종류에 대해서도 하나하나 알아보고 또 정리해보며 차근차근 공부해보기 !
댓글