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

Presentation on theme: "Chapter 02. 소프트웨어와 자료구조."— Presentation transcript:

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

2 학습 목표 소프트웨어의 단계적 생명주기에 대한 이해 추상화와 구체화 알고리즘의 개념과 조건 알고리즘의 표현 방법
알고리즘의 선택 기준과 성능분석 방법

3 프로그램의 개발과 운영 및 유지보수에 관한 모든 정보와 작업 포함
소프트웨어 생명주기 프로그램의 개발과 운영 및 유지보수에 관한 모든 정보와 작업 포함 성공적인 소프트웨어 개발이란? 얼마나 정확하고 효율적으로 소프트웨어의 개발과 사용 및 관리가 이루어지는가? 개발할 소프트웨어에 대한 정확한 이해, 사용할 자료와 자료간의 연산관 계를 분석하여 최적의 자료구조 정의 자료구조에 대한 이론적, 실제적 고려 중요 소프트웨어 생명주기(Software Life Cycle) 소프트웨어를 체계적으로 개발하고 관리하기 위해서 개발 과정을 단계별로 나누어 구분한 것 일반적으로 6단계로 구분 요구분석, 시스템 명세, 설계, 구현, 테스트, 유지보수

4 소프트웨어 생명주기 소프트웨어 생명주기(Software Life Cycle) 일반적인 소프트웨어의 생명주기
필요한 단계로 피드백을 반복 수행하면서 소프트웨어의 완성도를 높인다.

5 소프트웨어 생명주기 1.요구분석 단계 2.시스템 명세 문제 분석 단계
개발할 소프트웨어의 기능과 제약조건, 목표 등을 소프트웨어 사용자와 함께 명확히 정의하는 단계 개발할 소프트웨어의 성격을 정확히 이해하고 개발 방법과 필요한 개발 자원 및 예산 예측 요구명세서 작성(소프트웨어 개발 완료 여부를 결정짓는 근거) 2.시스템 명세 시스템이 무엇을 수행해야 하는가를 정의하는 단계 입력 자료, 처리 내용, 생성되는 출력이 무엇인지를 정의 시스템 기능 명세서 작성 개발과정상에서 이견 또는 오류로 재개발 또는 사용자의 불만 발생치 않게 정확히 기재

6 소프트웨어 생명주기 3.설계 단계 시스템 명세 단계에서 정의한 기능을 실제로 수행하기 위한 방법을 논리적으로 결정하는 단계
시스템 구조 설계 시스템을 구성하는 내부 프로그램이나 모듈 간의 관계와 구조 설계 프로그램 설계 프로그램 내의 각 모듈에서의 처리 절차나 알고리즘을 설계 사용자 인터페이스 설계 사용자가 시스템을 사용하기 위해 보여지는 부분 설계

7 소프트웨어 생명주기 설계 방법(하향식, 상향식, 객체지향 설계) 하향식 설계 방법
상위단계에서 하위단계로 설계해가면서 점차 구체적으로 설계하는 방법 분할 정복 방식의 설계 방법

8 소프트웨어 생명주기 상향식 설계 방법 객체지향 설계 방법
하위단계의 작은 단위의 문제를 먼저 해결하고 이를 이용하여 상위단계의 큰 단위의 문제를 해결하는 방법 기존에 개발되어 문제해결 도구를 재사용할 수 있을 경우 개발기간 및 비용을 단축하고 신뢰성을 확보 객체지향 설계 방법 하위단위의 문제해결 도구를 객체로 만들어 재사용하는 방법으로 전체 문제를 해결하는 방법 자료와 처리 방법을 묶어서 객체를 만들어 사용

9 소프트웨어 생명주기 4.구현 단계 설계 단계에서 논리적으로 결정한 문제 해결 방법(알고리즘)을 프로그래밍언어를 사용하여 실제 프로그램을 작성하는 단계 사용할 프로그래밍 언어 선택:개발 기간, 비용, 테스트 및 유지보수에 영향 사용자의 요구, 프로그래머 능력, 현재 사용중인 언어, 컴파일러의 가용성과 품질, 지원 가능한 개발도구, 언어의 호환성, 개발 경험 등을 고려 프로그래밍 기법과 스타일 프로그래밍 순서 프로그래밍 기법 구조화 프로그래밍 지정문과 조건문, 반복문만을 사용하여 프로그램을 작성 순차구조, 선택구조, 반복구조의 세가지 제어구조로 표현 구조가 명확하여 정확성 검증과 테스트 및 유지보수 용이 모듈러 프로그래밍 프로그램을 여러 개의 작은 모듈로 나누어 계층 관계로 구성하는 프로그래밍 기법 각 모듈은 구조화 프로그래밍 기법으로 작성하고 기본적으로 하나의 기능만 수행토록 함 모듈별로 개발과 테스트 및 유지보수 가능 및 모듈의 재사용 가능

10 소프트웨어 생명주기 5.테스트 단계 개발한 시스템이 요구사항을 만족하는지, 실행결과가 예상한 결과와 정확하게 맞는지를 검사하고 평가하는 일련의 과정, 숨어있는 오류를 최대한 찾아내어 시스템의 완성도를 높이는 단계 1단계 - 단위 테스트(Unit Test) 시스템의 최소 구성요소가 되는 모듈에 대해서 개별적 시행으로 요구사 항 명세서에 기술된 기능을 제대로 수행하는지를 테스트 2단계 – 통합테스트(Integration test) 단위 테스트를 통과한 모듈을 연결하여 전체 시스템으로 완성하여 통합 적으로 시행하는 테스트 최소 모듈을 연결하여 점진적으로 통합 테스트(오류의 위치 파악) 구성요소 연결을 점진적으로 확장하면서 테스트 시행 하향식 테스트 상향식 테스트

11 소프트웨어 생명주기 3단계 – 인수 테스트 하향식/상향식 점진적 테스트
완성된 시스템을 인수하기 위해서 실제 자료를 사용한 최종 테스트 즉, 실질 적으로 사용하기 위한 마지막 테스트 알파테스트 : 사용자들이 직접 사용하는 테스트 베타테스트 : 잠정 고객에게 사용하도록 하여 오류를 찾아내는 테스트 상위 단계의 구성요소를 통합하여 테스트한 후에 각각의 구성요소에 부속된 하위 단계의 구성요소를 테스트 최하위 단위 프로그램을 테스트하고 그 상위 단계의 구성요소를 테스트

12 소프트웨어 생명주기 6.유지보수 단계 시스템이 인수되고 설치된 후 일어나는 모든 활동 유지보수의 유형 수정형 유지보수
소프트웨어 생명주기에서 가장 긴 기간 프로그램 오류 수정, 시스템 디자인 수정 새로운 요구사항 추가 시스템 사용 환경 변화에 대한 교정… 유지보수의 유형 수정형 유지보수 사용 중에 발견한 프로그램의 오류 수정 작업 적응형 유지보수 시스템과 관련한 환경적 변화에 적응하기 위한 재조정 작업 완전형 유지보수 시스템의 성능을 향상시키기 위한 개선 작업 예방형 유지보수 앞으로 발생할지 모를 변경 사항을 수용하기 위한 대비 작업

13 “성공한 S/W : 정확하고, 사용환경 변화에 대한 적응이 쉽고, 보안 기능이 있으며, 널리 사용되는 소프트웨어”
소프트웨어 생명주기 개발된 소프트웨어의 품질 평가 시스템 개발 초기에 유지보수에 대한 면밀한 계획 수립 필요 (유지>개발, 유지보수의 문제로 시스템 운영이 불가) 정확성 요구되는 기능들을 소프트웨어가 정확하게 수행하는 정도를 평가 유지 보수성 효율적 유지 보수의 정도를 평가 무결성 바이러스 등의 외부 공격에 대한 보안성 평가 사용성 사용자가 쉽고 편리하게 사용할 수 있는가에 대한 평가 “성공한 S/W : 정확하고, 사용환경 변화에 대한 적응이 쉽고, 보안 기능이 있으며, 널리 사용되는 소프트웨어”

14 추상 자료형 뇌의 추상화 기능 기억할 대상의 구별되는 특징만을 단순화하여 기억하는 기능

15 추상 자료형 컴퓨터를 이용한 문제해결에서의 추상화 크고 복잡한 문제를 단순화시켜 쉽게 해결하기 위한 방법
자료 추상화(Data Abstraction) 처리할 자료, 연산, 자료형에 대한 추상화 표현 자료 프로그램의 처리 대상이 되는 모든 것을 의미 연산 어떤 일을 처리하는 과정. 연산자에 의해 수행 예) 더하기 연산은 +연산자에 의해 수행 자료형 처리할 자료의 집합과 자료에 대해 수행할 연산자의 집합 예) 정수 자료형 자료 : 정수의 집합. {…, -1, 0, 1, …} 연산자 : 정수에 대한 연산자 집합. {+, -, x, ÷, mod}

16 추상 자료형 추상 자료형(ADT, Abstract Data Type) 추상화와 구체화
자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형 자료형에 대한 자료, 연산자의 특징, 연산자가 무엇을 수행 문제해결 방법인 알고리즘 개발이 쉽고, 원하는 프로그래밍 언어로 프로그램으로 구체화가 쉽다(구체적인 구현이 포함되지 않음) 추상화와 구체화 추상화 – “무엇(what)인가?”를 논리적으로 정의 구체화 – “어떻게(how) 할 것인가?”를 실제적으로 표현

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

18 객체지향과 절차지향 객체지향의 배경 소프트웨어 모듈의 재사용과 독립성을 강조 객체
소프트웨어 모듈의 재사용과 독립성을 강조 객체 효율적인 정보관리를 위하여 의미를 부여하고 분류하는 개념적인 단위 객체 지향(Object-Oriented) 대 절차지향(Procedural-Oriented) 절차지향 : 데이터 구조와 그 데이터를 변화 시키는 알고리즘으로 구성 모든 데이터의 구조에 대한 이해 필요 객체지향 : 객체들이 메시지(message)를 통하여 통신함으로써 원하는 결과를 얻는다. 각 객체는 고유의 데이터와 데이터를 처리할 수 있는 메소드로 구성

19 객체지향과 절차지향 공유 데이터 데이터 함수 절차지향 객체지향 객체 메 소 드 메소드
절차지향 객체지향 메시지 객체 메 소 드 메소드 데이터 절차지향 : 모든 데이터의 구조를 이해가 필요 객체지향 : 객체들의 집합(객체를 생성하고 객체들 간의 메시지를 통하여 정보를 교환 객체(object) : 데이터와 데이터를 처리하는 메소드로 구성 - 구성원 각각이 객체 - 예, 물건을 사오라 즉 사오는 것을 알고 있다는 것(즉 메소드를 갖고 있고 돈, 라면…은 데이터… 즉, 객체는 주어진 데이터와 메소드 만으로 일을 수행하는 단위 중요개념 : 객체(object), 클래스(class), 메시지(message), 갭슐화(encapsulation), 상속화(inheritance), 다형성(plymorphism)

20 객체지향의 장점 문제를 쉽고 자연스럽게 프로그램화(모델링) 할 수 있다 쉬운 프로그램의 개발로 인한 생산성 향상 시킬 수 있다
프로그램 모듈을 재사용 할 수 있다 프로그램의 확장 및 유지 보수가 용이하다

21 객체(Object) 효율적으로 정보를 관리하기 위하여, 사람들이 의미를 부여하고 분류하는 논리적인(개념적인) 단위
실세계에 존재하는 하나의 단위에 대한 소프트웨어적 표현 객체의 구성 속성(attribute)의 값을 나타내는 데이터(data) 데이터를 변경하거나 조작할 수 있는 메소드로 구성 자동차 사람.. 등 유,무형의 존재

22 객체의 예 아버지 객체 아들 객체 메소드 데이터 장난감, 자동차, 돈, 과자, 동화책, 술, 몽둥이, 신문, 게임기, 비디오,
객체는 프로그래머에 의해 모델링 아버지 객체 아들 객체 과자를 먹는다 동화책 을 읽는다 TV를 본다 메소드 데이터 자동차, 돈, 술, 몽둥이, 신문, 담배 운전을 한다 돈으로 물건을 산다 몽둥이로 때린다 담배를 피운다 술을 마신다 신문을 장난감, 과자, 동화책, 게임기, 비디오, TV 장난감을 가지고 논다 비디오 를 본다 게임을 한다

23 클래스(Class) 객체는 항상 클래스로부터 생성. 즉 클래스는 객체를 생성하는 형판(template)
하나의 클래스로부터 여러 개의 객체를 생성하는 형판 클래스는 두 개의 구성요소(member)인 자료구조(필드)와 연산(메소드)을 가진다 클래스로부터 생성된 객체를 instance라 한다. 객체 = instance 정보처리의 주체는 클래스가 아니라 객체이다 객체지향 프로그래밍의 시작은 클래스의 생성이다 클래스로부터 객체의 생성 예 동일한 속성과 메소드를 가진 객체 생성 = 클래스 하나의 클래스로부터 여러 개의 객체를 생성하는 형판 객체는 데이터와 메소드를 갖고 클래스는 데이터의 구조(속성)와 메소드를 갖는다 학생1 = new 학생(이기쁨, 남자, 컴퓨터공학과, 2학년) 객체 객체생성 클래스 매개변수 이름 명령어 이름 데이터

24 클래스 - 클래스로부터 객체의 생성 클래스 객체이름 데이터 메소드 클래스 이름 학생1=new 학생(이기쁨,남자,….);
성별 학과 학년 수강신청 시험보기 성적조회 클래스 이름 학생1=new 학생(이기쁨,남자,….); 학생2=new 학생(신예진,여자,….); 학생3=new 학생(이정순,여자,….); 속성(자료구조) 메소드(연산) 객체생성(instantiation) 객체이름 데이터 메소드 학생1 이기쁨 남자 컴퓨터공학과 2학년 수강신청 시험보기 성적조회 학생2 신예진 여자 경영학과 3학년 수강신청 시험보기 성적조회 학생3 이정순 여자 철학과 4학년 수강신청 시험보기 성적조회 객체 지향프로그램은 클래스 작성과 작성된 클래스로부터 객체의 생성, 객체사이의 메시지 전송이 프로그램의 전부 클래스에서 객체의 생성과정을 실체화(instantiation) 생성된 객체를 instance 인스턴스 (객체)

25 상속(inheritance) 상속관계의 클래스들은 계층구조를 구성할 수 있다
하위 계층의 클래스는 상위 계층의 모든 요소를 상속 받고 추가적으로 필요로 되는 새로운 자료구조와 메소드를 더 가진다 하위 클래스는 상위 클래스를 확장한 개념 상속의 개념을 이용하여 소프트웨어의 재사용(reusing)을 지원 * 예로, 학생 객체를 생성에서 생성된 객체에서 같은 속성과 메소드를 갖고 있는데 만든 객체와 비슷한 객체를 생성키위해서는 새로운 클래스를 생성해야되나 기존 클래스로부터 모든 속성과 메소드를 상속 받고 더 필요한 속성과 메소드를 추가하여 클래스를 생성할 수 있다

26 클래스의 상속 상속 (inheritance) 추가된 속성과 메소드 클래스 이름 속성(자료구조) 메소드(연산) 학생-high
성별 학과 학년 수강신청 시험보기 성적조회 클래스 이름 속성(자료구조) 메소드(연산) 학생-low 컨닝횟수 컨닝하기 추가된 속성과 메소드 상속 (inheritance)

27 클래스의 계층구조 클래스의 계층 구조 새로운 클래스를 생성할 때 기존 클래스의 하위 클래스로 선언할 수 있다.
새로운 클래스에 속성이나 메소드를 추가하여 기존 클래스를 확장할 수 있다. 클래스는 계층구조를 이룬다. 동물 새 양서류 물고기 포유류 코끼리 사자 사람 생물 식물 일반화 - 공통 속성 가짐 - 속성이 간단 특수화 - 상위속성 상속 - 개별속성 추가 - 속성이 많다 클래스의 계층 구조

28 + + + + + + = = = = 클래스계층 구조에서의 상속 관계 속성을 상속하여 새로운 클래스를 생성
: 새로 정의하여 추가한 속성 : 상속하여 재사용하는 속성 = 호흡함 생물 : 상속 경로 = 호흡함 + 걸어 다님 동물 = 호흡함 걸어 다님 + 젖으로 양육함 포유류 + 상속은 소프트웨어 설계를 간단하게 하고, 코드의 재사용을 높인다 다중상속은 여러 개의 클래스로부터 상속을 받아 새로운 클래스를 생성 + = 호흡함 걸어 다님 + 젖으로 양육함 + 웃음 사람 속성을 상속하여 새로운 클래스를 생성

29 상속의 예 person 상위(super) 클래스 student faculty staff 하위(sub) 클래스 undergrad
Undergrad : 재학생 graduate:졸업생 하위(sub) 클래스 undergrad graduate

30 캡슐화(encapsulation) 객체를 캡슐화 하여 What만 보여주고 How는 감춘다.
객체를 작성할 때 숨겨야 하는 정보(private)와 공개해야 하는 정보(public)를 구분하여 작성 객체의 사용자는 기능만 알고 사용하며 어떻게 처리되는지는 은폐된다(Information Hiding) 정보은폐 공개된 인터페이스 객체의 사용자들은 공개된 인터페이스를 통해서만 객체에 접근할 수 있다 숨겨진 데이터와 메소드들 public 객체 객체가 어떻게 처리하는지는 알 필요 없다(즉, 감기약의 성분을 알 필요가 없듯이) = encapsulation public public public 숨겨진 데이터에 대한 접근 불가

31 캡슐화의 장점 객체에 포함된 정보의 손상과 오용을 막을 수 있다. 객체 조작 방법이 바뀌어도 사용방법은 바뀌지 않는다.
데이터가 바뀌어도 다른 객체에 영향을 주지 않아 독립성이 유지된다. 처리된 결과만 사용하므로 객체의 이식성이 좋다. 객체를 부품화 할 수 있어 새로운 시스템의 구성에 부품처럼 사용할 수 있다. * Encapsulation을 통한 정보은폐의 장점

32 메시지(message) 메시지 수신객체 송신객체 메시지를 받을 객체의 이름(주소)
객체에게 일을 시키는 행위 메시지는 세가지 요소로 구성된다 메시지를 받을 객체의 이름(주소) 송신객체가 실행을 원하는 수신객체의 메소드 이름 실행을 원하는 메소드에 전달할 매개변수 객체 생성 = 컴퓨터 메모리 상에 생성 객체는 자신의 고유한 데이터만 갖고 생성(클래스의 데이터 구조와 메소드를 모두 갖지는 않는다) 다수개 생성된 객체는 클래스에 있는 메소드를 공유한다 수신객체 메시지 송신객체 객체이름.메소드(매개변수)

33 메시지의 예 Point 객체의 메소드 호출 클래스 P의 구조 int xPosition; int yPosition;
자료구조 int xPosition; int yPosition; boolean status; Color color; public class Point1 { P point; public static void main(String args[]) { point = new P(); // 객체의 생성 point.move(10,10); // 메시지 사용 point.setColor(blue); point.penUp(); point.penDown(); } void move(int x, int y); void setColor(Color c); void penUp(); void penDown(); 클래스 P의 구조

34 클래스 계층구조에서의 메시지 처리 상위 클래스에서 메소드 탐색 계속하여 상위 클래스를 탐색 소속 클래스에서 메소드 탐색
메소드1 메소드 5 자료 구조 자료 구조 메소드 2 메소드 4 상속 상속 메소드 6 메소드3 소속 클래스에서 메소드 탐색 메시지 도착 객체 고유 데이터 객체 고유 데이터 객체 객체2 (객체들은 자신이 가지는 고유의 데이터만 가지고 생성되며 메소드는 클래스에 있는 것을 공유 )

35 다형성(Polymorphism) “one interface, multiple implementation”
하나의 인터페이스를 사용하여 다양한 구현 방법을 제공 Polymorphism = 다양한(poly) + 변신(morphism)

36 다형성(Polymorphism) A3 A A1 A2 A1 superobject = new A(); (X)
A superobject = new A1(); (O) 상위클래스 타입의 객체 변수에 하위 클래스에서 생성된 객체를 할당 A1 superobject = new A(); (X) 하위클래스 타입의 객체 변수에 상위 클래스에서 생성된 객체를 할당 불가

37 다형성(Polymorphism) 모형 draw() 타원 draw() { 타원을 그린다 } 삼각형 draw() { 삼각형을
사각형 draw() { 사각형을 그린다 } * 추상 메소드 : 선언 부분만 있고 구현 부분이 없는 메소드(모형 메소드)

38 다형성(Polymorphism) A A1 A2 모형 A ; // 상위 클래스 타입의 객체 변수 A 선언
A = new 타원(); // 상위 클래스 타입의 객체 변수 A에 타원 클래스의 객체를 생성하여 할당 A.draw(); // 타원 클래스에 기술된 draw() 메소드를 수행하여 선언된 타원을 그린다 A = new 사각형(); // 상위 클래스 타입의 객체 변수 A에 사각형 클래스의 객체를 생성하여 할당 // 사각형 클래스에 기술된 draw() 메소드를 수행하여 선언된 타원을 그린다 ………………….. 모형에서 선언된 draw() 메소드는 할당되는 하위 클래스의 객체에 따라 다양한 변신을 시도하여 서로 다른 결과를 나타낸다 메시지에서 요구한 메소드(draw())의 매핑을 동적으로(실행시간) 수행

39 객체지향의 개념과 자바 프로그램 클래스 생성 메소드 생성 클래스 A로부터 상속받아 클래스 B 생성 클래스 B는 A로부터
class A { private int result1; public int add(int x,int y) { result1 = x + y; return result1; } public int subtraction(int x,int y) { result1 = x - y; class B extends A { private int result2; public int multi(int x,int y) { result2 = x * y; return result2; public int divide(int x,int y) { result2 = x / y; 클래스 생성 메소드 생성 클래스 A로부터 상속받아 클래스 B 생성 클래스 B는 A로부터 상속되었으므로 A의 메소드를 사용할 수 있다 클래스 내부 에서만 사용 하는 은폐된 변수

40 객체지향의 개념과 자바 프로그램 객체에게 메시지를 보낸다 objectb 객체는 클래스로부터 객체의 생성
메소드 add()를 가지고 있지 않으므로 상위 클래스를 탐색 하여 add() 메소드를 수행 클래스로부터 객체의 생성 class TestAB public static void main(String args[]) { int temp; A objecta = new A(); B objectb = new B(); temp = objecta.add(10,20); System.out.println( A의 add 수행결과 + temp); temp = objectb.add(1,2); System.out.println( B의 add 수행결과 + temp); temp = objectb.multi(2,2); System.out.println( B의 multi 수행결과 + temp); temp = objecta.multi(20,20); System.out.println( A의 multi 수행결과 + temp); } objecta 객체는 multi() 메소드를 가지고 있지 않으므로 에러를 발생

41 객체지향 프로그래밍(OOP) 언어 1960 1970 1980 1990 LISP ALGOL SIMULA Smalltalk C
Pascal Flavors Loops Objective-C Eiffel Object Pascal C++ CLOS Actor JAVA 객체지향 전통언어 전통 및 객체지향 객체지향 프로그래밍 언어들의 계보

42 알고리즘 알고리즘(Algorithm)의 이해 알고리즘
문제해결방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서 즉, 컴퓨터로 문제를 풀기 위한 단계적인 절차 알고리즘의 조건 입력(input) : 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다. 출력(output) : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다. 명확성(definiteness) : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다. 유한성(finiteness) : 알고리즘은 수행 뒤에 반드시 종료되어야 한다. 효과성(effectiveness) : 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다.

43 알고리즘 자료 >> 알고리즘 절차 연산 [요리 재료]
스펀지케이크(20×20cm) 1개, 크림치즈 200g, 달걀 푼 물 2개 분량, 설탕 3큰술, 레몬즙·바닐라에센스 1큰술씩, 딸기시럽(딸기 500g, 설탕 1½ 컵, 레몬즙 1작은술), 딸기 1개, 플레인 요구르트 2큰술 [요리법] ① 케이크 틀의 가장자리에 필름을 돌린 다음 스펀지케이크를 놓는다. ② 볼에 크림치즈를 넣고 거품기로 젓다가 달걀 푼 물과 설탕 3큰술을 세번에 나누어 넣으면서 크림 상태로 만든다. ③ ②에 레몬즙과 바닐라에센스를 넣고 살짝 저은 다음 ①에 붓는다. 이것을 180℃의 오븐에 넣고 20분 정도 굽는다. ④ 냄비에 슬라이스한 딸기와 설탕 1½ 컵을 넣고 끓이다가 약한 불에서 눌어붙지 않도록 저으면서 거품을 걷어낸다. 되직해지면 레몬즙을 넣고 차게 식힌다. ⑤ 접시에 치즈케이크를 한 조각 담고 ④의 시럽을 뿌린 다음 플레인 요구르트와 딸기를 얹어낸다 >> 알고리즘 절차 연산

44 알고리즘 알고리즘의 표현 방법 자연어를 이용한 서술적 표현 방법 순서도(Flow chart)를 이용한 도식화 표현 방법
인간이 읽기가 쉽다. 그러나 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모 호해질 우려가 있다 순서도(Flow chart)를 이용한 도식화 표현 방법 프로그래밍 언어를 이용한 구체화 방법 가상코드(Pseudo-code)를 이용한 추상화 방법

45 알고리즘 순서도를 이용한 알고리즘의 표현 순서도에서 사용하는 기호 장점 단점 알고리즘의 흐름 파악이 용이함
복잡한 알고리즘의 표현이 어려움

46 알고리즘 순서도의 예) 1부터 5까지의 합을 구하는 알고리즘

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

48 알고리즘 가상코드의 형식 기본 요소 지정문 기호 자료형 연산자 문장의 레이블 다음에는 콜론 사용형식
변수, 자료형 이름, 프로그램 이름, 레코드 필드 명, 문장의 레이블 등을 나타냄 문자나 숫자의 조합. 첫 문자는 반드시 영문자 사용. 문장의 레이블 다음에는 콜론 자료형 정수형과 실수형의 수치 자료형, 문자형, 논리형, 포인터, 문자열 등의 모든 자료형 사용 연산자 산술연산자, 관계연산자, 논리연산자 지정문 사용형식 지정연산자(←)의 오른쪽에 있는 값(또는 식의 계산 결과 값이나 변수의 값) 을 지정연산자(←)의 왼쪽에 있는 변수에 저장 명령문은 세미콜론 사용 변수  ← 값 ;

49 알고리즘 조건문 조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만든다. if 문 형식 : if 문의 제어 흐름

50 알고리즘 중첩 if 문 중첩 if 문의 제어 흐름

51 알고리즘 if Average >= 90 then grade = "A" ;
   else if Average >= 80  then  grade = "B" ;          else  if Average >= 70  then  grade = "c" ;                else  grade = "F" ;

52 알고리즘 case 문 여러 조건식 중에서 해당 조건을 찾아서 그에 대한 명령문을 수행 중첩 if 문으로 표현 가능 형식 :
             조건식-1 : 명령문1 ;              조건식-2 : 명령문2 ;                             조건식-n : 명령문n ;      else : 명령문n+1 ;        }   

53 알고리즘 case 문 사용 예) 평균 점수에 따른 등급 계산하기 case {
               Average >= 90 :  grade = "A" ;                Average >= 80 :  grade = "B" ;                Average >= 70 :  grade = "C" ;                else :  grade = "F" ;        }

54 알고리즘 반복문 일정한 명령을 반복 수행하는 루프(loop) 형태의 제어구조 for 문
형식 : 초기값 : 반복문을 시작하는 값 조건식 : 반복 수행 여부를 검사하는 조건식 증감값 : 반복 회수를 계산하기 위해서 반복문을 한번 수행할 때마다 증가 또는 감소시키는 값 for 문의 제어 흐름      for (초기값 ; 조건식 ; 증감값)  do  명령문 ;

55 알고리즘 while 문 while (조건식) do 명령문 ; 형식 : 조건식이 참인 동안 명령문을 반복 수행

56 알고리즘 do-while 문 do 명령문 ; while (조건식); 형식 :
일단 명령문을 한번 실행한 후에 조건식을 검사하여 조건식이 참인 동안 명령문을 반복 수행 do-while 문의 제어 흐름 do  명령문 ;      while (조건식);

57 알고리즘 함수문 처리작업 별로 모듈화하여 만든 부프로그램 형식 : 함수의 호출과 실행 및 결과값 반환에 대한 제어 흐름
     함수이름 (매개변수)           명령문 ;            ...           return  결과값 ;       end

58 성능분석 알고리즘 분석 판단 기준 정확성 명확성 : 알고리즘의 표현이 얼마나 이해하기 쉽고 명확하게 작성 되었는가? 수행량
문제에 대한 해결 방안은 여러 개 있을 수 있음(하나의 문제에 대한 여러 알고리즘) 가장 효율적이고 사용환경에 최적의 알고리즘을 결정하기 위해서는 알고리즘을 분석하고 평가. 알고리즘 분석 판단 기준 정확성 올바른 입력에 대한 유한 시간 내에 올바른 결과를 출력하는가? 명확성 : 알고리즘의 표현이 얼마나 이해하기 쉽고 명확하게 작성 되었는가? 알고리즘이 명확할수록 이해와 변경이 쉽고 정확성을 판단하기 쉬워진다. 수행량 일반적 연산은 제외하고 알고리즘의 특성을 나타내는 중요연산을 분석 메모리 사용량 프로그램이 사용하는 명령어, 변수, 입출력 자료의 정보를 저장하는 메모리도 판단 기준 최적성 알고리즘을 적용할 시스템의 환경에 따라 수행량과 메모리 사용량이 달라진다, 좋은 알고리즘은 최적 알고리즘

59 성능분석 알고리즘 성능 분석 방법 공간 복잡도 : 실행에 필요한 공간 측면에서 분석
알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양 공간 복잡도 = 고정 공간(프로그램 크기, 입출력횟수에 무관, 프로그램 저장 공간 및 변 수) 가변 공간(실행과정에 필요한 자료, 변수 공간, 관련 정보공간) 시간 복잡도 : 실행에 소요되는 시간 측면에서 분석, 알고리즘간의 비교 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간 시간 복잡도 = 컴파일 시간 + 실행 시간 컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산 실행 빈도수의 계산 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차이가 거의 없으므로 하나의 단위시간으로 갖는 기본 명령문으로 취급

60 성능분석 예) 피보나치 수열 알고리즘의 빈도수 구하기

61 성능분석 n<0, n=0, n=1의 경우에 대한 실행 빈도수 for 반복문이 수행되지 않기 때문에 실행 빈도수가 작다.

62 성능분석 n>1의 일반적인 경우에 대한 실행 빈도수 n에 따라 for 반복문 수행
총 실행 빈도수 = n+(n-1)+(n-1)+(n-1) = 4n+2

63 성능분석 시간 복잡도 표기법 빅-오(Big-Oh) 표기법 사용 빅-오(Big-Oh) 표기법 순서
실행 빈도수를 구하여 실행시간 함수 찾기 실행시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택하여 계수는 생략하고 O (Big-Oh)의 오른쪽 괄호 안에 표시 피보나치 수열의 시간 복잡도 = O (n) 실행시간 함수 : 4n+2 n에 대한 항을 선택 : 4n 계수 4는 생략하고 O (Big-Oh)의 오른쪽 괄호 안에 표시 : O (n)

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

65 Thank you