1. 자료 구조 (Data Structure)
ㅇ 문제 해결이 쉽도록, 손쉬운 접근,변경,처리가 가능하게, 데이터를 조직화,저장,표현하는 방법
- 구조화된 데이터에 특정한 연산들을 용이하게 할 수 있는 구조
ㅇ 알고리즘 적용시, 효과적으로 처리 가능하도록 만들어진, 특화된 데이터 체제/형태
- 例) 배열, 링크드 리스트, 스택, 큐, 트리, 그래프 등
ㅇ 자료 및 그 처리를 함께 고려하는 데이터 형식
- 즉, 자료와 그 작동을 함께 고려하면서,
. 이를 컴퓨터에 효과적으로 표현,저장,처리하는 기술
- 특히, 이 둘을 잘 감싸는(캡슐화) 것을, 추상자료형 이라고 함
2. 자료구조의 목적/이유
ㅇ (추상화) 현실 세계에 존재하는 개념,구조의 표현
- 약속된 자료구조를 쓰면 좀더 높은 단계의 프로그래밍이 가능
ㅇ (효율성) 효율적으로 데이터를 사용하기 위함
- 통상, 좋은 자료구조는 연산의 횟수를 작아지게할 수 있지만,
. 모든 목적에 적합한 단일한 자료구조는 없으며, 응용에 따라 달라짐
- 또한, 사칙연산 이외에도,
. 읽기,삽입,삭제,비교,교환,검색 등의 용이성,효율성도 고려 필요
※ 즉, 문제 마다 적절한 자료구조를 사용함으로써,
- 사용 편의성, 메모리 효율성, 코드 성능, 버그 감소 등 측면에서 유리함
3. 자료구조의 종류 ☞ 자료구조 종류 참조
ㅇ 단순 구조 (통상, 자료구조로써 구분 포함시키지 않음)
- 문자형, 문자열형, 숫자형, 논리형 등 ☞ 자료형, C 언어 자료형 등 참조
ㅇ 자료 간의 연결 형태/모양에 따른 구분
- 선형 자료구조 (linear, 전후 1:1 연결 형태)
. 기본 선형 자료구조 : 리스트, 연결 리스트, 배열, 레코드 등
.. 특히, 배열,리스트 이 둘로부터, 대부분의 다른 자료구조들을 구현 가능
. 제한 선형 자료구조 : 스택, 큐, 데크(스택과 큐가 혼합된 형태) 등
.. 자료의 입출력이 정해진 위치에서 만 가능
- 비선형 자료구조 (nonlinear, 전후 多:多 연결 형태)
. 트리, 그래프 등
ㅇ 자료 간에 연속,연결 구조에 따른 구분
- 배열에 기반한 연속 방식 구조 (continuation) : 리스트 등
- 포인터 기반의 연결 방식 구조 (link) : 연결 리스트 등
ㅇ 기타 자료구조 구분
- 입출력 순서를 중심으로 성립되는 자료구조 : 스택, 큐 등
- 자료들 간에 입출력 순서가 중요하지 않은 자료구조 : 집합, 딕셔너리/사전 등
- 키 값의 연산에 의해 직접 접근이 가능한 자료구조 : 해시 테이블
- 파일 구조에 따른 구분 : 순차 파일, 색인 파일, 직접 파일
4. 자료구조의 선택 (고려 사항)
ㅇ 데이터의 양
ㅇ 데이터 사용 횟수 및 방법
ㅇ 요구되는 기억장치의 양
ㅇ 데이터 수정에 필요한 시간
ㅇ 알고리즘 복잡도 등
5. 자료구조의 관점 (저장,처리)
ㅇ 데이터의 저장/접근 관점
- 데이터를 컴퓨터 메모리에 저장/접근할 때,
- 데이터의 순서 및 위치관계 등이 명확하게 정해져야 올바른 처리 가능 함
ㅇ 데이터 및 연산을 다루는 관점
- 자료형(Data Type) : 데이터 중심으로 만 고려
. 자료(변수)가 갖는 값의 종류를 표현
. 이때, 연산은 그 자료형에 맞도록, 별도/부가적/부차적으로 수행되는 관점임
- 추상 자료형(Abstract Data Type) : 데이터와 연산을 함께 고려
. `자료` 및 `연산`을 모두 하나로 묶어 하나의 단위로 표현
. 자료 저장 및 처리 보다는 문제 해결 지향적인 자료형 임
ㅇ 例) 자료구조별 대표적인 연산들
- 스택 : push(), pop(), createStack() 등
- 큐 : inqueue(), dequeue(), createQueue() 등
6. 자료구조의 표현 (구현)
ㅇ 사전 정의형 (프로그래밍 언어에서 기본 내장 제공)
- C 언어 例) 배열, 구조체 등
- 파이썬 例) 리스트,튜플,집합 등
ㅇ 사용자 정의형 (프로그래머가 응용에 따라 직접 구현)
- 다루는 데이터들에 대해,
. 단순히 적절한 자료형을 선택하는 것 이상으로,
- 종합적으로 고려하면서,
. 어떤 연산들이 필요하고,
. 데이터를 효율적으로 저장하는 방법은 어떻고,
. 유효한 연산들은 무엇인지 등
- 자료구조 및 알고리즘 등을 설계 구현해야 함