[자료구조] 기본개념

1.1 개요 : 시스템 생명 주기

시스템 생명 주기는 크게 다섯가지로 나누어진다.

(1) 요구사항(requirement) : 대부분의 프로젝트들은 그 프로젝트들의 목적을 정의한 명세들의 집합으로부터 시작한다.

(2) 분석(analysis) : 시스템의 요구사항을 기술하고 나면 문제들을 실제 다룰 수 있을 정도의 작은 단위로 나눈다. 분석에는 크게 두가지 접근법이 있는데 bottom-up과 top-down방법이 있다. bottom-up은 세세한 부분들을 합쳐서 포괄적이게 되는 방식이고 top-down은 포괄적인 부분부터해서 점점 세세한 부분으로 내려가는 방식이다.

(3) 설계(design) : 설계 단계는 분석 단계에서 완료된 작업들을 계속한다. 설계자는 시스템이 필요로 하는 객체들과 프로그램에서 실행되는 연산들에서 접근한다. 자료 객체들은 추상 데이터타입을 만드는것만 요구하지만, 프로그래메서 실행되는 연산들은 알고리즘의 명세와 알고리즘의 설계 기법의 고려까지 요구한다.

(4) 개선(refinement)과 코딩(coding) : 이 단계에서는 객체를 표현할 방법을 선택하고 객체들에게 수행되는 연산에 대한 알고리즘을 작성한다.이 단계는 객체의 표현 방법이 그와 연관된 알고리즘의 효율성을 결정하기 때문에 매우 중요하다. 이것은 객체와는 독립된 모든 부분에서 적용될 수 있는 알고리즘을 작성해야 한다는 것을 의미한다.

(5) 검증(verification) : 이 단계는 프로그램의 정확성 증명과 다양한 데이터를 입력하여 프로그램을 테스트하는 것과 오류제거로 구성된다.

1.2 알고리즘

1.2.1 개요

정의 : 알고리즘(algorithm)이란 특정한 일을 수행하는 명령들의 유한 집합이다. 또한 알고리즘은 다음과 같은 조건들을 만족해야 한다.

(1) 입력 : 외부적으로 제공되는 데이터가 0개 이상 있다.

(2) 출력 : 적어도 하나의 결과를 생성한다.

(3) 명확성 : 각 명령 명확하고 모호하지 않아야한다.

(4) 유한성 : 알고리즘의 명령대로 수행하면 모든 경우에 대해 알고리즘은 유한된 step 뒤에 종료되어야 한다.

(5) 유효성 : 모든 명령들은 반드시 수행하기에 충분히 기본적이어야 한다. 원칙적으로 연필과 종이만으로도 수행될 수 있어야한다. 각 연산이 (3) 명확성 에 정의한 대로 명확해서만은 안되고 반드시 실행 가능해야한다.

1.2.2 재귀 알고리즘

 (1) 직접 재귀 : 함수가 그 수행이 완료되기 전에 자기자신을 다시 호출

 (2) 간접 재귀 : 호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출

1.3 데이터 추상화

추상 데이터 타입

정의 : 추상 데이터 타입(ADT)은 객체를 구현 없이 그 객체의 명세와 그 객체의 연산의 명세를 나타낸 것이다.

1.4 성능 분석

기준

(1) 프로그램이 원래 수행할 기능에 부합하는가?

(2) 정확하게 작동하는가?

(3) 프로그램이 어떻게 사용하고 어떻게 작동하는지에 대한 문서화가 포함되어 있는가?

(4) 논리적 단위를 생성하기 위해 프로그램이 함수를 효과적으로 사용하는가?

(5) 프로그램의 코드가 읽기 쉬운가?

(6) 프로그램이 메인 메모리와 보조기억장치를 효율적으로 사용하는가?

(7) 프로그램의 실행 시간은 수행할 기능에 납득할만한가?

1.4.1 공간 복잡도

정의 : 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양

프로그램이 필요로 하는 공간은 다음과 같은 요소의 합이 된다.

(1) 고정 공간 요구 : 프로그램의 입출력 횟수나 크기에 의존적이지 않은 공간 요구를 의미한다.

(2) 가변 공간 요구 : 이는 풀려는 문제의 특정 인스턴스 에 의존하는 크기를 가진 구조화된 변수들을 위해 필요로 하는 공간들로 구성된다. 인스턴스 에 작업하는 프로그램 의 가변 공간 요구는 로 표기한다. 

임의의 프로그램의 총 공간 요구 는 다음과 같이 표현할 수 있는데, 여기서 는 고정 공간 요구를 표현하는 상수이다.

프로그램의 공간 복잡도를 분석할 때는 보통 가변 공간 요구에 대해서만 관심을 둔다.

1.4.2 시간 복잡도

정의 : 프로그램을 실행시켜 완료하는 데 필요한 컴퓨터 시간의 양

프로그램 에 의해 소요되는 시간 는 컴파일 시간과 실행 시간을 합한 것이다. 컴파일 시간은 인스턴스 특성에 의존하지 않기 때문에 고정 공간 요구와 유사하다. 그렇기 때문에 프로그램의 실행 시간 만 염두에 두면 된다.

  를 결정하는 것은 컴파일러의 속성에 대한 상당한 지식이 요구되기 때문에 쉬운 작업이 아니다. 하지만 실행 시간에 대한 자세한 견적을 위해 노력할 필요는 없다. 만약 실행 시간을 꼭 알아내야 한다면, 가장 좋은 방법은 시스템 클럭을 이용해 시간을 재는 것이다. 다른 방법으로는 프로그램이 수행하는 연산의 횟수를 계산하는 것이다. 이것은 컴퓨터에 독립적인 견적이 된다.

1.4.3 점근 표기법

(1) (빅 오) : 알고리즘의 최악의 경우의 성능, 즉 수행 시간의 상한을 나타냄

(2) (빅 오메가) : 알고리즘의 최선의 경우의 성능 ,즉 수행 시간의 하한을 나타냄

(3) (빅 세타) : 알고리즘이 처리해야 하는 수행시간의 상한과 하한을 동시에 나타냄