자료구조 2 - 소프트웨어와 알고리즘, 시간복잡도, 공간복잡도

* 소프트웨어 생명주기 (Software Life Cycle)

 

1. 요구분석 - 2. 시스템 명세 - 3. 설계 - 4. 구현 - 5. 테스트 - 6. 유지보수

6단계로 구성되며, 단계별로 반복 수행하며 소프트웨어의 완성도를 높이게 된다.

 

1. 요구분석

만들 소프트웨어의 성격, 목적을 정확하게 이해하여 어떠한 방식으로 개발할지, 무엇이 필요한지 예산과 자원을 측정한다. - 요구명세서 작성

 

2. 시스템 명세

시스템이 수행해야 할 것, 그리고 입력, 처리내용, 출력이 무엇인지 정의하는 단계  - 시스템 기능 명세서 작성

 

3. 설계 단계

기능들을 수행하기 위한 방법을 논리적으로 결정. 이 단계에서 시스템의 구조와 프로그램, 사용자 인터페이스를 설계한다. 

설계 방식에는 하향식과 상향식이 있다.

하향식 설계 큼직한 문제들부터 해결하며 점차 구체적이고 디테일한 부분을 완성하는 방법.

상향식 설계 하향식과 반대. 디테일한 부분부터 해결하여 위로 올라간다.

 

4. 구현 단계

설계한 논리(알고리즘)을 바탕으로 실제 코딩을 통하여 프로그램 작성

구조화 프로그래밍

지정문, 조건문, 반복문만 사용하여 작성.

순차구조, 선택구조, 반복구조의 제어구조로 표현.

구조가 명확하여 정확성 검증, 테스트, 유지보수가 용이하다.

 

모듈러 프로그래밍

프로그램을 여러 개의 작은 모듈로 나눠, 계층(부모) 관계로 구성한다.

나눈 모듈별로 따로따로 유지보수가 가능하다.

같은 기능을 구현할때 모듈의 재사용을 통해 효율이 높다.

 

5. 테스트 단계

프로그램이 잘 개발 되었는지 테스트하는 단계. 숨어있는 오류를 디버깅하여 완성도를 높여야 한다.

1단계 - 단위 테스트(Unit Test) : 시스템의 최소 구성요소가 되는 모듈에 대하여 개별적으로 테스트.

2단계 - 통합 테스트(Integration Test) : 전체 시스템을 통합적으로 테스트. 상향식 테스트, 하향식 테스트가 있다.

3단계 - 인수 테스트 : 완성된 시스템을 인수하기 위해, 실제 자료를 사용한 최종 테스트

 

6. 유지보수 단계

시스템이 인수되고 설치를 마친 후 일어나는 모든 활동을 말한다. (소프트웨어 생명주기의 가장 긴 부분)

수정형 유지보수 : 사용 중 발생한 에러에 대한 수정 작업.

적응형 유지보수 : 시스템과 관련하여 환경적인 변화 맞추기 위해 재조정 작업.

완전형 유지보수 : 성능 향상을 위한 개선 작업.

예방형 유지보수 : 혹시 모를 변경 사항을 수용하기 위한 대비 작업.

 

* 소프트웨어 품질 평가.

정확성 : 정확한 기능을 수행하는가.

유지 보수성 : 유지보수를 효율적으로 할 수 있는가.

무결성 : 바이러스 및 외부 공격에 대한 보안성이 있는가.

사용성 : 사용자 친화적인가.

 

---

* 알고리즘(Algorithm)

 

어떠한 문제에 대한 해결방법을 추상화하여, 단계적 절차를 논리적으로 기술해놓은것.

 

*알고리즘의 조건

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

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

명확성(Definiteness): 수행할 작업의 내용과 순서를 명확해야한다.

유한성(finiteness) : 문제 해결뒤엔 반드시 종료되어야 한다.

효과성(effectiveness): 모든 명령어들은 실행이 가능해야한다.

 

*알고리즘의 표현 방법

1. 자연어를 이용해 서술적 표현   

ex) 식물 기르는 방법 - 1. 흙에 심는다. 2. 물을 준다. 3. 햇볕을 받게 한다. 4. 식물이 자란다. 5. 2번부터 반복한다.

 

2. 순서도(Flow Chart)를 이용한 도식적 표현

위와같은 기호를 사용하여, 도식적으로 표현, 다만 복잡한 알고리즘의 경우 표현이 어렵다.

3. 프로그래밍 언어를 이용한 구체화된 표현

 

4.가상코드(Pseudo-code)를 이용한 추상화된 표현

조건문, Case문, 반복문(for do, while), 함수문.... 등을 사용하여 표현한다.

 

 

* 알고리즘 성능 분석 방법

* 공간 복잡도

알고리즘 실행부터 완료까지 필요한 총 저장 공간의 양

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

 

 

* 시간 복잡도

알고리즘 실행부터 완료까지 총 소요시간

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

(컴파일 시간은 고정적이고, 실행 시간은 컴퓨터의 사양에 따라 달라지므로, 명령문의 실행 빈도수에 따라 계산)

 

 

* 시간복잡도를 표기하는 빅-오(Big-Oh)표기법

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

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

3. 계수는 생략, O의 오른쪽 괄호에 삽입

 

 

 

 

ex ) 피보나치 수열의 시간 복잡도 

1. 실행시간 함수 : 4n +2

2. n에 대한 항을 선택 : 4n

3. 계수 4는 생략하고 O의 오른쪽 괄호에 삽입.

따라서 피보나치 수열의 시간복잡도는 O(n)

 

* n값에 따른 실행 빈도수 비교