1. 자료구조 개요
1.1 소프트웨어와 자료구조
소프트웨어
컴퓨터 하드웨어가 인간의 몸이라면 소프트웨어는 인간의 정신에 해당한다. 자동차는 이동 수단이라는 목적으로만 사용되는 반면, 컴퓨터는 사용되는 소프트웨어에 따라 정보 검색, 소셜 네트워크 서비스, 3차원 그래픽 등 다양한 범용 기기로 변신할 수 있다. 이와 같이 소프트웨어는 컴퓨터 시스템을 문제 해결 도구로 만들어주는 마법 상자 라고 할 수 있다. 컴퓨터 시스템은 그림 1.1 과 같이 소프트웨어와 하드웨어로 구분하고, 소프트웨어는 알고리즘과 데이터로 구성된다.
소프트웨어는 특정 기능을 담당하는 단일 또는 복수의 프로그램을 의미한다. 프로그램은 처리할 대상인 자료(데이터)와 처리 절차인 알고리즘으로 구성되며, 프로그램을 설계하는 작업을 프로그래밍 또는 코딩이라고 부른다.
알고리즘은 주어진 문제 해결에 필요한 절차를 체계적으로 구성해 놓은 것이라고 할 수 있다.
데이터는 일상 생활에서 관찰된 정보를 수치 또는 문자로 기록해 놓은 것이다. 수집된 데이터를 분석하여 새롭게 알아낸 사실을 정라고 하며, 연관된 정보들이 모여서 새로운 지식을 창출할 수 있다.
자료구조
자료구조는 프로그램을 통해 대량의 데이터를 효과적으로 저장하고 처리하기 위한 방법론 또는 자료구조 그 자체를 의미한다. 자료구조는 프로그램의 성능에 밀접하게 영향을 주기 때문에 프로그래머는 주어진 문제를 해결하는데 가장 적합한 자료구조를 선택할 수 있는 안목을 갖추어야 한다. 이를 위해서는 자료구조의 특성에 대한 정확한 지식과 다양한 개발 경험이 필요하다.
잘교구조는 그 형태에 따라 선형 자료구조, 비선형 자료구조로 나눌 수 있으며, 구현 방법에 따라 배열 방식과 연결 리스트 방식으로 구분할 수 있다.
선형 구조에는 배열, 스택, 큐, 리스트가 있으며 비선형 구조에는 트리와 그래프가 있다.
자료구조의 기본적인 특징과 함께 정렬, 탐색, 해싱 등의 관련 알고리즘도 자료구조의 학습 범위에 포함된다.
1.2 소프트웨어 개발 주기
그림 1.2는 소프트웨어 개발 주기의 각 단계를 나열한 것이다.
소프트웨어는 요구사항, 문제 분석, 기능 설계, 구현, 검증의 5단계에 걸쳐 개발되고 단계를 순환하면서 개선된다.
요구사항 단계에서는 개발하려는 소프트웨어의 목표를 정의한다. 이 단계에서는 소프트웨어의 목표 사용 환경, 기능, 입출력, 사용자 인터페이스 등의 정보를 요구사항 명세서에 기록한다.
문제 분석 단계에서는 추상적으로 기술된 소프트웨어의 요구 사항을 해결하기 용이하도록 구체적인 세부 문제들로 분할한다. 대표적인 문제 분석 기법에는 하향식과 상향식 방법이 있다.
하향식은 프로젝트의 최상위 목표에서 하위 단계로 세부 모듈들을 분리해가는 방식으로 전체 모듈의 계층도를 생성한다.
예를들어, 프로그램을 작성할 때 먼저 필요한 서브루틴 함수들을 나열하고, 각 서브루틴을 명령어로 구현하는 방식을 들 수 있다.
반면, 상향식은 기본 모듈들을 조합하여 중간 단위의 서브 시스템을 완성하고 이 서브 시스템을 다시 결합하여 최종적인 목표 시스템을 구축하는 방식이다.
설계 단계는 전 단계에서 생성된 모듈에서 필요한 객체와 연산들을 정의한다. 객체는 속성과 메소드로 이루어진다.
구현은 각 모듈에서 사용하는 객체와 메소드 함수를 실행가능한 코드로 만드는 코딩 과정을 말한다. 메소드는 기본 내장 함수를 이용하거나 직접 알고리즘을 설계하여 개발할 수 있다.
검증은 구현된 프로그램이 프로젝트의 목표 기능들을 정확히 수행하고 오류가 없는지 확인하는 과정이다. 일반적으로 판단하는 블랙 박스 시험과 입력과 출력 정보이외에 프로그램 내부 루틴까지 포함하여 오류를 검사하는 화이트 박스 시험으로 나뉜다.
평과 결과에서 오류가 발생하면 오류의 원인이 해당하는 전 단계로 돌아가서 개선 절차를 수행한다.
개발중인 소프트웨어가 목표 수준에 도달할 때까지 이 단계들을 반복하면서 순환한다.
1.3 알고리즘의 정의
알고리즘은 주어진 문제 해결에 필요한 유한한 명령어들의 집합으로 정의하며, 다음 조건을 만족해야 한다.
- 입력 : 0개 이상의 입력이 있어야 한다.
- 출력 : 1개 이상의 출력이 있어야 한다.
- 명확성 : 모호하지 않은 명령어로 표현되어야 한다.
- 유한성 : 유한한 수의 명령어로 이루어져야 한다.
- 유효성 : 중복되고 불필요한 명령문 없이 효율적으로 작성되어야 한다.
첫째, 알고리즘에서 사용자(또는 파일)를 통한 명시적인 외부 입력이 반드시 필요한 것은 아니다.
둘째, 알고리즘은 수행이 완료된 후 하나 이상의 출력 결과를 제시해야 한다.
셋째, 알고리즘을 구성하는 명령문들은 모호하지 않도록 정량적인 기준과 함께 표현되어야 한다.
넷째, 알고리즘은 일반 프로그램과 달리 유한한 개수의 명령어 실행 이후에 종료되어야 한다.
끝으로, 유효성이란 중복되거나 실행에 불필요한 명령어가 알고리즘에 포함되지 않고 효율적으로 기술되어야 한다는 의미이다.
알고리즘은 개발자 간의 소통 수단이므로 효과적인 문서화는 매우 중요하다. 비교적 단순한 알고리즘은 플로우 차트로 표현할 수 있으며, 일반적으로는 알고리즘을 빠르게 기술하기 위해 의사 코드를 사용한다.
몇 가지 간단한 알고리즘 예제들을 살펴보도록 하자.
1.4 추상 자료형
프로그래밍 언어에서 학생이나 교과목과 같은 실 세계 객체를 기본 자료형으로 지원한다면 인간이 사고하는 방식대로 프로그래밍하기 쉬울 것이다.(예, 학생이 교과목을 수행한다.) 이러한 자료형을 추상 자료형이라고 부르며 이에 기반한 작업을 객체 지향 프로그래밍이라고 한다. 파이썬, C++, 자바 언어는 기본적으로 추상 자료형인 클래스를 지원하지만 C언어는 지원하지 않는다.
