이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.
https://github.com/AeroCodeX/자료구조란? (What is Data Strcture?) |
큐, 스택, 링크드 리스트 같은 추상적 자료형에서의 효율적인 동작(알고리즘_)을 위해,
메모리 내에서 다수의 정보를 어떻게 저장할지에 대한 방법.
자료구조의 연산 (Operation) |
- 접근 (access / Indexing)
데이터의 값을 얻어오는 연산.
자료구조마다 앞부분, 중간부분, 뒷부분의 접근 성능이 다를 수 있다.
인덱스 번호를 통해 데이터의 값을 얻어오는 연산은 Indexing 이라고 한다.
- 검색 (search)
주어진 조건(최대, 최소, 등가 eg.)을 만족하는 데이터의 값을 얻어오는 연산.
검색에 최적화된 자료구조를 검색 자료구조(Search Data Structure)라고 한다.
- 삽입 (insert)
자료구조에 데이터를 저장하는 연산.
자료구조마다 앞부분, 중간부분, 뒷부분의 삽입 성능이 다를 수 있다.
- 제거 (remove)
자료구조에서 데이터를 제거하는 연산.
자료구조마다 앞부분, 중간부분, 뒷부분의 제거 성능이 다를 수 있다.
- 밸런싱 (balance, optional )
특수한 목적을 효율적으로 달성하기 위해, 자료들의 순서나 내부 정보를 고치는 연산.
자료구조와 성능 (Operation Complexity) |
데이터의 삽입/삭제가 빈번하게 이루어지는 프로그램에서,
삭제성능이 나쁜 자료구조를 사용하면 병목의 원인이 될 수 있다.
문제의 특성을 적절히 고려한 자료구조의 선택은,
프로그램의 성능을 극적으로 향상시킨다.
자료구조의 종류 (Type) |
- 배열 (Array)
- 벡터 (Vector)
- 데크 (Deque)
- 일부 추상적 자료형을 구현화한 것
- ...
자료구조의 분류 (Specialization) |
- 외부 메모리 자료구조 (External Memory Data Structure)
외부적 디스크에 존재하는 자료구조. (마그네틱 테이프 eg.)
일반적으로 액세스 속도가 매우 느리지만, 캐싱으로 극복할 수 있다.
- 수동적 자료구조 (Passive Data Structure)
자료구조의 외부 쓰레드(또는 외부 프로세스_)에서만 수정가능한 자료구조.
능동적 자료구조와 반대되는 개념이다.
- 능동적 자료구조 (Active Data Structure)
자료구조의 내부 쓰레드에 의해서만 수정가능한 자료구조.
외부에서 요청을 받으면 내부 쓰레드가 해당 요청을 처리한다.
- 영속적 자료구조 (Persistent Data Structure)
오래된 버전의 자신도 함께 저장하고 있는 자료구조.
최신 버전에서 이전 버전의 데이터가 필요한 경우에 사용된다.
- 부분 영속적 자료구조 (Partially Persistent Data Structure)
최신 버전의 자료구조만 수정가능한 영속적 자료구조.
- 전체 영속적 자료구조 (Fully Persistent Data Structure)
이전 버전의 자료구조도 수정가능한 영속적 자료구조.
- 병합가능한 영속적 자료구조 (Confluently Persistent Data Structure)
최신 버전과 이전 버전의 결합/병합이 가능한 영속적 자료구조.
- 재귀적 자료구조 (Recursive Data Structure)
A가 모여 또다른 A를 만들 수 있는 자료구조.
예를 들면 트리나 리스트. (트리 안에 서브트리, 리스트 안에 서브리스트)
추상적 자료형이란? (What is ADT ㅡ Abstract Data Type?) |
일부 ADT는 객체화하면 자료구조로도 본다는 것에 주의.
트리는 ADT이지만, (배열로도 구현할 수 있고, 링크드 리스트로도 구현할 수 있으므로, _)
객체화되면 자료구조로도 생각할 수 있다.
추상적 자료형의 종류 (Type) |
- 딕셔너리 (Dictionary)
- 스택 (Stack)
- 트리 (Tree)
- 큐 (Queue)
- 셋 (Set)
- 백 (Bag)
- ...
추상적 자료형과 성능 (Algolithm) |
ADT는 어떻게 자료를 삽입/삭제할것인지에 대한 내부적인 알고리즘을 갖고있는 경우가 많다.
적절히 고려한 ADT는 프로그램의 생산성을 높일 수 있다.
참고문헌 |
