강의 소개, 자료구조의 개념, SW 개발과 자료구조 C언어 응용 제 1 주 강의 소개, 자료구조의 개념, SW 개발과 자료구조

강의소개 담당교수 : 컴퓨터시뮬레이션학과 이형원 교재 : C로 배우는 쉬운 자료구조 강의시간 : 월1,2 수5,6교시, E323 평가방법 네 번의 필기 시험 : 총 30% 1,3차 시험 : 각 5% 중간, 기말 필기고사 : 각 10% 두 번의 실기 시험 : 총 30%(각 15%) 10번의 숙제 : 총 20% 수업참여 : 10% 출석 : 총 10%

강의자료 http://comsi.inje.ac.kr ->자료실->강의자료실

강의자료 http://ecampus.inje.ac.kr 로그인 후 사용

강의자료

강의 일정 1주차 : 강의 안내, 자료구조의 개념, SW 새발과 자료구조(1,2장) 2주차 : 추석 휴강 3주차 : C 프로그램 기법, 순차 자료구조(3장,4장) 4주차 : 1차 필기시험 5주차 : 연결자료구조, 스택(5장, 6장) 6주차 : 스택, 큐(6장, 7장) 7주차 : 큐(7장) 8주차 : 중간고사 필기 및 실기 시험

강의일정(계속) 9주차 : 트리(8장) 10주차 :트리, 그래프(8장, 9장) 11주차 : 그래프(9장) 12주차 : 3차필기 시험 13주차 : 정렬(10장) 14주차 : 정렬, 검색(10장, 11장) 15주차 : 검색(11장) 16주차 : 기말고사 필기 및 실기 시험

강의 진행 강의 노트 준비 지난 주 실습 내용 토론하기 내용에 대한 질문과 답하기 새로운 단어 이해하기 실습 내용 설명 및 실습시간에 실습하기 다음 주 강의 내용 교재 읽어오기 숙제 해서 제출하기

시험 준비 각자 A4의 ¼ 크기의 요약집을 준비 한다. (10 점 제공, 시험시간에 제출)

다음 주 과제 3,4장 읽어오기 숙제 해서 제출하기

C로 프로그램 개발하기(1학기 복습) 컴퓨터 프로그램 응용(application) 프로그램 프로그램 실행 과정 수집한 여러 가지 데이터(data)에 대해 정해진 절차대로 특별한 처리를 수행하여 의사 결정에 사용할 수 있는 정보(information)를 얻기 위해 컴퓨터에게 내리는 명령을 모아놓은 것 응용(application) 프로그램 운영체제 외에 사용자의 목적에 맞게 개발되어 배포되는 프로그램 워드 프로세서(아래아 한글, MS-워드 등) 그래픽 편집 프로그램(포토샵 등) 프레젠테이션 제작 도구(MS-파워포인트 등) 스프레드시트(MS-엑셀 등) 프로그램 실행 과정 프로그램은 주기억장치에 저장 즉 적재(loading)된 후 CPU에 의해 명령이 하나씩 해석된 후 적절한 장치에 의해 실행된다.

1.3 프로그램 개발 과정 프로그램 개발 과정

통합 개발 환경의 종류 비주얼 C++(Visual C++) 마이크로소프트사의 제품 윈도우 기반의 거의 모든 형태의 응용 프로그램 제작 가능 최신 버전: 비주얼 C++ 2012

통합 개발 환경의 종류 Eclipse 오픈소스 기반의 개발 플랫폼 최신 버전: INDIGO, JUNO, KEPLER(최신) Cygwin(gcc), CDT Perspective 이용

통합 개발 환경의 종류 Dev-C++ 오픈 소스 프로젝트의 산물 C/C++ 통합 개발 환경 GCC 컴파일러 이용 무료

Eclipse 개발 환경 만들기 Cygwin 설치 : http://www.cygwin.org 환경변수 설정 CDT 설치 : Eclipse 의 Help 메뉴에서 검색

Cygwin 설치하기 Setup 프로그램 다운 로드

Setup 프로그램 실행

Setup 프로그램 실행 오류창 무시

Setup 프로그램 실행 아이콘 확인 콘솔 창에서 gcc –-version 동작 확인

환경변수 설정 제어판->시스템 및 보안->시스템->고급시스템설정 C:\cygwin\bin 추가

Eclipse 설치하기 Download & Installation (http://www.eclipse.org)

eclipse Download & Installation (http://www.eclipse.org)

eclipse Download & Installation (http://www.eclipse.org) Download and save to directory

eclipse Download & Installation (http://www.eclipse.org) Unzip downloaded file Copy eclipse directory to Program Files or Program Files (x86) Currently eclipse support only 32bit JRE

eclipse overview eclipse made of one or more plug-ins

Eclipse를 이용한 프로그램 개발 eclipse의 기동 (INDIGO, Juno, Kepler)

CDT(C Development Tool) 설치 Help -> Install New Software…

CDT(C Development Tool) 설치 CDT Juno - http://download.eclipse.org/tools/cdt/releases/juno Select the site

Eclipse 개념 Workbench ~ Workspace 실습시 Workspace : D:\Lec_hwl\capp\y2014

Eclipse 개념 Project 작업의 기본 단위 응용프로그램단위로 프로젝트 생성

Eclipse실행

Eclipse실행

Perspective 선택 클릭후 원하는 것 선택

응용프로그램 만들기 C Project 생성 소스(Source) 파일 추가(파일명에 .c 추가) 실행파일 빌드 실행 실습프로그램 화면에 “Hello C Express” 라고 출력한다.

C Project 생성 프로젝트 명 입력 저장 디렉토리 확인 프로젝트 종류 선택 (Empty Project) 콤파일러 선택 (Cygwin gcc) 다음 단계로 이동

C Project 생성 생성 완료 내용이 없는 프로젝트 Hi 생성

소스파일 추가 소스 이름 hi.c 클릭후 오른쪽 버튼 클릭

소스파일 추가 소스 목록 소스 편집 창

디렉토리 구조 소스파일 Workspace 이름 Project 이름

소스 수정 * 표시는 수정 후 저장이 안되었다는 의미 필요한 소스 추가 저장 또는 모두저장 버튼을 클릭하면 저장됨

빌드하기

실행하기(도스창) 실행명령 Hi 실행 결과 실행 파일

실행하기(Eclipse) 실행 결과

비주얼 C++ 설치

워크스페이스와 프로젝트 솔루션(solution); 문제 해결에 필요한 프로젝트가 들어 있는 컨테이너 프로젝트(project): 하나의 실행 파일을 만드는데 필요한 여러 가지 항목들이 들어 있는 컨테이너

프로젝트 생성하기

프로젝트 생성하기

프로젝트 생성하기

소스 파일 생성하기

소스 파일 생성하기

프로그램 입력

프로그램 입력

전문가 설정

컴파일하기

프로그램 실행 하기

프로그램 기본 논리 순차(sequence) 분기(branch) 반복(loop) if, if~else, switch for while do~while

자료구조 자료구조 개요 자료구조의 분류 자료의 표현

자료구조의 의미와 중요성을 알아본다. 자료구조에서 다루는 내용을 알아본다. 컴퓨터 내부의 2진수 코드 체계를 알아본다. 자료의 형태에 따른 자료 표현 형식을 알아본다.

자료구조 자료구조란 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업 [그림 1-1] 자료구조의 예

자료구조의 필요성 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 하기 때문에 자료구조에 대한 개념과 활용 능력을 필요로 한다. [그림 1-2] 문제해결 과정

자료구조의 내용 [그림 1-3] 자료구조의 내용

자료의 형태에 따른 분류 [그림 1-4] 자료구조의 형태에 따른 분류

디지털 시스템에서의 자료의 표현 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료를 2진수 코드로 표현하여 저장 및 처리 1과 0, ON과 OFF, 참(True)과 거짓(False)의 조합 2진수 코드의 단위 [그림 1-5] 비트와 니블과 바이트

n개의 비트로 2n개의 상태수 표현 예) n=2 인 경우 예) n=4 인 경우 [그림 1-6] n개의 비트로 2n개의

컴퓨터 내부에서 표현할 수 있는 자료의 종류 [그림 1-8] 컴퓨터 내부에서 자료를 표현하는 방법

10진수의 표현 10진수의 존(Zone) 형식의 표현 10진수 한자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식 존 영역 상위 4비트 1111로 표시 수치 영역 하위 4비트 표현하고자 하는 10진수 한자리 값에 대한 2진수 값을 표시 존 형식의 구조 [그림 1-9] 존 형식의 구조

수치 영역의 값 표현 [표 1-1] 4비트의 2진수에 대한 10진수 표현

여러 자리의 10진수를 표현하는 방법 존 형식으로 10진수를 표현하는 예 10진수의 자릿수 만큼 존 형식을 연결하여 사용 마지막 자리의 존 영역에 부호를 표시양수 (+) : 1100 음수(-) : 1101 존 형식으로 10진수를 표현하는 예 +213 -213 [그림 1-10] 존 형식의 10진수 표현 형식 2 1 3 1111 0010 0001 1100 0011 F 2 1 C(+) 3 2 1 3 1111 0010 0001 1101 0011 F 2 1 D(-) 3

팩(Pack) 형식의 표현 10진수 한자리를 표현하기 위해서 존 영역 없이 4비트를 사용하는 형식 최하위 4비트에 부호를 표시 양수(+) : 1100 음수(-) : 1101 팩 형식으로 10진수를 표현하는 예 + 213 - 213 [그림 1-11] 팩 형식의 10진수 표현 형식 0010 0001 0011 1100 2 1 3 C(+) 0010 0001 0011 1101 2 1 3 D(-)

2진수의 정수 표현 n비트의 부호 절대값 형식 최상위 1비트 - 부호 표시 나머지 n-1 비트 – 이진수 표시 양수(+) : 0 음수(-) : 1 나머지 n-1 비트 – 이진수 표시 1바이트를 사용하는 부호 절대값 형식의 예 1비트 ←  7 비트      → 0  0  1  0  1  0  1 부호 21의 절대값  1비트 ← 7 비트      → 1 0  0  1  0  1  0  1 부호 21의 절대값 

1의 보수(1’ Complement) 형식 음수의 표현에서 부호 비트를 사용하는 대신 1의 보수를 사용하는 방법 예) 10진수 21을 1의 보수로 만들기 (1바이트 사용) 1바이트를 사용하는 1의 보수 형식의 예 + 21  - 21 부호절대값형식의 양수 표현과 같음      1 1 1 1 1 1 1 1  -  0 0 0 1 0 1 0 1 ☜  21의 2진수 값     1 1 1 0 1 0 1 0  21의 1의 보수 0  0  1  0  1  0  1 ←  21의 절대값      → 1 1  1  0  1  0  1  0 ←  21의 1의 보수     →

2의 보수(2’ Complement) 형식 음수의 표현에서 부호 비트를 사용하는 대신 2의 보수를 사용하는 방법 1의 보수에 1을 더해준다. 예) 10진수 21을 2의 보수로 만들기 (1바이트 사용) 1바이트를 사용하는 2의 보수 형식의 예 + 21  - 21 부호절대값 형식의 양수 표현과 같음 2진수 정수의 세 가지 표현 방법에서 양수의 표현은 같고, 음수의 표현만 다르다.      1 1 1 1 1 1 1 1  -  0 0 0 1 0 1 0 1 ☜  21의 2진수 값     1 1 1 0 1 0 1 0 + 1  21의 1의 보수     1 1 1 0 1 0 1 1  21의 2의 보수 0  0  1  0  1  0  1 ←  21의 절대값      → 1 1  1  0  1  0  1  1 ←  21의 2의 보수     →

2진수의 실수 표현 고정 소수점 표현 부동 소수점 형식의 표현 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어있는 것으로 취급하는 방법 고정 소수점 표현의 00010101 은 0.00010101 의 실수 값을 의미 부동 소수점 형식의 표현 고정 소수점 형식에 비해서 표현 가능한 값의 범위가 넓다. 실수를 부호와 지수, 소수의 세 부분으로 구분하여 표현 4바이트를 사용하는 부동 소수점 형식 [그림 1-12] 4바이트 부동소수점 표현 형식

문자자료의 표현 문자에 대한 이진수 코드를 정의하여 사용 문자에 대한 이진수 코드표 6비트를 사용하여 문자 표현 BCD 코드 EBCDIC 코드 ASCII 코드 6비트를 사용하여 문자 표현 상위 2비트 : 존 비트 하위 4비트 : 2진수 비트 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어 대문자와 특수문자를 표현 BCD 코드의 구성 [그림 1-13] BCD 코드의 구성

[표 1-2] BCD 코드 표 예) 영문자 A에 대한 BCD 코드 ☞ 010001 [표 1-2] BCD 코드 표

EBCDIC 코드 EBCDIC 코드의 구성 8비트를 사용하여 문자 표현 상위 4비트 : 존 비트 하위 4비트 : 2진수 비트 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어 대문자/소문자와 특수문자를 표현 EBCDIC 코드의 구성 [그림 1-14] EBCDIC 코드의 구성

[표 1-3] EBCDIC 코드 표 예) 영문자 A에 대한 EBCDIC 코드 ☞ 11000001

ASCII 코드 ASCII 코드의 구성 7비트를 사용하여 문자 표현 상위 3비트 : 존 비트 하위 4비트 : 2진수 비트 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어 대문자/소문자와 특수문자를 표현 ASCII 코드의 구성 [그림 1-15] ASCII 코드의 구성

[표 1-4] ASCII 코드 표 예) 영문자 A에 대한 ASCII 코드 ☞ 1000001 [표 1-4] ASCII 코드표

논리자료 논리값 방법1) 방법2) 방법3) 논리값을 표현하기 위한 자료 형식 참(true)과 거짓(false), 1과 0 1바이트를 사용하여 논리자료를 표현하는 방법 방법1) 참 - 최하위 비트를 1로 표시. 00000001 거짓 – 전체 비트를 0으로 표시. 00000000 방법2) 참 – 전체 비트를 1로 표시. 11111111 방법3) 참 – 하나 이상의 비트를 1로 표시

포인터 자료 문자열(string) 자료 메모리의 주소를 표현하기 위한 자료 형식 변수의 주소나 메모리의 특정 위치에 대한 주소를 저장하고 주소연산 하기 위해 사용 문자열(string) 자료 여러 문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식 하나의 문자열 자료에 포함된 부분문자열을 표현하는 방법 방법1) 부분문자열 사이에 구분자를 두고 연속 저장하는 방법 방법2) 가장 긴 부분문자열의 길이에 맞추어 고정 길이로 연속 저장하는 방법 방법3) 부분문자열을 연속 저장하고 각 부분문자열에 대한 포인터를 사용하는 방법

부분문자열의 표현 예 표현할 문자열 : {COMPUTER, DATA STRUCTURE, STRING} 방법1) 구분자를 사용하는 표현 : 구분자로 세미콜론(;) 사용 방법2) 고정길이를 사용하는 표현 [그림 1-16] 구분자를 사용하여 저장하는 방법_방법 1 [그림 1-17] 고정 길이로 저장하는 방법_방법 2

부분문자열의 표현 예 방법3) 포인터를 사용하는 표현 [그림 1-18] 포인터를 사용하여 저장하는 방법_방법 3

부분 문자열 표현 방법의 비교 [표 1-5] 문자열 표현 방법 비교

소프트웨어와 자료구조 소프트웨어 생명주기 추상 자료형 알고리즘 성능 분석 한빛미디어(주)

소프트웨어의 단계적 생명 주기를 이해한다. 추상화와 구체화를 이해한다. 알고리즘의 개념과 조건을 이해하고 알고리즘의 표현 방법을 알아본다. 알고리즘의 선택 기준과 성능 분석 방법을 알아본다.

소프트웨어 생명주기(Software Life Cycle) 성공적인 소프트웨어 개발 얼마나 정확하고 효율적으로 소프트웨어의 개발과 사용 및 관리가 이루어지는가? 개발할 소프트웨어에 대한 정확한 이해 사용할 자료와 자료간의 연산관계를 분석하여 최적의 자료구조 정의 소프트웨어 생명주기(Software Life Cycle) 소프트웨어를 체계적으로 개발하고 관리하기 위해서 개발 과정을 단계별로 나누어 구분한 것 일반적으로 6단계로 구분

일반적인 소프트웨어의 생명주기 필요한 단계로 피드백을 반복 수행하면서 소프트웨어의 완성도를 높인다. [그림 2-1] 소프트웨어 생명 주기

요구분석 단계 시스템 명세 설계 단계 문제 분석 단계 개발할 소프트웨어의 기능과 제약조건, 목표 등을 소프트웨어 사용자와 함께 명확히 정의하는 단계 개발할 소프트웨어의 성격을 정확히 이해하고 개발 방법과 필요한 개발 자원 및 예산 예측 요구명세서 작성 시스템 명세 시스템이 무엇을 수행해야 하는가를 정의하는 단계 입력 자료, 처리 내용, 생성되는 출력이 무엇인지를 정의 시스템 기능 명세서 작성 설계 단계 시스템 명세 단계에서 정의한 기능을 실제로 수행하기 위한 방법을 논리적으로 결정하는 단계 시스템 구조 설계 시스템을 구성하는 내부 프로그램이나 모듈 간의 관계와 구조 설계

설계 방법 프로그램 설계 사용자 인터페이스 설계 하향식 설계 방법 프로그램 내의 각 모듈에서의 처리 절차나 알고리즘을 설계 사용자가 시스템을 사용하기 위해 보여지는 부분 설계 설계 방법 하향식 설계 방법 상위단계에서 하위단계로 설계해가면서 점차 구체적으로 설계하는 방법 분할 정복 방식의 설계 방법 [그림 2-2] 하향식 설계 방법

상향식 설계 방법 하위단계의 작은 단위의 문제를 먼저 해결하고 이를 이용하여 상위단계의 큰 단위의 문제를 해결하는 방법 객체지향 설계 방법 하위단위의 문제해결 도구를 객체로 만들어 재사용하는 방법으로 전체 문제를 해결하는 방법 [그림 2-3] 상향식 설계 방법

구현 단계 설계 단계에서 논리적으로 결정한 문제 해결 방법(알고리즘)을 프로그래밍언어를 사용하여 실제 프로그램을 작성하는 단계 프로그래밍 기법 구조화 프로그래밍 지정문과 조건문, 반복문만을 사용하여 프로그램을 작성 순차구조, 선택구조, 반복구조의 세가지 제어구조로 표현 구조가 명확하여 정확성 검증과 테스트 및 유지보수 용이 모듈러 프로그래밍 프로그램을 여러 개의 작은 모듈로 나누어 계층 관계로 구성하는 프로그래밍 기법 모듈별로 개발과 테스트 및 유지보수 가능 모듈의 재사용 가능

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

3단계 – 인수 테스트 완성된 시스템을 인수하기 위해서 실제 자료를 사용한 최종 테스트 [그림 2-4] 하향식 테스트/상향식 테스트

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

개발된 소프트웨어의 품질 평가 정확성 유지 보수성 무결성 사용성 요구되는 기능들을 정확하게 수행하는 정도를 평가 효율적 유지 보수의 정도를 평가 무결성 바이러스 등의 외부 공격에 대한 보안성 평가 사용성 사용자가 쉽고 편리하게 사용할 수 있는가에 대한 평가

뇌의 추상화 기능 기억할 대상의 구별되는 특징만을 단순화하여 기억하는 기능 [그림 2-5] 뇌의 추상화 기능

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

추상 자료형(ADT, Abstract Data Type) 자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형 추상화와 구체화 추상화 – “무엇(what)인가?”를 논리적으로 정의 구체화 – “어떻게(how) 할 것인가?”를 실제적으로 표현 자료와 연산에 있어서의 추상화와 구체화의 관계 [그림 2-6] 추상화와 구체화의 예 [표 2-1] 자료와 연산의 추상화와 구체화

알고리즘 알고리즘의 표현 알고리즘의 조건 문제해결방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서 입력(input) : 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다. 출력(output) : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다. 명확성(definiteness) : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다. 유한성(finiteness) : 알고리즘은 수행 뒤에 반드시 종료되어야 한다. 효과성(effectiveness) : 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야 한다. 알고리즘의 표현 자연어를 이용한 서술적 표현 방법 순서도(Flow chart)를 이용한 도식화 표현 방법 프로그래밍 언어를 이용한 구체화 방법 가상코드(Pseudo-code)를 이용한 추상화 방법

순서도를 이용한 알고리즘의 표현 순서도에서 사용하는 기호 장점 단점 알고리즘의 흐름 파악이 용이함 복잡한 알고리즘의 표현이 어려움 [그림 2-8] 순서도에 사용되는 기호

순서도의 예) 1부터 5까지의 합을 구하는 알고리즘 가상코드를 이용한 알고리즘의 표현 가상코드, 즉 알고리즘 기술언어(ADL, Algorithm Description Language)를 사용하여 프로그래밍 언어의 일반적인 형태와 유사하게 알고리즘을 표현 특정 프로그래밍 언어가 아니므로 직접 실행은 불가능 일반적인 프로그래밍 언어의 형태로 원하는 특정 프로그래밍 언어로의 변환 용이 [그림 2-9] 1부터 5까지의 합을 구하기 위한 순서도

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

조건문 조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만든다. if 문 if (조건식) then 명령문1; 형식 : if 문의 제어 흐름     if (조건식) then 명령문1;     else 명령문2; 또는   if (조건식) then 명령문1; [그림 2-10] if 문의 제어 흐름

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

if Average >= 90 then grade = "A" ;    else if Average >= 80  then  grade = "B" ;          else  if Average >= 70  then  grade = "c" ;                else  grade = "F" ;

case 문 여러 조건식 중에서 해당 조건을 찾아서 그에 대한 명령문을 수행 중첩 if 문으로 표현 가능 형식 : 역할을 담당해야 하는지 구분하여 정의      case {              조건식-1 : 명령문1 ;              조건식-2 : 명령문2 ;                ...              조건식-n : 명령문n ;      else : 명령문n+1 ;        }    [그림 2-12] case 문의 제어 흐름

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

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

while 문 while (조건식) do 명령문 ; 형식 : 조건식이 참인 동안 명령문을 반복 수행 while 문의 제어 흐름

do-while 문 do 명령문 ; while (조건식); 형식 : 일단 명령문을 한번 실행한 후에 조건식을 검사하여 조건식이 참인 동안 명령문을 반복 수행 do-while 문의 제어 흐름 do  명령문 ;      while (조건식); [그림 2-15] do-while 문의 제어 흐름

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

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

예) 피보나치 수열 알고리즘의 빈도수 구하기 fibonacci(n) 01 if (n<0) then 02 stop ; 04 return n ; 05 f1 ← 0 ; 06 f2 ← 1 ; 07 for (i←2 ; i≤n ; i←i+1) do { 08 fn←f1+f2 ; 09 f1←f2 ; 10 f2←fn ; 11 } 12 return fn ; 13 end

n<0, n=0, n=1의 경우에 대한 실행 빈도수 for 반복문이 수행되지 않기 때문에 실행 빈도수가 작다. [표 2-2] 피보나치 수열 알고리즘의 실행 빈도수 : n<0, n=0, n=1의 경우

n>1의 일반적인 경우에 대한 실행 빈도수 n에 따라 for 반복문 수행 총 실행 빈도수 = 1+0+1+0+1+1+n+(n-1)+(n-1)+(n-1)+0+1+0 = 4n+2 [표 2-3] 피보나치 수열 알고리즘의 실행 빈도수 : n>1의 경우

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

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