- 자료구조(資料構造 / 데이터구조, Data Structures)
- 프로그램(혹은 알고리즘)이 컴퓨터상에서 효율적으로 동작할 수 있도록 자료를 저장하는 방법
- 잘 설계된 자료구조와 그에 따른 프로그램(혹은 알고리즘)은 수행시간 혹은 메모리 용량과 같은 자원(resource)을 최소한으로 사용하면서 프로그램이 효율적으로 수행된 수 있도록 해 줌
- 프로그램 설계 시 적절한 자료 구조의 선택은 반드시 필요함
- 프로그램 구현의 난이도나 프로그램의 성능은 자료구조에 크게 의존
- 자료구조가 먼저 선택되면 이를 이용하는 알고리즘의 설계는 상대적으로 명확해짐
자료구조를 적절히 선택해야 처리할 때 효율적으로 (시간적- 빠르게 / 공간적 - 메모리를 적게 cpu time을 적게 기억공간을 적게)
주기억장치 cache에 들어와야 빨리하고 disc에 있는 건 가져와야 해서 오래 걸림
- 내용
- 자료의 표현과 그에 대한 기본적인 연산을 중심으로 배열과 연결 리스트, 스택, 큐, 트리 및 그래프 등의 기본 개념과 표현 방법을 다룸
- 정렬 문제, 탐색 문제 및 그래프 문제를 중심으로 자료구조와 알고리즘의 불가분 관계를 설명하며, 여러 가지 기본 알고리즘을 다루어 응용문제 해결에 직접 적용할 수 있도록 함
참고문헌
Part 1 & Part 7 Handbook of Data Structures and Applications
제 1장 소 개
- 소프트웨어 개발
1.1 소프트웨어 개발 예
[문제] n개의 데이터 중 가장 큰 수를 찾아라.
(문제 개요)
Alice는 연구를 하기 위하여 실험을 하는데 실험 결과 항상 n개의 자료가 무작위로 만들어진다고 한다. Alice는 이 때마다 제일 큰 수를 찾기 위하여 고생을 한다. 그래서 실험 결과로 만들어진 수를 컴퓨터를 이용해 제일 큰 수를 찾을 수 없을까 고민하다가 소프트웨어 개발자(Bob)에게 의뢰하기로 하였다.
- 앞에 있는 수를 제일 큰 수로 가정하고 다 비교
- 30개면 15개씩 나눠서 비교해서 제일 큰 수 두 개를 비교
- 오름차순으로 정렬 제일 뒤에 있음
(소프트웨어 개발 단계)
- 요구사항 분석
- 설계 : 알고리즘 기술언어(플로우차트 등)를 사용하여 기술
- 프로그래밍 : 기술한 알고리즘을 프로그래밍 언어를 사용하여 변형
- 테스트 : 프로그램을 테스트함
- 사용 : Alice는 Bob에게 프로그램을 받아서 사용한다. 프로그램을 컴퓨터에 설치하는 법 , 프로그램을 수행하는 법 등을 배움
- 유지보수 단계 : Alice는 프로그램을 사용하다가, 실험내용이 변경되어 제일 작은 수도 필요하게 되었다. 수정을 의뢰하게 된다. 그 외 실수 데이터 처리가 필요하다든지, 운영체제가 바뀌어 프로그램을 다시 설치한다든지 등의 문제가 발생할 수 있다.
(1) 요구사항 분석 및 전달 단계(Alice/Bob) : Alice가 프로그래머에게 필요한 프로그램 내용을 설명한다.
개발 단계(Bob)
(2) 프로그래머가 프로그램을 설계한다.
(3) 프로그래밍을 한다
(4) 프로그래밍을 테스트 한다.
(5) 사용 단계(Alice) : Alice는 프로그램을 받아 사용한다.
(6) 사용 및 보수 단계(Bob) : 몇 달이 지나 Alice는 프로그래머에게 수정 또는 보완해 줄 것을 요구한다.