[자료구조] 소프트웨어와 자료구조

소프트웨어의 생명주기 (요구 분석 > 시스템 명세 > 설계 > 구현 > 테스트 > 유지 보수)

소프트웨어를 체계적으로 개발하고 관리하기 위해 개발 과정을 단계별로 나누어 구분한 것.

 

자료 추상화(Data Abstraction)

• 처리할 자료, 연산, 자료형에 대한 추상화 표현
• 자료: 프로그램의 처리 대상이 되는 모든 것을 의미
• 연산: 어떤 일을 처리하는 과정. (연산자에 의해 수행)
• 자료형: 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합
  • ex) 자료: 정수의 집합

추상 자료형(ADT, Abstract Data Type)

자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형

	자료	연산
추상화	추상 자료형	알고리즘 정의
구체화	자료형	프로그램 구현

알고리즘

입력(input): 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공되어야 한다.

출력(output): 알고리즘 수행 후 하나 이상의 결과 출력되어야 한다.

명확성(definiteness): 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확해야 한다.

유한성(finiteness): 알고리즘은 수행 뒤에 반드시 종료되어야 한다.

효과성(effectiveness): 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다.

 

알고리즘 표현 방법

1. 자연어를 이용한 서술적 표현 방법

2. 순서도(Flow chart)를 이용한 도식화 표현 방법

3. 프로그래밍 언어를 이용한 구체화 방법

4. 가상코드(Pseudo-code)를 이용한 추상화 방법

  4-1. 가상코드, 즉 알고리즘 기술 언어(ADL)를 사용하여 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘 표현

  4-2. 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능

  4-3. 일반적인 프로그래밍 언어의 형태이므로 원하는 특정 프로그래밍 언어로의 변환 용이

 

가상 코드

기호

  변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블 등을 나타냄

  문자나 숫자의 조합

  첫 문자는 반드시 영문자 사용

자료형

  정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자유형에 사용

연산자

  산술 연산자, 관계 연산자, 논리 연산자

대입문

  대입 연산자의 오른쪽에 있는 값을 대입 연산자의 왼쪽에 있는 변수에 저장

조건문 (if-else, switch-case)

  조건에 따라 실행할 명령문이 결정되는 선택적 제어 구조

반복문 (for, while, do-while)

  일정한 명령을 반복 수행하는 루프 형태의 제어구조

함수문

  처리 작업 별로 모듈화 하여 만든 부프로그램

 

알고리즘 성능 분석

공간 복잡도 ( = 고정 공간 + 가변 공간 )

알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간량

시간 복잡도 ( = *컴파일 시간 + *실행 시간 )

알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간

*컴파일 시간: 프로그램마다 거의 고정적인 시간이 소요

*실행 시간: 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간보다 명령문의 실행 빈도수에 따라 계산

실행 빈도수의 계산

지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 파이가 거의 없으므로 하나의 단위시간으로 갖는 기본 명령문으로 취급

 

시간 복잡도 표기법

빅-오(Big-Oh) 표기법

  1. 실행 빈도수를 구하여 실행시간 함수 찾기

  2. 실행시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택

  3. 계수는 생략하고 O(Big-Oh)의 오른쪽 괄호 안에 표시

    3-1. ex) O(n) = 3n+1 or O(n) = n etc....

 

각 실행 시간 함수에서 n값의 변화에 따른 실행 빈도수 비교

logn	<	nlogn	<	n²	<	n³	<	2^n
1		0		1		1		2
2		2		4		8		4
4		8		16		64		16
8		24		64		512		256
16		64		256		4096		65536
32		160		1024		32768		4294967296

출처: IT COOKBOOK