콘텐츠로 이동

소프트웨어 개발과 자료구조

1. 소프트웨어 생명주기

1) 스프트웨어 생명주기

성공적인 소프트웨어 개발이란?

얼마나 정확하고 효율적으로 소프트웨어를 개발하고 사용 및 관리가 이루어지는가?

  • 개발할 소프트웨어에 대한 정확한 이해
  • 사용할 자료와 자료 간의 연산 관계를 분석하여 최적의 자료구조 정의

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

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

  • 일반적으로 6단계로 구분 요구 분석
  • 시스템 명세 설계
flowchart LR
    A[요구분석] --> B[시스템 명세]    
    B --> C[설계]
    C --> D[구현]
    D --> E[테스트]
    E --> F[유지보수]
    F -.-> B
    F -.-> C
    E -.-> C
    E -.-> D
    D -.-> C
    C -.-> B
    ――――> 프로세스   
    ----> 피드백   
    필요한 단계로 피드백을 반복수행하면서 소프트웨어 완성도를 높임
요구분석 단계

문제분석단계

  • 개발할 소프트웨어의 기능과 제약조건, 목표 등을 소프트웨어 사용자와 함께 명확히 정의하는 단계
  • 개발할 소프트웨어의 성격을 정확히 이해하고 개발 방법과 필요한 개발 자원 및 예산 측정
  • 요구 명세서 작성
시스템 명세 단계

시스템이 무엇을 수행해야 하는가를 정의하는 단계

  • 시스템 기능 명세서 작성
  • 입력 자료, 처리 내용, 생성되는 출력이 무엇인지를 정의
  • 개발과정에서 의견차이나 오류로 인해 재개발 작업이나 사용자 불만이 발생하지 않도록 가능한 정확하게 작성해야 함
설계단계

시스템 명세 단계에서 정의한 기능을 실제로 수행하기 위한 방법을 논리적으로 결정하는 단계

  • 시스템 구조 설계: 시스템을 구성하는 내부 프로그램이나 모듈 간의 관계와 구조 설계
  • 프로그램 설계: 프로그램 내의 각 모듈에서의 처리 절차나 알고리즘을 설계
  • 사용자 인터페이스 설계: 시스템을 사용하는 사용자에게 보여지는 프로그램을 설계
설계 단계 방법

하향식 설계 방법(Top-Down design)

  • 무엇을 수행할 것인지를 정의하는 상위단계에서 각 단계를 내려갈 수록 수행 방법을 구체적으로 정의하고 세분화하는 방법
  • 마지막 단계의 작은 단위 문제들을 각각 처리함으로 전체 문제를 해결
  • 분할 정복(Divide & Conquer) 방식의 설계 방법

상향식 설계 방법(Bottom-Up design)

  • 최하위 단계에 있는 작은 단위의 문제를 먼저 해결하고 이를 이용하여 상위 단계의 큰 단위의 문제를 해결하는 방법
  • 최하위 단위의 문제들에 대해 기존에 개발되어 있는 문제해결 도구(알고리즘)을 재사용하는 경우 개발 기간과 비용 단축 가능

객체지향 설계 방법(Object-Oriented design)

  • 상향식 설계 방법과 유사
  • 작은 단위의 문제 해결을 위한 자료와 처리 방법을 하나로 묶어서 객체를 만들고, 객체들을 연결하여 재사용
구현단계

설계 단계에서 논리적으로 결정한 문제 해결 방법(알고리즘)을 프로그래밍언어를 사용하여 실제 프로그램을 작성하는 단계

구조화 프로그래밍
  • 지정문과 조건문, 반복문 만을 사용하여 프로그램을 작성
  • 순차구조, 선택구조, 반복구조의 세가지 제어구조로 표현
  • 구조가 명확하여 정확성 검증과 테스트 및 유지보수 용이
모듈러 프로그래밍
  • 프로그램을 여러개의 작은 모듈로 나누어 계층관계를 갖도록 구성하는 프로그래밍 기법
  • 각 모듈은 구조화 프로그래밍 기법으로 개발
  • 모듈별로 개발과 테스트 및 유지보수, 모듈의 재사용가능
테스트 단계

개발한 시스템이 요구사항을 만족하는지, 실행 결과가 예상한 결과와 정확하게 맞는지를 검사하고 평가하는 일련의 과정
오류를 최대한 찾아내어 시스템의 완성도를 높이는 단계

1단계

단위 테스트(Unit Test)
- 시스템의 최소 구성요소가 되는 모듈에 대해서 개별적으로 시행

2단계

통합 테스트(Integration Test)
- 단위 테스트를 통과한 모듈을 연결하여 전체 시스템으로 완성하여 통합적으로 시행하는 테스트 - 구성요소 연결을 점진적으로 확장하면서 테스트 시행(하향/상향식 테스트)

3단계

인수 테스트
- 완성된 시스템을 인수하기 위해서 실제 자료를 사용한 최종 테스트(알파 테스트, 베타 테스트)

유지보수 단계

시스템이 인수되고 설치된 후 일어나는 모든 활동
- 오류및디자인수정,새로운요구사항에대한기능추가등 소프트웨어 생명주기에서 가장 긴 기간 소요

유지보수 유형
  • 수정형: 사용중에 발견한 프로그램의 오류 수정작업
  • 적응형: 시스템과 관련한 환경적 변화에 적응하기 위한 재조정 작업
  • 완전형: 시스템의 성능을 향상시키기 위한 개선 작업
  • 예방형: 앞으로 발생할지 모를 변경 사항을 수용하기 위한 대비 작업

2) 개발된 소프트웨어 품질 평가

  • 정확성: 요구되는 기능들을 정확하게 수행하는 정도를 평가
  • 유지 보수성: 사용하는 동안 발생하는 변경사항들에 대해 쉽게 수용할 수 있는지를 평가
  • 무결성: 바이러스 등의 외부 공격에 대해 문제가 발생하지 않는 보안성을평가
  • 사용성: 사용자가 쉽게 사용법을 배우고 편하게 사용할 수 있는 정도를 평가

2.추상 자료와 알고리즘

1) 추상 자료형

뇌의 추상화 기능

  • 기억할 대상의 구별되는 특징만을 단순화하여 기억하는 기능

컴퓨터를 이용한 문제 해결에서의 추상화

자료 추상화(Data Abstraction)

  • 크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법
  • 처리할 자료, 연산, 자료형에 대한 추상화 표현

자료(Data)

  • 프로그램의처리대상이되는모든것을의미

연산(Operation)

  • 어떤 일을 처리하는 과정으로 연산자에 의해 수행
  • 예)더하기연산: ‘+’연산자에의해수행

자료형(Data type)

  • 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합
  • 예)정수형자료에대한정수의집합:{...,-1,0,1,...}, 연산자 집합. {+, -, x, ÷, mod}

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

자료형의 종류

  • 시스템 정의 자료형
  • 사용자 정의 자료형
    • 사용자가 필요에 따라 시스템 정의 자료형이나 기존에 정의해 놓은 다른 사용자 정의 자료형을 이용하여 정의

추상화

  • 자료형을 정의하기 위해서는 구체적인 구현에 앞서 자료형에 대한 자료와 연산자의 특성과 연산자는 무엇을 수행하는지를 구체적으로 정의(추상 자료형)해야 함

추상화의 장점

  • 구체적인 구현을 포함하지 않기에 알고리즘을 개발하기가 단순해지며, 실제 프로그래밍 언어를 사용하여 프로그램으로 구체화하기 쉬움

추상화와 구체화

  • 추상화 : “무엇(What)인가?”를 논리적으로 정의
  • 구체화 : “어떻게(How)할 것인가”를 실제적으로 표현
추상화 → 구체화

    ↗ 코걸이
고리 → 귀걸이
    ↘︎ 배꼽걸이 

         ↗ C 프로그램
추상 자료형 → C++ 프로그램
         ↘︎ JAVA 프로그램

자료의 연산에 있어서의 추상화와 구체화의 관계

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

2) 알고리즘의 이해

알고리즘(Algorithm) 이란

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

[요리 재료] >> 자료

스펀지케이크(20×20cm) 1개, 
크림치즈 200g, 달걀 푼 물 2개 분량, 
설탕 3큰술, 레몬즙·바닐라에센스 1큰술씩, 
딸기시럽(딸기 500g, 설탕 11⁄2 컵, 
레몬즙 1작은 술), 
딸기 1개, 플레인 요구르트 2큰술

[요리법] >> 알고리즘   

    1 케이크 틀의 가장자리에 필름을 돌린 다음 스펀지케이크를 놓는다. 
 절  2 2볼에크림치즈를넣고거품기로젓다가달걀푼물과설탕3큰술을세번에 나누어 넣으면서 크림 상태로 만든다.
 차  3 2에 레몬즙과 바닐라에센스를 넣고 살짝 저은 다음 1에 붓는다. 이것을 180°C의 오븐에 넣고 20분 정도 굽는다.
 ↓  4 냄비에 슬라이스한 딸기와 설탕 11⁄2 컵을 넣고 끓이다가 약한 불에서 눌어붙지 않도록 저으면서 거품을 걷어낸다. 되직해지면 레몬즙을 넣고 차게 식힌다.
    5 접시에 치즈케이크를 한 조각 담고 4의 시럽을 뿌린 다음 플레인 요구르트와 딸기 를 얹어낸다
                ⌙→ 연산

알고리즘의 이해

알고리즘의 조건

입력(input)
  • 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수있어야 함
출력(ouput)
  • 알고리즘수행후하나이상의결과를출력해야함
명확성(definiteness)
  • 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세 되어야 함
유한성(finiteness)
  • 알고리즘은 수행 뒤에 반드시 종료되어야 함
효과성(effectiveness)
  • 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 함

3) 알고리즘의 표현

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

  • 사람이 사용하는 자연어(언어)를 이용하여 표현
  • 자연어는 서술적이고 사용하는 사람에 따라 일관성과 명확성을 유지하기가 어려워 누구나 이해하고 사용해야 하는 알고리즘을 표현하는 방법으로 한계가 있음

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

  • 알고리즘을 그림으로 도식화하여 표현
  • 순서도의 작성 규칙에 따라 도식화하여 명령의 흐름을 쉽게 파악할 수 있지만, 복잡한 알고리즘을 표현하기에 효과적이지 못함
flowchart TD
    a((시작, 종료))
    b[입력, 출력]
    c((처리문, 치환문))
    d1{조건문, 판단문}

--->: 제어의 흐름

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

  • 순서도를 이용하여 1부터 5까지의 합을 구하는 알고리즘의 예
flowchart LR
    a((시작))
    a --> b[total = 0<br>n = 0]
    b --> c[n = n + 1]
    c --> d[total = total + n]
    d --> e{n = 5}

    e --> |Yes| f[/total/]
    e --> |NO| c
    f --> g((중료))
n total n = n + 1 total = total + n
0 0 1 1
1 1 2 3
2 3 3 6
3 6 4 10
4 10 5 15
5 - -

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

  • 프로그래밍 언어를 이용하여 표현
  • 알고리즘 자체가 실제로 구체화된 구현으로 추가적인 구체화 작업 필요 없음
  • 특정 프로그래밍 언어로 작성된 알고리즘의 경우 그 언어를 모르는 사람의 경우 이해가 어려움
  • 다른 언어로 개발해야 하는 경우 알고리즘을 번역하고 다른 프로그래밍 언어로 변환해야 하는 작업이 추가로 필요

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

  • 특정 프로그래밍 언어가 아니면서 프로그래밍 언어의 형태를 가진 가상 코드를 사용하여 표현
  • 프로그래밍 언어가 아니기에 실행할 수 없지만 일반적인 프로그래밍 언어의 형태를 가지고 있기 때문에, 나중에 특정 프로그래밍 언어로 변환(구체화)하기 용이함

가상 코드를 이용하여 1부터 5까지의 합을 구하는 알고리즘의 예

total <- 0;
n <- 0;
do 
    n <- n+1;
    total <- total + n;
while (n<5)
n total n = n + 1 total = total + n
0 0 1 1
1 1 2 3
2 3 3 6
3 6 4 10
4 10 5 15
5 - -

3. 알고리즘과 성능 분석

1) 가상 코드를 이용한 알고리즘의 표현

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

  • 가상 코드, 즉 알고리즘 기술 언어(ADL, Algorithm Description Language)를 사용하여 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 표현
  • 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능한대신 일반적인 프로그래밍 언어의 형태이므로 원하는 특정 프로그래밍 언어로의 변환 용이

가상 코드 기본요소

기호
  • 변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블 등을 나타냄
  • 문자나숫자의조합으로첫문자는반드시영문자사용
자료형
  • 정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형
연산자
  • 산술 연산자, 관계 연산자, 논리 연산자

지정문

변수에 값을 지정하는 방법

사용형식 : 변수 ← 값
- 지정 연산자(←)의 오른쪽에 있는 값(또는 식의 계산 결과 값이나 변수의 값)을 지정 연산자(←)의 왼쪽에 있는 변수에 저장하라는 의미 - 지정문에 사용할 수 있는식은 산술식, 부울식, 문자식등모든 연산식을 사용할 수 있음

예) - A ← 5; - A ← 3 + 2; - A ← B; 명령문은 세미콜론(;)을 사용하여 한 문장의 끝을 표 시하고 한 줄에 여러 개의 명령문을 쓸 수 있음

조건문

조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만듦 종류: if 문 과 case 문

if 문
  • 하나 이상의 명령문을 중괄호({})로 묶으면 하나의 명령문으로 취급함
  • 사용 형식 : if-then-else 형 
    if (조건식) then 명령문 1; 
else 명령문 2;
  • 순서도 표현 
    flowchart LR
    z[...] --> a{조건식}
    a --> |참| b[명령문1]
    a --> |거짓| c[명령문2]
중첩 if 문

  • 사용 형식 

    if (조건식 1) then 명령문 1;
else if (조건식 2) then 명령문 2;
else 명령문 3;

  • 순서도 표현 ㅉㅉㅈ 

    flowchart LR
    z[...] --> a{조건식1}
    a ---> |참| b[명령문1]
    a --> |거짓| c{조건식2}    
    c --> |참| d[명령문2]
    c --> |거짓| e[명령문3]
    b --> f[...]
    d --> f
    e --> f

예) 평균 90점 이상이면 ‘A’, 90 미만 80 이상이면 ‘B’, 80 미만 70 이상이면 ‘C’, 70 미만이면 ‘F’
if Average >= 90 then grade = “A”; 
else if Average >= 80 then grade = “B”;
else if Average >= 70 then grade = “C”; 
else grade = “F”;

순서도 표현 

flowchart LR
    z[...] --> a{Average >= 90}
    a --> |참| b[grade = A]
    a --> |거짓| c{Average >= 80}
    c --> |참| d[grade = B]
    c --> |거짓| e{Average >= 70}    
    e --> |참| f[grade = C]
    e --> |거짓| g[grade = F]

    b --> h[...]
    d --> h
    f --> h
    g --> h
case 문

  • 여러 조건식 중에서 해당하는 조건식을 찾아서 그에 대해 정해진 명령을 수행하는 조건문으로 하나의 case문은 중첩 if문과 같은 의미를 나타냄

  • 사용 형식 

    case {
        조건식 1 : 명령문 1; 
        조건식 2 : 명령문 2;
        ...
        조건식 n : 명령문 n;
        else : 명령문 n+1;
}

예) 평균 90점 이상이면 ‘A’, 90 미만 80 이상이면 ‘B’, 80 미만 70이상이면 ‘C’, 70 미만이면 ‘F’
case {
    Average >= 90 : grade = “A”; 
    Average >= 80 : grade = “B”;
    Average >= 70 : grade = “C”;
    else : grade = “F”
}

순서도는 if-else문과 큰 차이가 없어보여 생략

반복문

일정한 명령을 반복 수행하는 루프(loop) 형태의 제어구조
종류 : for 문, while-do 문, do-while 문

for 문
  • 사용 형식 
    for (초기값 ; 조건식 ; 증감값) 
do { 명령문; }
    • 초기값: 반복문을시작하는값
    • 조건식 : 반복 수행 여부를 검사하는 조건식
    • 증감값: 반복회수를계산하기위해서반복문을 한번 수행할 때마다 증가 또는 감소 시키는 값
    • 명령문은 하나 또는 여러 개 일수 있음

순서도 표현 

flowchart LR
    z[...] --> a{조건식 1}
    a --> |참| b[명령문]    
    b --> c[증감연산]
    c --> a
    a ----> |거짓| y[...]

while-do 문
  • 조건식을 검사하여 조건식이 “참”인 동안 명령문을 반복 수행
  • 사용 형식 
    while (조건식) 
do { 명령문; }

순서도 표현 

flowchart LR
    z[...] --> a{조건식 1}
    a --> |참| b[명령문]    
    b --> a
    a ---> |거짓| y[...]

do-while 문
  • 먼저 명령문을 수행하고 그 다음에 조건식을 검사하여 참이면 반복수행을 시작
  • do-while 문은 while-do 문과 달리 조건식이 참이 아니더라도 일단 명령문이 반드시 한번은 수행됨
  • 사용 형식 
    do { 명령문; }
while (조건식)

순서도 표현 

flowchart LR
    z[...] --> b[명령문]    
    b --> a{조건식 1}
    a --> |참| b
    a ---> |거짓| y[...]

함수문

어떤 문제를 처리하는 프로그램을 만들 때, 한 개의 프로그램으로 구성하는 것보다 처리할 작업 별로 모듈화하여 작은 단위
프로그램(함수) 여러 개로 나누어 구성하는 것이 효율적 임

  • 같은 일을 하나의 단위 프로그램에서 독립적으로 수행하게 되어 프로그램의 크기가 줄어듦
  • 수정과 관리, 재사용이 용이함
  • 함수 호출을 통해 독립적으로 실행되며, 매개변수를 사용하여 다른 함수 및 프로그램과 서로 연결

  • 사용 형식 

    함수 이름 (매개변수) 명령문;
    ...
    return 결과값;
end

    return 문은 함수의 실행 결과값을 함수를 호출한 위치로 반환하고 end 문으로 함수의 실행이 끝나게 됨

프로그램 A에서 함수B 호출과 함수의 실행 및 결과값 반환에 대한 제어 흐름

  • 생략

2) 성능 분석

알고리즘 성능 분석 기준

문제에 대한 해결방법은 하나 이상일 수 있음 → 그중 가장 효율적인 알고리즘을 결정해야 함

판단 기준
정확성
  • 올바른 입력에 대하여 유한 시간 내에 올바른 결과를 출력하는지를 판단
명확성
  • 알고리즘의 표현이 얼마나 이해하기 쉽고 명확하게 작성되었는지를 판단
수행량
  • 일반적인 연산을 제외하고 알고리즘의 특성을 나타내는 중요 연산들을 분석
메모리 사용량
  • 사용하는 명령어, 변수, 정보를 저장하기 위한 메모리를 얼마나 사용하는지를 판단
최적성
  • 알고리즘을 적용할 시스템의 사용 환경에 따라 수행량과 메모리 사용량이 달라지기 때문에 이들간의 최적화를 판단

알고리즘 성능 분석 방법

공간 복잡도

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

공간복잡도 = 고정공간 + 가변공간
  • 고정 공간 : 프로그램의 크기나 입출력의 횟수에 상관없이 고정적으로 필요한 저장 공간으로 프로그램의 저장공간, 변수 및 상수들을 저장하기 위한 공간
  • 가변 공간 : 실행 과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장
시간 복잡도

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

시간복잡도 = 컴파일시간 + 실행시간
  • 컴파일 시간 : 프로그램 마다 거의 고정적인 시간 소요
  • 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로, 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산

실행빈도수의 계산

  • 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행 시간 차이가 거의 없으므로, 하나의 단위 시간을 갖는 기본 명령문으로 취급하여 실행빈도수를 계산

    예) 피보나치 수열 알고리즘의 빈도수 구하기
    // 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 
// 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열

fibonacci(n)
    if (n < 0) then
        stop;
    if (n <= 1) then
        return n; 
    f1 ← 0;
    f2 ← 1;       
    for (i ← 2 ; i <= n; i ← i+1) do { 
        fn ← f1 + f2;
        f1 ← f2;
        f2 ← fn; 
    }
    return fn; 
end

  • n < 0, n = 0, n = 1 의 경우에 대한 실행 빈도수

  • for 반복문이 수행되지 않기 때문에 실행 빈도수가 작음
행 번호 n < 0 n = 0 n = 1
1 1 1 1
2 1 0 0
3 0 1 1
4 0 1 1
5~13 0 0 0
  • n > 1의 일반적인 경우에 대한 실행 빈도수
  • n에 따라 for반복문 수행
행 번 호 실행빈도수 행 번호 n = 1
1 1 8 n - 1
2 0 9 n - 1
3 1 10 n - 1
4 0 11 0
5 1 12 1
6 1 13 0
7 n

총 실행 빈도수 = 1+0+1+0+1+1+n+(n-1)+(n-1)+(n-1)+0+1+0 = 4n+2

시간 복잡도 표기법
  • 빅 오(Big Oh) 표기법 사용

  • 빅 오(Big Oh) 표기법 순서

  • 실행빈도수를구하여실행시간함수를찾고

  • 실행시간함수의 값에 가장 큰 영향을 주는 n에대한 항을 선택하여
  • 계수는생략하고 O(BigOh)의 오른쪽 괄호안에 표시
- 피보나치 수열의 시간 복잡도 = O (n)
  1. 실행시간 함수 : 4n+2
  2. N에대한항을선택:4n
  3. 계수4는 생략하고 O (Big-Oh)의 오른쪽 괄호안에 표시: O(n)


  • 각 실행시간 함수에서 n값의 변화에 따른 실행 빈도수 비교
logn n nlog \(n^2\) \(n^3\) \(2^n\)
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 4096 65536
5 32 160 1024 32768 4294967296

실행 빈도수가 상수값을 가지는 경우 O(1)로 표기하고 가장 빠른 실행 시간 함수가 됨