02. 소프트웨어와 자료구조

[ 학습목표 ]

소프트웨어의 단계적 생명주기를 이해한다.

추상화와 구체화를 이해한다.

알고리즘의 개념과 조건을 이해하고 알고리즘의 표현방법을 알아본다.

알고리즘의 선택 기준과 성능 분석 방법을 알아본다.

소프트웨어는 프로그램의 개발과 운영 및 유지보수에 관련된 모든 정보와 작업을 포함한다.

얼마나 정확하고 효율적으로 개발과 사용 및 관리가 이루어질 수 있는가 하는 것이 중요하다.

소프트웨어 생명주기
Software Life Cycle / Development Cycle

진행상황에 따라 필요한 이전 단계로의 피드백을 반복하면서 소프트웨어의 완성도를 높이는 방식으로 진행한다.

요구분석 → 시스템 명세 → 설계 → 구현 → 테스트 → 유지보수

1) 요구분석 Requirement Analysis

소프트웨어의 기능과 제약조건, 목표 등을 명확하게 정의

이 단계에서 요구명세서를 작성하는데, 요구명세서는 소프트웨어의 개발 완료 여부를 결정짓는 근거가 된다.

2) 시스템 명세 System Specification

입력 데이터, 처리 내용과 그 결과 생성되는 출력이 무엇인지를 정의한다.

개발 과정에서의 의견 차이나 오류로 인해서 재개발작업이나 사용자의 불만이 발생하지 않도록 가능한 정확하게 작성해야 한다.

3) 설계 Design

시스템 구조 설계와 프로그램 설계, 사용자 인터페이스 설계로 구분할 수 있다.

시스템 구조 설계는 시스템을 구성하는 내부 프로그램이나 모듈 간의 관계와 구조를 설계하고,

프로그램 설계는 프로그램 내의 각 모듈에서의 처리 절차나 알고리즘을 설계한다.

사용자 인터페이스 설계는 시스템을 사용하는 사용자에게 보이는 부분에 대한 설계를 한다.

Top-Down Design, Bottom-Up Design, Object-Oriented Design

기존에 개발되어있는 문제해결 도구(알고리즘)을 재사용할 수 있는 경우에는 개발기간과 비용을 단축하고 신뢰성을 확보할 수 있다.

4) 구현 Implementation

설계 단계에서 논리적으로 결정한 문제해결 방법(알고리즘)을 C, C++, Java 등의 특정 프로그래밍 언어를 사용하여 실제 프로그램을 작성한다.

프로젝트에 대한 사용자의 요구, 프로그래머의 능력, 현재 사용중인 언어, 컴파일러의 가용성과 품질, 지원가능한 개발도구, 언어의 호환성, 개발 경험 등을 고려하여 선택해야 한다.

구조화 프로그래밍, 모듈러 프로그래밍

5) 테스트 Test

구현이 완료된 시스템은 설계한 대로 동작하는지 테스트해야한다.

단위 테스트, 통합 테스트, 인수 테스트

6) 유지보수

시스템이 인수되고 설치된 후 일어나는 모든 활동을 포괄적으로 의미한다.

시스템 개발 초기부터 유지보수에 대한 계획을 면밀하게 세워야 한다.

개발된 소프트웨어의 품질은 정확성과 유지보수성, 무결성, 사용성과 같은 기준에 따라 평가한다.

성공한 소프트웨어란 정확하고, 사용환경의 변화에 대한 적응이 쉽고, 보안 기능이 있으며, 널리 사용되는 소프트웨어라고 정의할 수 있다.

수정형: 사용중에 발견한 프로그램의 오류를 수정하는 작업

적응형: 시스템과 관련한 환경적 변화에 적응하도록 재조정하는 작업

완전형: 시스템의 성능을 향상시키기 위해 개선하는 작업

예방형: 앞으로 발생할 지 모르는 변경 사항을 수용할 수 있도록 미리 대비하는 작업

추상 데이터 타입

데이터 Data

프로그램의 처리 대상이 되는 모든 것, Value

연산 Operation 

어떤 일을 처리하는 과정으로 연산자에 의해 수행된다.

데이터 타입 Data Type

처리할 데이터의 집합과 데이터에 대해 수행할 수 있는 연산자의 집합

알고리즘 Algorithm

주어진 문제를 해결하기 위한 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술해놓은 명세서이다.

사람이 사용하는 언어를 이용한 서술적 표현 방법

순서도 Flow Chart 를 이용한 도식화 표현 방법

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

가상코드 Pseudo-code 를 이용한 추상화 표현 방법

가상코드
ADL Algorithm Description Language

기호: 변수, 데이터 타입 이름, 프로그램 이름 등등

데이터타입: 정수, 실수, 문자, 논리, 포인터, 문자열, 추상데이터타입 등등

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

대입문: 변수에 값을 대입

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

반복문: 조건식을 검사하여 명령문을 반복 실행, Loop

함수문: 함후 호출, 실행, 결과반환

성능분석

하나의 문제에 대해 여러 개의 알고리즘이 있을 수 있다.

가장 효율적이고 사용 환경에 최적인 알고리즘을 결정하기 위해서는 알고리즘을 분석하고 평가할 수 있어야 한다. 

알고리즘 분석 기준: 정확성, 명확성, 수행량, 메모리 사용량, 최적성 

일반적으로 알고리즘의 성능분석은 필요한 공간 측면에서 분석하는 공간 복잡도와 실행에 소요되는 시간 측면에서 분석하는 시간 복잡도를 추정하여 일반적인 평가를 한다. 

- 공간 복잡도: 알고리즘을 프로그램으로 실행하여 완료하는 데 필요한 총 저장 공간 (고정공간 + 가변공간)

- 시간 복잡도: 알고리즘을 프로그램으로 실행하여 완료하는 데 걸리는 시간 (프로그램의 컴파일 시간 + 실행 시간)

실행 빈도수를 구하여 실행시간 함수를 찾는다.

실행시간 함수의 값에 가장 큰 영향을 주는 n 에 대한 항을 선택하여 계수는 생략하고 O의 오른쪽 괄호 안에 표시한다.

Big-O 기법:  O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

https://www.hackerrank.com/challenges/30-running-time-and-complexity/tutorial

문제해결을 위한 알고리즘들을 작성하고, 그에 대한 실행시간 함수를 구하여 가장 작은 값의 실행시간 함수를 갖는 알고리즘을 선택한다.