자료구조

　자료구조 요점 정리
1. 자료의 정의
자료(data) : 어떤 사실이나 개념의 값들 또는 값들의 집합
자료원소(data element) : 자료를 나타내는 값들 중의 하나(자료의 기본 구성 원소)
　
자료의 구성단위
필드(field) : 한 속성(attribute) 자료
레코드(record) : 모든 속성에 관한 자료 (필드의 모임)
파일(file) : 레코드의 모임.
예) 사원 인사자료
사원 이름 사원 번호 남여 급여(원)
Brown 1065 여 500,000
Davis 7282 남 550,000
　
속성 명(필드 명) : 사원 이름, 사원 번호, 남여, 급여
사원 이름 속성 값(속성 자료) : Brown, Davis
사원 번호 속성 값 : 1065, 7282
레코드 : 한 사원의 모든 속성에 관한 자료
첫번째 레코드 값 : Brown 1065 여 500,000
정보(Information) : 자료가 컴퓨터에 의해 처리되어, 어떤 조직체에 의미가 있고 적절히 사용될 수 있는 형태로 변형된것
2. 문제 풀이의 단계
컴퓨터로 문제 풀이시 고려 사항
자료구조 (data structure)
자료는 자료 원소의 집합으로 구성되어 있으며, 자료 원소간에는 논리적인 관계가 있다. 자료 원소간의 논리적인 관계가 표현 되도록 자료 원소를 구성한 것
　
자료 구조를 어떤 자료 구조로 구성해야 할까를 선택
　
연산작업
사용될 자료 구조에서 수행 되어야 할 연산 작업을 결정
자료구조를 만들거나 없애는 작업, 자료구조에 새로운 원소를 삽입/삭제/갱신
　
저장방법
자료구조를 기억장소 내에서 물리적으로 표현한 것을 저장구조(storage structure)
한 자료구조에 대한 저장 구조는 여러 가지일수 있다(트리의 자료구조는 기억장소에 순차적으로 저장 할 수도 있고 비순차적으로 저장 할 수도 있다.)
저장 구조 선택시 고려 사항
1. 자료 원소간의 논리적 관계가 유지 될수 있어야 함.
2. 연산이 효율적으로 수행
　
프로그램 언어
프로그램 언어에 따라 선택된 자료 구조가 제공 되지 않을 수가 있음
포인터 자료구조(C에서는 지원 되나, FORTRAN에서는 제공 되지 않음)
　
3. 자료구조
컴퓨터가 초기에는 주로 수치적인 문제를 풀기 위해 사용되었으나, 점차 비수치적인 문제를 해결하기 위해 더 많이 사용
수치적인 문제 해결 : 정수, 실수, 배열
비수치적인 문제 해결 : 구조체, 포인터, 등
　
자료구조 구분
기본 자료구조 파생 자료구조 사용자 정의 자료구조
선형 비선형
정수
실수
문자 배열
구조체
포인터
클래스 연결 리스트
스택
큐 트리
그래프
　
　
4. 알고리즘
　
41. 알고리즘 정의
　
알고리즘
특정한 문제를 풀기 위해 정해진 일련의 명령
- 이차함수를 푸느 방법, 요리법
컴퓨터에 의해 수행 될수 있고, 프로그램 작성이 가능하여야함.
　
프로그램
추상적인 형태로 표현한 알고리즘을 컴퓨터가 수행 할수 잇도록 구체적인 형태로 표현한 것
　
알고리즘의 조건
1) 명확성 (definitness): 일상적인 언어에는 모호함이 많음(예 : 빨간색, 비싸다, 작다 등)
부호를 사용하여 명확하게 표형 가능 (프로그램언어)
2) 유한성 (finiteness): 유한한 시간내에 유한한 단계를 거쳐 끝이 나야함.
3) 유효성 (efffectiveness): 수행가능한 명령으로 구성
의 완전한 값 사용, 0/2 등
　
4) 정확성 (correctness) : 수행한 결과가 문제를 해결할수 있어야 한다.
4.2 알고리즘과 자료구조의 관계
주어진 문제에서 수행될 연산작업의 유형을 고찰하고 이러한 작업들이 효과적으로 수행될 수 있도록 자료를 표현
예) 이름 Ai와 전화 번호 Bj가 짝으로 이루어진 리스트
(A1, B1), (A2, B2), (A3, B3), (A4, B4), (A5, B5)
사람으름으로 전화번호를 검색하기 위해서 데이타가 정렬되어 있으면 효율적으로 처리될수 있음.
데이타가 정절되지 않으면 검색이 불가능함.
자료에 대한 기본 연산
1) 초기화(initialization) : 자료구조를 생성할 때
2) 소멸(destruction) : 생성된 자료를 소멸시키고, 사용했던 기억장소를 다른 목적으로 재사용할 수 있도록 하는 연산
3) 조회(retrieval) : 자료구조에서 원하는 자료를 찾아 이를 보고하는 연산
4) 순회(traversal) : 자료구조의 각 자료 원소를 한번만 방문하면서 전체 자료를 처리
5) 삽입(insertion) : 자료구조에서새로운 자료 원소를 삽입
6) 삭제(deletion) : 자료구조에서 기존의 원소 자료를 삭제
7) 탐색(searching) : 자료구조에서 원하는 자료를 찾아내는 연산
8) 정렬(sorting) : 자료구조에서 있는 자료원소를 찾아내는 연산
9) 합병(merging) : 정렬되어 있는 두 개의 자료를 하나로 합병
4.3 알고리즘의 기술방법
1) 자연언어 방법 : 이야기체로 기술, 부정확하고 신뢰성이 결여
2) 흐름도 방법 : 표준 기호를 사용하여 알고리즘의 개개 명령들을 나타내고 이들을 흐름선으로 연결하여 명령들의 순서와
방향을 표현
3) 알고리즘 언어 방법 : 여러 기존 프로그램 언어와 유사한 형태로 기술
알고리즘언어(algorithmic language)는 특별한 형식이 정해진 언어는 아니고 저자가 고안하여 사용
특정언어의 제한성을 피할 수 있고, 자연 언어의 모호성을 배제
4) 특성 프로그램 언어 방법 : 특정 프로그램 언어로 알고리즘을 직접 기술
　
5. 프로그램의 기본 제어 구조
제어구조의 기본 4가지
1) 순차구조(sequence structure) : 명령문이 나열된 순서로 하나씩 순차적으로 수행
2)선택구조 (selection/decision structure) : 선택 조건을 검사하여 그 결과에 따라 명령문을 선택하여 수행 (if, switch)
3) 반복구조 (repetiton, itrition, loop structure) : 반복 조건에 따라 명령문을 반복 수행 ( while, for, do-while)
4) 건너뜀 구조(jump structure) : 프로그램의 흐름을 도중에서 건너뜀(goto, break, continue)
　
프로그램 제어 구조은 입구(entry point)와 출구(exit point)가 하나여야함.
　
5.2 선택구조
(1) if 구조
그림 1.5-3 대안이 다수일 경우의 예
[방법 1] (if-else)
if (sales < 500)
commission = 0.02 * sales;
else {
if (sales < 5000)
commission = 0.05 * sales;
else
commission = 0.08 * sales;
}
[방법 2] (if-if)
if (sales >= 500) {
if (sales < 5000)
commission = 0.05 * sales;
else
commission = 0.08 * sales;
} else
commission = 0.02 * sales;
[방법 3] (if-else if)
if (sales < 500)
commission = 0.02 * sales;
else if (sales < 5000)
commission = 0.05 * sales;
else
commission = 0.08 * sales;
위 세방법중에 방법 3이 프로그램을 앍고 이해하기 쉬움.

　
(2)switch 구조
조건의 값을 검사한 후 case 레이블 중 하나를 선택하여 수행
조건은 정수형 또는 정수형으로 변환되는 자료형이어야함
if-else if 구조는 서택조건에 여러 변수의 다양한 조건식이 가능
다중선택일 경우 switch 문을 사용하면 프로그램이 단순
　
5.3 반복구조
(1) while구조
반복횟수를 알지 못할 경우 사용
반복조건의 검사가 반복되는 명령문 집단보다 먼저 실행
- 반복 명령문이 한번도 실행되지 않을수 있다.
반복조건에 포함된 반복제어 변수는 반복제어문을 수행하기 전에 초기화되어야함.
int ch:
ch = cint.get();
while (ch != EOF) {
if(ch >= '0' && ch <= '9') {
cout << "숫자임 \n";
} else {
cout << "숫자가 아님\n";
}
ch = cin.get();
}
위의 프로그램의 중복부분을 제거하면
int ch:
ch = cint.get();
while ((ch = cin.get()) != EOF) {
if(ch >= '0' && ch <= '9')
cout << "숫자임 \n";
else
cout << "숫자가 아님\n";
}
(2) for 구조
while 문과 달리 반복 구조를 제어하는 모든 정보를 한곳에 모아둠으로써 반복 구조를 간결하게 함.
// 문자열 f_string의 문자 순서를 뒤바꾸어서 문자열 r_string을 만듬 //
void str_reverse(char* f_string, char* r_string) {
int i, j;
for(i = 0, j = strlen(f_string) -1; j >= 0; j--, i++)
r_string[i] = f_string[j];
r_string[i] = '\0';
}
　
for문의 초기화에 여러개의 식을 사용하는 것은 프로그램을 어렵게함.
　
(3) do-while구조
do-while구조는 while 구조와는 달리 명령문 집단을 적어도 한 번 실행
　
(4) 반복 제어구조의 비교
for가 세 구조중에 가장 분명한 구조이므로 가장 먼저 고려
반복 실행하기전에 반복 조건을 검사해야한다면 while 구조
　
5.4 건너뜀구조
사용하는 제어구조 : goto, break, continue
프로그램의 작성, 이해, 수정을 쉽게 하기 위해서는 건너뜀 제어 구조를 가능한 한 사용하지 않아야한다.
goto 문 : 제한 없이 사용
break 문 : 반복문과 switch문에 사용
continue문 : 반복 구조에 사용
break, continue문은 건너 뛰는 곳이 제한적이므로 goto문 보다는 문제가 적다.
　
(1) break문
반복문과 switch문을 완전히 빠져나올때 사용 (그림 1.5-9 참조)
while 구조에서 break를 제거
while (more_to_do) {
명령문 집단 1
if(조건) break;
명령문 집단 2
} while (more_to_do) {
명령문 집단 1
if(!조건) {
명령문 집단 2
} else {
more_to_do= no
}
}
(2) continue문
반복구조에서만 사용하며, 반복 구조를 완전히 빠져 나오는 것이 아니라 현재 반복 중인 것만 중단하고 다음 반복 순서로 계속
continue문은 if문으로 대치하고 사용하지 않는 것이 바람직
예) 문자열 s[i]에서 공백이 나오면 다음 문자를 처리하기 위해 다음 순서로 건너뜀
for문 속의 continue를 제거
for (i=0;s[i] != '\0'; i++) {
if(isspace(s[i])) {
continue;
} else {
s[i]의 문자를 처리
}
} for (i=0;s[i] != '\0'; i++) {
if(!isspace(s[i])) {
s[i]의 문자를 처리
}
}
while문 속의 continue를 제거
while (more_to_do) {
명령문 집단 1
if(조건) continue;
명령문 집단 2
} while (more_to_do) {
명령문 집단 1
if(!조건) {
명령문 집단 2
}
}
(3) goto 문
사용하지 말아야 할 제어 구조
goto 문을 do_while 구조로 대치
start:
명령문 집단;
cout << "계속하시겠습니까? (Y,N)";
if (getchar() == 'Y') goto start; do {
명령문 집단;
cout << "계속하시겠습니까? (Y, N)";
} while (getchar() == 'Y');
goto 문을 continue로 대치
while (조건1) {
명령문 집단 1
if(조건2) goto end;
명령문 집단 2;
end:
} while (조건1) {
명령문 집단 1
if(조건2) continue;
명령문 집단 2
}
goto 문을 break로 대치
　
while (조건1) {
명령문 집단 1
if(조건2) goto out;
명령문 집단 2
}
out: while (조건1) {
명령문 집단 1
if(조건2) break;
명령문 집단 2
}
}
goto 문이 바람직하지 못한 이유
1) goto 문의 역할과 건너뛰어 가는 곳의 라벨(label)의 역활이 무엇인지 알기힘듬
반복구조, 선택구조 탈출중 어느것인지?
2)한 레벨로 향하는 여러 goto문이 존재
프로그램을 해석하기 곤란
　
goto 문이 유용한 경우
중첩된 반복구조에서 탈출하기 위함.
　
6. 순환 구조
　
순환 함수(recursive function) : 어떤함수가 자기자신을 직접 호출 할 때의 함수
Factorial 함수
Factorial 함수
n! = 1
n*(n-1)! n = 0 일 때
n > 0 일때
n!을 (n-1)!를 이용하여 정의 하였으므로 이 함수는 순환 적으로 정의됨
3!계산 절차
3! = 3*(2!) = 3*(2*(1!)) = 3*(2*(1*(0!)))
3*(2*(1*(1))) = 3*2*1 = 6
순환함수가 무한정 수행되지 않기 위해서 다음 2가지 성질을 가져야함.(well-defined 함수)
1) 자신을 호출하지 않고 함수의 값이 정의되는 경우가 있어야함.
(base case 정의, 위의 예에서 n=0 인 경우)
2) 자신을 호출할 때 전달하는 인자는 현재 주어진 인자보다 작아하며, 호출할 때마다 base case에 가까워져야한다.)
　
Factorial 계산 프로그램
　
int factorial_recursive(int n) {
if (n==0)
return 1:
else
return ( n * factorial_recursive(n - 1) );
}
　
꼬리 순환(tail recursion) : 순환함수의 마지막 명령문이 순환 호출
- for, while 구조를사용하여 동등한 반복함수로 변환

Factorial 순환함수를 반복함수로 변환
int factorial_recursive(int n) {
if (n==0) {
return 1:
} else {
facto = 1;
for (int i = 1; i <= n; i++)
facto *= i;
return facto ;
}
}
Fibonacci 수열
0 n=1 일 때
F(n) = 1 n=2 일 때
F(n-1)+F(n-2) n>2 일 때
　
Fibonacci 함수는 잘 정의된(well-defined) 함수 이다 그 이유는 ?
- n=1, n=2 일때 자신을 호출하지 않고 함수 값이 주어지며, F(n)은 n 보다 적을 값으로 정의되고 , 호출될 때마다 n=1에 가까워짐.
　

　
Fibonacci 수열 프로그램
　
int fibonacci (int n) {
if (n==1)
return 0;
if (n==2)
return 1;
else
return (fibonacci(n-1) + fibonacci(n-2));
}
　
위의 순환 함수는 비효율적임
- F(n)을계산하기 위해 F(n-1)은 한번, F(n-2)은 두번, F(n-3)은 세번, F(n-4)은 다섯번, F(n-5)는 여덟번 중복 호출.
　
Fibonacci 수열을 반복함수로 프로그램
int fibonacci (int n) {
int i, lasr, next_to_last, answer;
if (n==1) return 0;
if (n==1) return 0;
next_to_last = 0;
last = 1;
for ( i=3; i < = n; i++) {
answer = last + next_to_last;
next_to_last = last
last = answer;
}
return answer;
}
위의 방법보다도 더 좋은 것은 분석적으로 구하는 것

　
프로그램 언어에 따라 순환구조를 허용하는 것과 허용 하지 않는 것이 있음.
순환 구조 처리에는 상당히 보조 작업이 필요함으로 무분별하게 사용 하면 비효율적인 프로그램이 된다.
순환 절차는 매우 간결한 구조이며, 순환적으로 저의된 알고리즘을 그대로 반영 할 수 있음.
　
제 2장
프로그램 작성
1. 프로그램 작성 기법
좋은 프로그램
프로그램의 질
- 신뢰성(reliability)
- 유지보수 용의(maintainability)
- 이해 용의성(comprehensibility)
재 사용의 용의성
프로그램 작성 기법
(1) 구조화 프로그램 작성 기법(structured programming)
(2) 객체 지향 프로그램 작성 기법(object-oriented programming)
구조화 프로그램 작성 기법으로 작성한 프로그램은 재 사용하기가 어렵다.
1.1 구조화 프로그램 작성
1) goto 문 없는 프로그램 작성(goto-less programming)
- 프로그램의 흐름을 간단 명료하게 한다.
- 그림 2.1-4 비 구조화된 흐름도를 구조화 하는 과정

2) 모듈화 프로그램 작성(modular programming)
- 모듈(module)이란 특정 작업을 수행하기 위해 작성된 명령의 집단인데,
일반적으로 하나의 제한된 기능을 갖는 최하위 수준의 프로그램 단위
- C++에서의 함수 단위, 다른언어에서는 subprogram
- 프로그램을 모듈화할 때, 모듈이 가져야할 조건
(1) 한 개의 입구와 한 개의 출구를 가지며, 지정된 기능을 수행하고 그 자체적으로도 완비되어야 함.
(2) 다른 모듈과 독립 적이어야 함
모듈간의 결합도가 낮아져(low-coupling)야 한 모듈을 다른 모듈과 무관하게 설계하고 수정할 수 있음.
한 모듈에서 발생한 오류가 다른 모듈에 영향을 주지 않음.
전역 변수의 사용은 억제
(3) 프로그램 작성자가 읽고 수정하기 힘들지 않아야 함.
- 모듈화 프로그램의 이점
(1) 모듈단위의 작고 독립적인 문제에 대한 프로그램이 가능하므로 프로그램 작성이 용의
큰 프로그램을 여러 사람이 모듈단위로 프로그래밍이 가능
(2) 모듈은 독립 적이므로 프로그램의 수정이나 삭제, 첨가 등의 작업이 독립적으로 수행
(3) 프로그램이 작은 단위로 구성되어 판독하기가 쉬움.
(4) 모듈은 기능이 제한되므로 오류 발생이 적어짐
(5) 같은 종류의 연산을 모듈화 시킴으로써 중복되는 프로그램을 제거.
- 프로그램이 작으면 이해하기가 쉬워진다.

3) 하향식 프로그램 작성(top-down programming)
- 전체 문제를 하나의 처리과정으로 간주하여 이로부터 하위 수준의 구조로 분할
그림 2.1-5 하향식으로 프로그램을 작성 하는 과정
- 주어진 문제를 작은 문제로 분할하여 최종적으로 모듈단위로 개발
1.2 객체 지향 프로그램 작성
- 프로그램 작성의 생산성을 향상시키기 위한 기법.
- 구조화 기법에서는 모듈이 함수 중심이고, 자료는 함수에서 사용된다는 부차적인 역활.
- 객체지향 기법에서 모듈은 자료 중심이고 함수는 이 자료를 사용한다는 부차적인 역활.
- 자료를 모듈 중심으로 하고, 이자료와 그 외 프로그램간의 상호 작용을 처리해줄 함수를 이 자료에 붙여서 한 구조로 만든 것이 클래스(class)
- 자료를 중심으로 모듈을 만들어 두면 주어진 문제에 따라서 이들을 구성품으로 사용하여 프로그램을 구축해 갈수 있기 때문에 기존 모듈을 더 쉽게 재사용이 가능
- 객체지향 기법은 자료 중심의 모듈을 먼저 만들고, 이를 상향식(button-up) 프로그램 방법으로 프로그램을 작성함.
　
구조화 기법 프로그래밍
// namecard.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"

struct namecard
{
char *name;
char *address;
};

namecard adddata(char *name, char *address)
{
namecard person;
person.name=name;
person.address=address;
return person;
}

char *getname(namecard person)
{
return person.name;
}

char *getaddress(namecard person)
{
return person.address;
}

void main(int argc, char* argv[])
{
namecard person;
person = adddata("김정홍 ", "상주대학교 컴퓨터공학과");
cout << "이름 : " << getname(person) ;
cout << " 주소 : " << getaddress(person) << "\n";
}
객체지향 기법 프로그래밍
// class_namecard.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "stdafx.h"
#include "iostream.h"

class namecard
{
protected:
char *name; // 이름 멤버
char *address; // 주소 멤버
public:
void adddata(char *namedata, char *addressdata);
char *getname();
char *getaddress();
};

// 이름과 주소를 넣는 멤버 함수
void namecard::adddata(char *namedata, char *addressdata)
{
name=namedata;
address=addressdata;
}

// 이름을 얻는 함수
char* namecard::getname()
{
return name;
}

// 주소를 얻는 함수
char* namecard::getaddress()
{
return address;
}

void main(int argc, char* argv[])
{
namecard person;
person.adddata("김정홍 ", "상주대학교 컴퓨터공학과");
cout << "이름 : " << person.getname() ;
cout << " 주소 : " << person.getaddress() << "\n";
}
2. 프로그램의 외형
2.1 기본 개념
(1) 읽기쉽고 이해하기 쉽도록 단순하게 프로그램해야 한다.
- goto 문을 사용하지 않고, 모듈단위 프로그래밍
(2) 소요 계산시간이 짧도록 프로그램(효율이 외형때문에 희생될수도 있음)
(3) 프로그램의 외형이 일관성있게 유지
(4) C++로 작성한 프로그램이 C보다 되형이나 효율이 더 좋다.
2.2 세부 지침
1) 명칭
2) 설명문
3) 들여쓰기
4) 괄호의 위치
5) 명령문)
6) 띄워쓰기
7) 빈줄 삽입
8) 반복 구조
9) if 구조
10) 비교연산
11) 전역변수
- 함수간에 자료를 전달할 때 전역변수를 사용하면 주소를 직접 찾게 되므로 실행 시간이 빠르고, 공동의 기억장소를 사용함으로 기억장소를 줄일 수 있음.
- 프로그램을 읽고 이해하는데 어렵고, 프로그램간의 독립성을 유지하기 힘듬.
- 전역변수를 사용하지 않는게 바람직 함.
12) 함수
2.3 C와 C++ 외형

- C++의 이점을 살리기 위해 버려야할 C 프로그램 관례
3. 프로그램의 오류 수정 방법

프로그램에 있는 오류를 bug라 함.
프로그램에 있는 오류를 찾아서 제거 하는 작업을 오류 수정(debugging)

프로그램의 오류
1) 구문오류 (syntax error) : 작성된 프로그램이 컴퓨터 언어의 규칙에 어긋날 때 나타나는 오류
컴파일 시간에 진단되어 메세지로 인쇄
2) 논리 오류 (logic error) : 성공적으로 컴파일된 프로그램이 실시될 때 나타나는 오류
논리 오류를 수정하는 방법
- 시각적으로
프로그램 작성자가 손과 눈으로 프로그램을 추적
- 출력문 사용
- debugger 사용
오류 수정 컴파일러(debugger)를 사용
debugger를 사용하여 프로그램을 원하는 곳에서 중단하여 변수 값 및 상수 값을 출력해 볼 수 있으며,
그 값을 변경시킬수도 있다.
　　
제 3장 프로그램의 효율성
- 프로그램의 계산 시간을 빠르게 하도록 원시프로그램(source program)과 목적 프로그램(object program)을 생산
1. 기본 개념
프로그램의 효율성
- 프로그램의 계산속도 향상
- 실시간 처리에서 문제
2. 프로그램의 계산시간 측정
2.1 측정 방법
프로그램의 효율성을 측정하기 위해 프로그램의 실행시간을 측정(cpu 사용시간)
- 표준 라이브러리 함수 clock(), time()
- time() 인 경우 내장 자료형은 time_t, 초 단위
- clock() 인 경우 내장 자료형은 clock_t, 컴퓨터의 내부 클럭, 컴퓨터에 따라 다름.
프로그램의 실행시간을 가지고 효율적인 프로그램을 판단하기 힘든 이유
1) 컴퓨터의 측정 시간 단위 10 -3 인데 비해 한 개의 명령어 수핸 시간은 10 -7 초이다.
2) 사용 컴퓨터의 CPU 처리 속도에 따라 실행 시간이 달라짐
3) 같은 컴퓨터라 할지라도 컴퓨터를 사용하는 사용자의 수에 따라 실행 시간이 달라짐
2.2 측정의 예
연산(표 3.2-1)
- 계산 시간은 자료형에 따라 연산 시간이 다름 ( 정수형 < 부동소수점형)
- 같은 자료형도 연산 종류에 따라 연산 시간이 다름(+, - < * /)
- 주소 연산자와 구조체 멤버 연산은 시간이 소요 되지 않는다.
- 컴퓨터에 따라 연산 시간이 다름
- register 사용하면 속도 향상
배열
- 2차원 배열 보다도 1차원 배열을 사용하거나 포인터 사용은 계산 시간을 단축 (page 64)
2.3 profiler 사용
프로그램 계산 시간의 90 %는 전체 프로그램의 10% 내에서 소비
profiler는 프로그램의 실행시간을 분석해주는 도구 (page 67)
3. 프로그램의 효율화 방법
1) 빠른 기계사용
2) 프로그램의 최적화
- 효율적인 알고리즘과 자료구조 사용
- 최적으로 효율화 해주는 최적화 컴파일러(optimization compiler) 사용
- 원시 프로그램의 개개 연산의 효율화 작업(code tuning)
(1) 효율적인 알고리즘과 자료구조 사용
- 효율적인 알고리즘과 자료구조 선택이 개개 연산을 최적화 하는 것보다 프로그램의 성능에 더많은 영향을 줌.
- 프로그램 성능을 향상 시키기 위해서 가장 중요함.
- 모든 문제에 향상 최선인 하나의 자료구조와 알고리즘이 있을수 없다.
(2) 최적화 컴파일러(optimization compiler) 사용
- 원시 프로그램의 연산을 더 빠른 연산으로 대치
- 원시 프로그램의 연산을 기억장소 사용량이 더 적은 연산으로 대치하여 컴파일
- 컴파일 시간이 오래 걸림.
(3) 원시 프로그램의 개개 연산의 효율화 작업
- 프로그램 작성자가 최적화
자료형
- 자료형을 혼합하여 사용하지 않도록 함.
float y;
int j;
if(y==4) j==10.0; => if(y==4.0) j==10
register
- 자주 사용되는 변수는 고속 기억장소인 register에 지정

변수
- 필요없는 변수는 제거
- 한번만 사용하는 변수는 제거
ii = i + 1
rr = r[ii] * t => area = pi * r[i+1} * t
area = pi * rr
- 임시 변수를 사용하지 않고 직접 표현
t1 = b + c
t2 = d * e => a = b + c + d * e
a = t1 + t2

　
초기화
- 자주 사용되는 상수는 미리 계산하여 초기화
factorial 계산시
const NUM = 6;
int factorial(int n) {
static precalcu[NUM] = {1, 1, 2, 6, 24, 120};
if ( n < NUM )
return precalcu[n];
else
return n * factorial(n -1);
}
연산
- 느린 연산은 빠른 연산으로 대치
(프로그램이 부자연스러워져 읽기가 어려워짐)
3 * i => i + i + i (i 가 실수이면 i + i + i 은 3 * i 보다 부정확 )
a = b / c / d / e => a = b /( c * d * e)
x = a / 5 => x * 0.2

- 2를 곱할 때 left shift 를 사용하는 것이 효과
a *= 2 => a <<= 1
i = j * 4 => i = j << 2
- 결합 연산자는 효과적으로 처리되므로 가능한한 이를 사용(일반 연산자를 사용하면 두번 연산)
i = i + 2 => i +=2
- 증가 연산자는 지정 연산자 보다 빠름
i += 1 => i ++
- 논리 연산자는 평가횟수를 줄일수 있도록 피연산자를 나열
&& 연산에서는 참이될 가능성이 낮은 것을 첫 피연산자로 하고,
|| 연산에서는 참이될 가능성이 높은 것을 첫 피연산자로 함
예) (a == 0) 의 가능성이 (b == 0)의 가능성 보다 높음.
if ((b == 0) && (a == 0))
if ((a == 0) || (b == 0))
while ((b == 0) && (a == 0))
while ((a == 0) || (a == 0))
- 인수분해하여 곱셉의 개수를 줄임
a = b * (e + f) - c * (e + f) + d * (e + f) => a = (b - c + d) * (e + f)
- 상수가 어떻게 산출되었는지를 보이기 위한 연산식은 제거 상수를 사용
float perim = 2 * 4.1 + 2 * 10.1 => float perim = 28.4 // 2 * 4.1 + 2 * 10.1
- 자주 사용되는 부 연산식은 제거
x = a[2 * i + J][2 * i + J] => temp = 2 * i + j;
x = a[temp][temp]

배열
- 가능하면 배열 대신 변수사용
(배열위치와 해당 배열 원소의 위치 계산이 필요)

a[n][n] * b[n][n] => c[n][n]
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
c[i][j] == 0.0;
for (k = 0; k < n ; K++) {
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
} => for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
sum = 0.0
for (k = 0; k < n ; K++) {
sum += a[i][k] * b[k][j];
}
c[i][j] = sum;
}
}

- 다차원 배열을 반복 처리할 때 배열의 저장 방법에 따라 계산 속도가 영향을 받는다.

for (j = 0; j < 100; j++) {
for (i = 0; i < 50; i++) {
a[i][j] = 0;
}
} => for (i = 0; i < 100; i++) {
for (j = 0; j < 50; j++) {
a[i][j] = 0;
}
}
　
반복 구조
- 가장 먼저 최적화 해야 할 부분, 가능한 한 많은 명령문을 반복 구조 밖으로 옮김.
- 반복시 변하지 않는 변수나 수식은 반복 구조 밖으로 옮김

for (i = 0; i < 100; i++)
sum = sum + x * a[i]; => for (i = 0; i < 100; i++)
sum += a[i];
sum = x * sum;

- 반복문의 조건은 반복 될때마다 검사 되므로 조건속의 상수는 반복 구조 밖으로 옮김
for (i = 0; i < strlen(key); i++)
address += word[i]; => length = strlen(key);
for (i = 0; i < length; i++)
address += word[i];

- 여러개의 반복 구조는 하나로 통합.
for (i = 0; i < n; i++)
a[i] = f1[i];
for (i = 0; i < n; i++)
b[i] = f2[i]; => for (i = 0; i < n; i++)
a[i] = f1[i];
b[i] = f2[i];


- 횟수가 적은 반복은 사용하지 않음.
for (i = 0; i < 2; i++)
a[i] = 0; => a[0] = 0;
a[1] = 0;
함수의 호출
- 불필요한 함수호출은 피함.

c = log(a) + log(b); => c = log(a * b);

- 일반함수보다는 특별한 경우를 위한 함수가 효율적.
if (i < j)
small = i;
else
small = j; => small = min(i, j);

- 내장함수 사용이 직접 프로그램 하는 것보다 효율적임.
if (i < j)
small = i;
else
small = j; => small = min(i, j);
if ('a' <= c && c <= 'z') => if (islower(c))

inline 함수
- 함수는 함수를 호출하고 인수가 전달될때 계산 시간이 소요.
짧은 함수를 inline함수화함으로써 호출시간을 줄임, 그러나 프로그램의 길이가 길어짐.
- inline 문을 사용하여 필요때 마다 사용
#include ..
inline int min(int x, int y) {
return x < y ? x : y;
}
void main()
{
int x;

z = min(x, y);
}
함수 인자 전달 방법
함수의 인자를 전달하는 방법의 세가지

(a) 값에 의한 전달 (pass by value)
- 새로 생성된 변수에 값을 복사
int x = 1;
int y = 2;
swap_v(x, y);

void swap_v(int a, int b) {
int temp;
temp = a;
a = b;
b = temp;
} // 호출시 x, y 값이 교환 되지 않는다.

x
1


a
1


(b) 포인터에 의한 전달 (pass by pointer)
- 변수의 주소만 새로 생성된 변수에 전달
int x = 1;
int y = 2;
swap_p(&x, &y);

void swap_p(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
주소 : 3100
x
1


pa
3100



(c) 참조자에 의한 전달 (pass by reference)
- 두 변수가 한이름을 가짐
int x = 1;
int y = 2;
swap_r(x, y);

void swap_r(int &a, int &b) {
int temp;
temp = a;
a = b;
b = temp;
}
x 와 a는 동일 함.
x, a
1



- 인수 전달 사용 기준
1) 인자 변수가 함수에 의해 수정되어야 한다면 참조자에 의한 전달
2) 인자 변수가 구조체이면 포인터나 참조자에 의한 인수 전달을 사용
기억장소 처리 시간 절약
3) 변수가 함수에 의해 수정 되지 않아도 된다면 값에 의한 인수 전달을 사용
4) 포인터나 참조자로 인수전달시 변수의 수정을 막고 싶다면, const 사용
int x = 1;
void func_p(const int *a)
void func_r(const int &a)

5) 배열 전체를 값에 의해 전달할 수 없다.
void func(int arr[])

함수의 리턴 자료형
- 리턴되는 자료형은 배열이외에 사용(배열은 struct, class 속에서는 리턴됨)
- 함수가 연산한 결과를 리턴할 필요가 없는 경우, 리턴할 자료형이 void
void function() {
　
return ;
}

- 리턴하는 방법 3가지
void main()
{
int xv = fnc(10);
int * xp = fnp(10); // 오류발생
int xr = fnr(10); // 오류 발생
1) 값을 리턴 (return a value) int fnv(int xx) {
return xx;
}
2) 포인터를 리턴 (return a pointer) int& fnp(int xx) {
return &xx;
}
3) 참조자를 리턴 (return a reference) int& fnr(int xx) {
return xx;
}

리턴하려는 변수가 함수내의 지역변수 일때 참조자나 포인터를 사용하여 주소를 사용하여
리턴하는 것은 위험함.
　
제 4 장 알고리즘의 분석
1. 알고리즘 분석의 필요성
알고리즘 분석의 기준
1) 소요계산 시간(computation time, complexity)
2) 기억장소 사용량(memory space usage, amount of space used)
3) 정확성(correctness)
4) 간결성(simplicity)

소요계산 시간과 기억장소 사용량이 중요한 이유
1) 알고리즘이 필요로하는 컴퓨터의 기억용량과 계산시간의 추정치(estimate)나 최대치(bound)를 알 수 있음
2) 여러개의 알고리즘을 비교하기위한 정량적인 표준으로 적합.
　
2. 계산량
2.1 계산량의 측정 방법
컴퓨터의 실행시간(execution time)을 계산량으로 쓰지 않는 이유
1) 실행시간은 사용하는 컴퓨터 기종에 따라 다름.
2) 프로그램 언어에 따라 다름
3) 실행시간을 측정하기 위하여 프로그램을 작성하고 수정하는 작업에 많은 시간이 소요.
일반적인 알고리즘 계산량 분석
- 알고리즘에서 기본 연산(가장 자주 실행되는 연산)이 실행되는 횟수를 계산
- 기본 연산이 다를경우(곱셈, 덧셈), 각 기본 연산의 실행 횟수에 가중치를 줌으로써 상대적인 계산량을 구함.

문제 기본 연산
명단에서 x를 찾음 명단의 원소와 x의 비교
두개의 행렬의 곱 두수의 곱셈과 덧셈
수치 목록을 오름차순 정렬 목록내의 두 원소의 비교

2.2 계산량의 표현
계산량은 상수로 표현 하지 않는 이유
1) 기본 연산의 횟수가 입력에 따라 좌우됨
- 일반 적으로 입력의 크기는 n으로 표현
- 입력의 크기

문제 입력의 크기
명단에서 x를 찾음 명단애의 원소의 갯수
두개의 행렬의 곱 행렬의 크기
수치 목록을 오름차순 정렬 목록내의 원소의갯수

2) 입력의 크기가 같더라도 입력 상태에 따라 계산량이 틀림.
- 입력이 정렬된 경우와 정렬 되지 않는 경우
평균 계산량(Average complexity) : A(n)
최악의 계산량(worst-case complexity) : W(n)
- 수행할 계산량의 상한치를 제공
- 대부분의 경우 최악의 계산량을 사용
- 알고리즘의 계산량이라고 하면, 최악의 계산량을 뜻함.
최선의 계산량(Best-case complexity) : B(n)
2.3 계산량 계산의 예
[예제 1]
// 배열 원소의 덧셈
sum = 0;
for (i = 0; i < n; i++) {
sum += a[i];
}

(기본연산) 덧셈
(계산량) 덧셈의 횟수는 입력 원소 n에 대하여 A(n) = W(n) = B(n) = n
[예제 2]
// 두 행렬의 곱셈
// 행렬 a와 b를 곱하여 그 결과를 c에 저장함.
for (i = 0; i < n; i++) {
for (j= 0; j < n; j++) {
sum = 0;
for (k = 0; k < n; k++) {
sum += a[i][k] * b[k][j];
}
c[i][j] = sum;
}
}
(기본연산) 곱셈(a[i][k] * b[k][j]) 또는 sum에 더하는 덧셈, 두연산의 실행 횟수는 동일
(계산량) 기본연산의 실행시간은 A(n) = W(n) = B(n) = n3
- 실제로 덧셈이나 곱셈연산보다도 지정연산(assignment operation)이 더 자주 수행됨
- i 에서 n번, j, c에서 n2 번, k 에서 n3 번, sum에서 n2 + n3 번 지정 연산이 수행
- (n + 3n2 + 2n3) 번의 지정연산이 수행, 최고차수는 n3

[예제 3]
// n개의 정수로 된 배열 a에서 x를 순차적으로 탐색함(순차 탐색)
// a[i] = x 이면 i를 리턴, 없으면 -1을 리턴
int sequential_search(int a[], int n, int x) {
int i;
for (i = 0; i < n && a[i] != x; i++)
;
return((i != n) ? i : -1);
}
(기본연산) 배열의 각 원소와 x의 비교
(계산량)
A(n) = (1 + 2 + 3 + .. n)/n = (n + 1)/2
B(n) = 1
W(n) = n
[예제 4]
// xn 을 순환 함수로 계산

int power(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n % 2 == 0)
return (power(x * x, n/2));
else
return (power(x * x, n/2) * x);
}
(기본연산) 곱셈
(계산량)
Xn을 계산하기 위해 소요되는 곱셈의 횟수 T(n)이라면
T(0) = 1
T(1) = 1
T(n) = T(n/2) + 1
= (1+ T((n/2)/2)) + 1
= (1+ (1+ T((n/2)/2)/2)) + 1
= 1 + 1 + 1 + ....
시각적으로 풀어쓰면
T(n) = T(n/2) + 1
T(n/2) = T(n/4) + 1
T(n/4) = T(n/8) + 1

T(2) = T(2/2) + 1
T(1) = 1

T(n)은 자신을 호출할 때마다 n의 값이 반으로 줄어듬, 총 자신의 호출수
n/(2k-1) = 1을 만족하는 k 이다.
k = log2n + 1
T(n) = log2n + 1
A(n) = W(n) = B(n) = log2n + 1
[참고]
int power(int x, int n) {
if ( n == 0)
return 1;
else
return (x * power(x, n-1));
}
x1000을 계산하기 위한 계산량
[예제 4] 에서는 10 의 곱셈 (29 = 512)
[참고] 에서는 1000번 곱셈

2.4 계산량의 차수
기본 연산의 수행횟수를 전체 알고리즘의 수행 계산량으로 간주하는 이유
-> 전체 알고리즘의 수행 계산량이 기본 연산의 수행횟수에 비례
예) 입력 I에 대하여 T(I) 만큼 기본 연산을 수행한다면
-> 전체적인 수행 횟수는 cT(I)
-> 실제 컴퓨터 실행시간은 c'T(I)

f(n)이 어떤 함수 g(n)에 대해 다음이 성립할 때 f(n)은 차수 g(n)이라고 말함

lim (f(n) / g(n)) = 상수 != 0
n->무한대

-> f(n) = O(g(n)) 로 표기 하며, 이 기호를 "big oh"라고 함.
f(n) = 2n5 + 6n4 + 6n2 + 18 은
lim ((2n5 + 6n4 + 6n2 + 18)/n5) = 2 이므로 f(n) = O(n5)
n->무한대
[참고]
n3 + n2 = O(n3)
O(n3) = n3 + n2 으로 표기 할수 없음
[문제]
100n5 = O(n5)
1 + 2 + 3 + 4 + .. + n = n(n + 1)/2 = O(n2)
1024 = O(1)
n + log n = O(n)
차수g(n)(big oh)을 사용하여 알고리즘 표현
- 이 알고리즘의 실행 시간은 g(n)에 비례한다.
- 이 알고리즘의 실행 시간(계산량)은 차수 g(n)이다
- 이 알고리즘의 실행 시간(계산량)은 O(g(n))이다
- 이 알고리즘은 차수 g(n) (혹은 O(g(n))의 알고리즘이다.

알고리즘의 형태
- 지수형 알고리즘(exponential algorithm) : 알고리즘의 실행 시간(계산량)이 지수형으로 표현
대표적인 지수형 알고리즘 : 외판원 문제(한 외판원이 한 도시를 오직 한번만 방문,
n 개 도시를 가장 싸게 방문 하는 방법)
20 의 도시인 경우 (20!의 계산이 필요)
초당 108 개의 연산 처리 컴퓨터라도 700 년이 소요
- 다항식 알고리즘(polynomial algorithm) : 알고리즘의 실행 시간(계산량)이 다항식으로 표현

Big-O 계산량 분석의 한계성
1) 복잡한 알고리즘에서는 분석이 어렵다.
2) 세밀한 측정이 아니므로 작은 차를 반영하지 못함.
3) 자료가 적은 경우 알고리즘의 성능을 반영 하지 못함.
[참고]
표 4.2-1 계산량 함수의 종류
표 4.2-1 계산 시간
표 4.2-1 계산량 함수의 증가율

2.5 알고리즘의 기본 구조의 계산량
단일 명령문
O(1)

명령문 순차구조
O(1)

단일 명령문
O(1)

for 반복문 구조
반복 횟수가 상수이면 O(1)
반복 횟수가 n이면 O(n)

for (i = 1; i <= n; i++) {
for (j = i; j <= i: j++) {
명령문 집단
}
}

전체 반복 횟수 1 + 2 + 3 + .. + n = (n2 + n)/2 = O(n2)
　
while 반복구조

count = 1;
while (count <= n) {
명령문 집단
}

count가 1부터 시작하여 k번 수행 후에는 count = 2k
반복 횟수 k = log2 (count) 이므로 계산량은 O(log2 n)

2.6 실행단계의 계산량 측정
실행되는 명령문의 개수를 세는 방법
counter를 실행문에 삽입.

실행 시간의 측정
정확한 시간측정이 어려움.

프로그램의 실행시간(CPU time)은 컴퓨터가 사용한 전체 시간인 경과시간(elapsed time)과는 구별
3. 기억장소 사용량
기억장소 사용량 분석은 계산량 분석보다 쉽다.
기억장소 사용량과 계산량의 관계는 trade-off (기억장소 사용량을 줄이기 위해 계산량이 증가함)
4. 정확성
복잡한 알고리즘일 경우, 작은 부분으로 분할하여, 각 부분이 모두 정확하다는 것을 증명함으로써 전체 알고리즘이 점확하다는 것을 증명함.
5. 간결성
프로그램의 정확성을 쉽게 증명할 수 있음.
프로그램의 수정 작업을 쉽게 할수 있음.
　　
제 5 장
정수, 실수 문자
　
자료형(data type) : 프로그램에서 별수들이 취할수 있는 값의 형태
자료형의 종류(C++)
Fundamental data type (기본 자료형) : 정수(integer), 실수(real), 문자 (character)
Derived data type (파생자료형) : 배열, 구조체, 포인터, 클래스
컴퓨터 기억장치내의 자료표현
bit : 최소 정보 단위 0 혹은 1의 값
byte : 기억장치내에 자료를 표현하기 위한 bit를 그룹화, 8 bit로 구성
word : byte를 그룹화, 컴퓨터에 따라 16bit, 32 bit, 64 bit로 구성
byte word에는 그 위치를 나타낼수 있는 주소가 부여
정수나 실수를 저장하는 단위는 word, 문자를 저장하는 단위는 byte
1. 정수
2진수에 대한 음수 표현 기법
(1) 부호화 크기 표현
음수와 양수 차이는 단지 부호 bit 뿐이고 절대치는 같다.
부호는 왼쪽 첫번째 bit 에 표현
표현은 간단하지만 두수를 더하거나 빼기위해서는 별도처리
4 bit 만 사용 할경우 : 7 + (-6) = 0111 + 1110 = 11101 : 계산이 틀림.
(2) 1의 보수 표현
전체 비트를 1은 0으로, 0은 1로 바꾼다.
(3) 2의 보수 표현
1의 보수 + 1
오른쪽에서 첫번째 1까지는 그대로 두고 나머지 부분은 1의 보수를 취한다.
1 byte로 -11 을 표현하면
부호화 크기 1000 1011
1의 보수 1111 0100
2의 보수 1111 0101
1 byte로 0의 표현
표현 방법 +0 -0
부호화 크기 0000 0000 1000 0000
1의 보수 0000 0000 1111 1111
2의 보수 0000 0000 없음
k bit 로 표현할수 있는 수의 크기
표현 방법 음수 양수
부호화 크기 -(2k-1 -1) 2k-1 -1
1의 보수 -(2k-1 -1) 2k-1 -1
2의 보수 -2k-1 2k-1 -1

컴퓨터에서 자료형의 크키
char : 1 byte
short : 2 byte
int : 컴퓨터의 word 크기 사용
long : 4 byte 사용
2. 실수
실수 : 소수점이 있는 수

0.0000000000832 = 0.832*10-10 (부동소수점 표현)
.832 : 가수(mentissa, fraction)
-10 : 지수(exponent)
10 : 지수의 기수 (base)

부동 소수점 표현
전체 부호 가수 지수 부호 지수
지수 부분에 부호를 제거 : exceed-64 방식
지수부분을 전체로 양수로하고 64를 양수 0으로 중가되는 수(65, 66, 67, ..) 에 따라 지수가 +1, +2, +3
감소되는 수(63, 62, 62 .. ) 에 따라 지수가 -1, -2, -3
전체 부호 지수 가수
1 bit 7 bit 28 bit
　
0.01010*2-1 을 정규화된 부동 소수으로 표현 ?
0.1010*2-2
지수 부분을 exceed-64 방식으로 표현 하면 : 2-2 = 62
0 0111110 1010000 ..... 0
C++에는 float, double, long double의 세 종류의 실수형
자료형 byte 수
float 4
double 8
long double 10
　
3. 문자
문자가 기억자소에 저장되는 단위는 byte(8 bit)
문자를 이진수로 표현하기 위한 방법
1) ASCII(American Standard Code for Information Interchange : 아스키) : 대부분의 컴퓨터가 사용
2) EBCDIC(Extended Binary Coded Decimal Interchange Code : 엡시딕) : IBM 대형 기종
한글의 표현
조합형

ㄱ + ㅏ + ㄱ = 각
완성형
가나다순으로 완성된 하나의 음절을 14비트로 코드화
2350자로 한정

배열, 구조체, 포인터
배렬, 구조체, 포인터 : 기본자료형에서 유도된 자료형으로 파생된 자료형(drived type)
배열과 구조체는 서로 관련있는 자료들을 집단화한 자료구조로 복합 자료구조(composite, structured)라고도함.
배열 : 같은 자료형의 자료들만 구성
구조체 : 배열이나 구조체를 포함하여 여러가지 자료형이 섞여서 구성
1. 배열
1.1 배열의 정의
일차원 배열
　 　 a[i] 　 　 　
배열 a의 가장 작은 첨자 L, 가장 큰 값을 U로 표시하면
일차원 배열은 A[L..U]로 표시
L : lower bound
U : upper bound
배열의 크기: 원소의 개수
a[L..U] 배열의 원소 크기 : U-L+1
C++에서 a[M] 이라 선언하면 M은 이 배열의 크기 (즉 , a[0..M-1] )
하한치가 0 인것을 : zero-orgin, zero-offset

다차원 배열

0 1 n-1
0
1
b[i][j]
m-1
b[L1..U1][L2..U2]의 원소 갯수 :
행의 수 : U1- L1 + 1
열의 수 : U2- L2 + 1
원소 갯수 : (U1- L1 + 1) * (U2- L2 + 1)
C++ 에서 배열 array[10][10]의 원소 개수 : 10*10
1.2 배열의 저장 방법
(1) 일차원 배열의 저장 방법
기억장소에 저장되는 물리적인 순서를 논리적 순서와 같도록 저장
원소 a[i+1]의 저장 장소가 a[i] 저장 장소에 바로 인접
a[0] a[1] a[2] a[3] a[4] 　
　 　 　 　 　 각 원소에 S
a a+3S 　 　 　 Byte 를 할당
배열의 주소를 계산하기 위해서 알아야 할 사항
1) 배열 a에 할당된 저장장소가 시작되는 주소 (base address)
2) 각 원소의 크기
(2) 다차원 배열의 저장방법
선형적 형태로 구성하는 방법

이차원 배열
- 행우선 순서 (row major order) 방법 : C++, COBOL, Pascal
- 열우선 순서 (column major order) 방법 : Fortran

　 　 　 　 행우선
　 　 　 　 　
　 　 　 　 　
열우선 　 　 　 　
이차원 배열 A[1..m, 1..n] 으로 구성된 배열에서 A[1,1]의 주소를 Base address라 한다면
가) 행 우선 순서 배열에서 원소 A[i, j]의 주소
Base address + (i -1)n + (j-1)
나) 열 우선 순서 배열에서 원소 A[i, j]의 주소
Base address + (j -1)m + (i-1)
삼차원이상에서
첫번째 첨자 기준으로 정렬하면 행 우선 순서 배열
마지막 첨자 기준으로 정렬하면 열 우선 순서 배열
3차원 배열
A[1..U1][1..U2][1..U3]에서 A[1,1,1]의 주소를 Base address라 한다면
가) 행 우선 순서 배열에서 원소 A[i, j,k]의 주소
A[i,1,1] 의 주소 : Base address + (i-1)*U2*U3
A[i,j,1] 의 주소 : Base address + (i-1)*U2*U3 + (j-1)*U3
A[i,j,k] 의 주소 : Base address + (i-1)*U2*U3 + (j-1)*U3 + (k-1)

나) 열 우선 순서 배열에서 원소 A[i, j,k]의 주소
A[1,1,k] 의 주소 : Base address + (k-1)*U1*U2
A[1,j,k] 의 주소 : Base address + (k-1)*U1*U2 + (j-1)*U1
A[i,j,k] 의 주소 : Base address + (k-1)*U1*U2 + (j-1)*U1 + (i-1)
1.3 배열의 연산
순회
배열의 저장순서를 고려하여 인접한 원소를 차례로 처리하는 것이 효율적임.
삽입. 삭제
삽입/삽제될 원소가 배열의 중간이라면 이 위치 이후의 원소를 모두 이동
삽입/삭제 연산의 횟수가 많다면 배열은 효율적인 자료 구조가아님.
　
1.4 희소 배열(sparse array)
희소 배열 배열의 원소값이 0인 원소가 비교적 많은 배열
희소 배열을 표현하기 위해서 배열 값이 0이 아닌 원소만 저장하는 방법이 필요
하나의 원소를 표현하기 위해 원소값과 배열의 위치 값인 인덱스를 함께 2차원 배열로 표현
　 　 13 　 27 　 　 　
　 　 　 　 　 8 31 　
　 　 　 　 2 　 　 　
　 　 　 　 　 　 　 　
　 15 73 　 　 　 　 　
　 　 　 　 　 　 　 　
　 　 　 　 　 32 　 　
　 　 14 　 　 　 　 　
　 　 　 　 　 47 　 　
희소 배열의 다른 방법 표현
행 번호 열 번호 원소값
0 0 1 13
1 0 3 27
2 1 4 8
3 1 5 31
4 2 3 2
5 4 0 15
6 4 1 73
7 6 4 32
8 7 1 14
9 8 4 47
위의 표현은 배열에 0이 아닌 원소를 새로이 첨가하거나, 0 이 아닌 원소를 0의 값으로 수정하면 원소의 순서까지도 수정해야함.
　
2. 구조체
2.1 구조체의 정의
논리적으로 서로 관련된 자료들을 집단화한 자료구조
구조체의 원소를 멤버(member)라 하고, 멤버는 이름을 사용하여 식별
구조체와 멤버를 레코드(record)와 필드(field)라 부름.
C++ 로 프로그램한 사원급여 구조체 employee의 지정문(specifier)
struct employee {
char name[20];
float salary;
int dependent;
int number;
}
　
employeer 구조체 표현 name salary dependent number
특정 레코드 표현 J.hong 350000 3 1234
구조체 지정문 : 구조체를 구성하는 원소들의 종류와 그 자료형을 규정
사용자 정의 자료형을 생성

새로운 자료형을 갖는 변수 생성
employee manager;
employee emp[100]
사용자 정의 자료형의 자료를 변수 대신 특별히 객체(object)라도 구별하여 부르기도 함.
　
2.2 구조체 저장 방법
구조체의 첫 맴버가 첫 위치에 저장되고, 마지막 멤버가 마지막 위치에 저장
　
3. 포인터
3.1 포인터 정의
기억장소의 모든 byte에는 주소가 있음
640 KByte 의 기억장소를 갖는 시스템 :
가장 높은 주소 640 * 1024 = 655,359
1 MByte 의 기억장소를 갖는 시스템 :
가장 높은 주소 1024 * 1024 = 1,048,575
포인터 변수의 선언
* 를 사용
int * p;

포인터 변수의 초기화
p = & x
& 는 address of 라고 읽음.
포인터에 0 또는 NULL을 지정하면 (p = NULL;)
포인터가 아무 것도 가르키지 않음.
3.2 포인터와 배열
배열 a[ ] 에서 괄호 없이 사용한 배열 이름 a 는 배열의 시작주소( &a[0])
a 는 a[0]를 가르키는 포인터
a가 주소 값이므로 a는 변수가 아니고 상수
- prt = a 는 옳은 표현, ptr = &a 는 옳지 않음.
　
ptr이 포인터 변수 이고 i가 정수 이면
- ptr + i는 ptr 로 부터 i 단위크기(cell) 만큼 떨어진 주소
- ptr[i] *(ptr + i) 는 같은 의미
예) ptr이 가르키는 값이 정수이면
ptr + 3 은 ptr로 부터 6 byte를 더해야함.
3.3 동적 기억장소 할당.
동적 기억장소 할당 : 실행시간에 기억장소를 할당
C에서는 malloc()를 사용, C++에서는 new라는 연산자 사용
배열을 정적으로 선언하려면 그 크기를 미리 지정해야함.
동적으로 기억장소 할당의 예
int * p_array;
cin >> array_size;
p_array = new int[array_size]

cin >> array_size;
int a[array_size] // 잘못된 프로그램
　
동적 구조체의 멤버를 접근할 때에는 구조체 이름이 없으므로, 정적 구조체에서처럼 구조체 이름에 점(.)을 사용할 수 없다.
C++ 에서는 화살표 멤버 연산자 (->)를 사용하여 접근
emplyee *emp;
p = new emplyee[10] // employee 객체 10개를 할당
자유 저장장소(free store) : 실행되고 있는 프로그램에서 동적 기억 장소가 자유롭게 할당되고 회수 되는 기억장소 영역
delete 연산자
new로 할당받은 기억장소가 프로그램에서 후에 불필요하게 되면 다른 곳에서 사용할수
있도록 자유저장장소로 되돌려 주기위한 연산.
delete 연산은 포인터 자체를 제거 하는 것이 아니라 이들이 가르키는 기억장소를 해제
delete [ ] p; //new에서 [ ]를 사용하면 delete에서도 [ ] 사용
쓰레기(garbage)
포인터가 가르키고 있는 원래 할당된 기억장소가 불필요하게 되었을 때,
이를 delete하지 않고 다시 새 기억장소를 가리키게 하면 우너래 할당된 기억장소는 다시
사용할수 없게 됨. 이를 쓰레기라고 함.
쓰레기 수거 (garbage collection)
사용할 수 없게 되어버린 기억 장소를 회수
　1. 정렬
1.1 선택 정렬
1.2 삽입정렬
정렬되지 않은 리스트의 한 원소씩을 정렬된 리스트에 제 위치를 찾아 삽입
카드를 한 장씩 돌려받을 때 손에 이미 정렬되어 있는 카드 속에 새 카드를 삽입하는 방법
정렬 되지
않은 배열 Pass 번호 정렬된
배열
1 2 3 4 5 6 7 8
77
33
44
11
88
22
66
55 77 33
77 33
44
77 11
33
44
77 11
33
44
77
88 11
22
33
44
77
88 11
22
33
44
66
77
88 11
22
33
44
55
66
77
88 11
22
33
44
55
66
77
88
　
//삽입정렬(insertion_sort)
void insertion_sort(int a[], int n)
int pass, i;
int temp;
for (pass = 2; pass <= n; pass++) { // 두번째 항목 부터 정렬
temp = a[pass - 1];
for(i = pass -2; i >= 0 && a[i] > temp; i--) { // i >= 0 : 비교할 항목이 있음,
// a[i] > temp 비교 항목보다 현재 값이 더큼.
a[i + 1] = a[i]
}
a[i + 1] = temp
}
}
전체 비교 횟수 : 1 + 2 + 3 + ... + (n - 1) = n(n-1)/2
수행 시간 : O(n2)
최선의 경우 : 원래 정렬되어 있는 경우, 전체 비교횟수는 n-1 번
1.3 버블정렬
바로 인접해 있는 두 개의 원소를 비교하여 순서가 바뀌어 있으면 서로 위치를 바꾸어 작은 값의 원소를 배열의 위쪽에 오게 하고 큰값의 원소를 아래쪽으로 가도록 하는 것
각 pass 가 끝나면 큰 값의 원소가 제 위치로 가게됨.
자료 원소들의 움직임은 액체속의 가벼운 기포(bubble)가 위로 올라가고 무거은 것은 아래로 내려오는 움직임과 유사하여 bubble 정렬이라고 부름.

정렬 되지
않은 배열 Pass 번호
1 2 3 4 5
73
65
52
24
83
17
35
96
41
9 65
73 65
52
73 65
52
24
73 65
52
24
73
83 65
52
24
73
17
83 65
52
24
73
17
35
83 65
52
24
73
17
35
83
96 65
52
24
73
17
35
83
41
96 65
52
24
73
17
35
83
41
9
96 52
65 52
24
65 52
24
65
73 52
24
65
17
73 52
24
65
17
35
73 52
24
65
17
35
73 52
24
65
17
35
73
83 52
24
65
17
35
73
41
83 52
24
65
17
35
73
41
9
83 52
24
65
17
35
73
41
9
83
96 　 　 　
전체 비교 횟수 : 1 + 2 + 3 + ... + (n - 1) = n(n-1)/2
수행 시간 : O(n2)
최선의 경우 : 원래 정렬되어 있는 경우, 1 번의 pass로 수행 종료
알고리즘이 수행도중 배열이 완전히 정렬된 상태를 알 수있음. (어떤 패스가 한번의 원소 교환도 없이 종료됨)
한 패스에서 다음 패스로 넘어갈떄 비교해야하는 원소의 수를 하나 이상 줄임으로 정렬 연산의 속도를 개선.
정렬 되지
않은 배열 Pass 번호
1
30
20
50
10
60
70
80
90 20
30
　

교환 20
30
50
　
　
교환 20
30
10
50
　

교환 20
30
10
50
60




20
30
10
50
60
70 20
30
10
50
60
70
80 20
30
10
50
60
70
80
90 65
52
24
73
17
35
83
41
96 65
52
24
73
17
35
83
41
9
96
버블정렬(bubble_sort)
void bubble_sort(int a[], int n) {
int temp;
int last, latest, i;
latest = n-1; //최근에 발생한 교환 위치
do {
last = latest;
for (i = 1; 1 <= last; i++) {
if (a[i - 1] > a[i]) { // 교환할 항목이 발생
latest = i - 1;
temp = a[i - 1];
a[i - 1] = a[i];
a[i] = tgemp;
}
}
}while (latest != last && latgest != 0);
}
// latest == last : 교환이 일어 나지 않음
// latest == 0 : 마지막 교환이 첫번쨰와 두번째 항목에서 발생함.
　
1.4 쉘정렬(shell sort)
버블정렬에서 자료의 위치가 정렬된 위치에서 멀리 떨어져 있다면 여러번 교환이 필요함.
멀리 떨어져 있는 원소끼리 비교 교환하도록 함.
알고리즘의 개요
원래의 자료 리스트를 여러개의 부분 리스트로 그룹화
한 부분 리스트씩 다른 부분 리스트와 독립 적으로 정렬
부분리스트에 정렬 방법은 선택 정렬 혹은 삽입정렬
(부분 리스트 정렬에서는 초기 패스에 제자리로 정렬될 확률이 높다.)
부분리스트를 구성하는 원속간의 거리 g를 간격(gap)
매 패스 마다 간격의 크기를 줄여 처리(부분 리스트의 수는 줄어듬)


정렬 되지
않은 배열 Pass 번호
1(원소간의 거리 5) 2(원소간의 거리 3) 3(원소간의 거리 1)
83
25
38
49
17
10
52
30 83
25
38
49
17
10
52
30 10
25
30
49
17
83
52
38 10
25
30
49
17
83
52
38 10
17
30
49
25
83
52
38 10
17
30
49
25
83
52
38 10
17
25
30
49
52
38
83
수행 시간 : O(n(log2n)2)
1.5 합병 정렬
(1) 정렬된 배열의 합병
각 배열의 원소를 순차적으로 비교하여 작은 값을 별도의 배열에 출력
5 17 24 　 3
3 19 30 35 42
5 17 24 　 3 5
3 19 30 35 42
5 17 24 　 3 5 17
3 19 30 35 42
5 17 24 　 3 5 7 19
3 19 30 35 42
5 17 24 　 3 5 7 19 24
3 19 30 35 42
5 17 24 　 3 5 7 19 24 30 35 42
3 19 30 35 42
수행 시간 : O(n), n은 두 배열의 크기
page 167 : 배열의 합병 알고리즘
두 부분리스트를 병합하는 알고리즘(2- 원 합병, 2-way merge)
(2) 합병 정렬
2- 원 합병을 일반화 하여 임의의 m 개 부분 리스트를 합병 : 다중 합병, m-원 합병정렬
8개의 부분 리스트를 합병
pass 1 73 65 52 24 83 17 35 96
65 73 24 52 17 83 35 96
pass 2 65 73 24 52 17 83 35 96
24 52 65 73 17 35 83 96
pass 3 24 52 65 73 17 35 83 96
17 24 35 52 65 73 83 96
배열의 원소가 2m 이형태이면, k 번째 pass가 끝 났을때에 각 부분 리스트의 원소는 2k 개임
n개의 원소가 있는 배열을 합병 할려면 ^ log2n ^ 번의 패스가 필요함.
수행 시간 : O(n(log2n))
합병 정렬 알고리즘 (page 171)
주어진 최초의 배열에서 자료원소가 부분적으로 정렬되어 있는 것을 이용하여 부분리스트를 구성 하여 합병정렬
run : 정렬된 부분 리스트
그림 7.1-16 부분적으로 정렬되어 있는 부분리스트로 구성
pass 1 73 65 52 24 83 17 35 96 41 9
65 73 24 52 83 17 35 41 96 9
pass 2 65 73 24 52 83 17 35 41 96 9
24 52 65 73 83 9 17 35 41 96
pass 3 24 52 65 73 83 9 17 35 41 96
9 17 24 35 41 52 65 73 83 96
1.6 퀵정렬
가장 효율적인 방법
세 단계로 수행
1) 한 패스 동안 임의의 원소를 선정 ( pivot 원소)
2) 이 원소를 기준으로 전체를 두 부분리스트로 분할(pivot 값을 기준으로 값이 큰 원소와 값이 적은 리스트로 분류)
3) 각 부분 리스에 대하여 단계 2를 반복 수행
그림 7.1-18 퀵정렬의 전 과정
pass
1 20 88 0 44 99 11 33 55 22 77 66
-> i j <-
20 22 0 44 99 11 33 55 88 77 66
-> -> -> i j <-
20 22 0 44 55 11 33 99 88 77 66
-> -> ->j i<-
20 22 0 44 55 11 33 66 99 88 77
2 20 22 0 44 55 11 33 66 99 88 77
-> -> -> i j
20 22 0 11 55 44 33
->j i<-
20 22 0 11 33 55 44
3 20 22 0 11 33 55 44
i j
0 22 20 11
->j i<- <-
0 11 22 20
4 0
5 22 20
j i<-
20 22
6 55 44
j i<-
44 55
7 99 88 77
j i<- <-
77 99 88
8 99 88
j i<-
88 99
//퀵정렬(QuickSort)
//배열 a에 n개의 원소가 있으면 이를 오름차순으로 정렬한다
Void quick_sort(int a[], int left, int right){
if(left < right) {
pivoit = a[right];
i = left -1;
j = right;

for (;;) {
do
i++;
while ( a[i] < pivot);
do
j--;
while ( a[j] > pivot);

if (i < j)
swap(a[i], a[j]);
else
break;
}
swap(a[i], a[right]);
quick_sort(a, left, i - 1);
quick_sort(a, i + 1, right);
}
}
void main()
{
int a[n+1];
quick_sort(a, 0, n);
}
퀵정렬의 개선
1) pivot 선정 방법 개선
- 부분적으로 정렬된 경우 분할이 한쪽으로 몰릴수 있음.
- 가장 이상적인 방법은 자료의 중간 값을 선정 (추가 연산이 필요)
- 자료의 중간 위치에 있는 값을 찾아, 첫번째, 중간, 마지막의 세 자료를 우선 정렬한 다음, 중간값 과 큰값을 리스트의 마지막에서 첫번째와 두번째에 정렬한후, 중간값을 pivot으로 선정하여 정렬. (간단히 pivot을 구함)
2) 퀵정렬 과정 중에 리스트가 더 작은 리스트로 계속 분할 될 경우 어느 단계에 이르면 부분리스트의 원소가 매우 적어짐.
- 리스트가 매우 작아 지면 퀵정렬은 보조 작업 때문에 다른 정렬 알고리즘보다 횽율이 낮아짐.
- 부분 리스트의 원소 갯수가 9개 이하면 다른 알고리즘을 적용
퀵 정렬의 계산량
T(n)를 n개의 자료를 정렬하는데 소요되는 시간
T(n) = T(i) + T(n-i-1) + cn

1) 최악의 경우 계산량
분할이 한쪽으로 몰릴경우 (예 : 7, 6, 2, 1, 0 )
T(n) = T(i) + T(n-i-1) + cn 식에서 i = 0이 됨
　 T(n) = T(n-1) + cn
　 T(n-1) = T(n-2) + c(n-1)
　 T(n-2) = T(n-3) + c(n-2)
　 　 　 　
　 T(2) = T(1) + c(2)
　 　 　 　
　 T(n) = O(n2)
2) 최선의 경우
pivot의 값이 항상 중앙값이어서 리스트의 중앙에 오는 경우
T(n) = T(i) + T(n-i-1) + cn 에서 i = n/2을 대입 하면
= T(n/2) + T(n - n/2 -1) + cn
= 2*T(n/2) + cn
　
수행
횟수 　 　 　
0 T(n) = 2*T(n/2) + cn
1 2*T(n/2) = 2*2*T(n/4) + 2*cn/2
2 4*T(n/4) = 4*2*T(n/8) + 4*cn/4
　 　 　 　
　 　 　 　
i 2i*T(n/2i) = 2i*2*T(n/2i+1) + 2i*cn/2i
　 　 　 　
　 T(n) = O(n log n)
2) 평균 계산량

T(n) = O(n log n)
1.7 정렬 방법의 비교
알고리즘 평균계산량 최악의 계산량 기억장소 사용량
선택정렬 O(n2) O(n2) 원래배열 그대로 사용
삽입정렬 O(n2) O(n2) 원래배열 그대로 사용
버블정렬 O(n2) O(n2) 원래배열 그대로 사용
쉘정렬 O(n log2 n2) O(n sqrt(n)) 원래배열 그대로 사용
합병정렬 O(n log2 n) O(n log2 n) n개의 추가 장소 필요
퀵정렬 O(n log2 n) O(n2) log2n개의 추가 장소 필요
　
1.8 보조 테이블을 사용한 정렬

자료이동을 줄이는 한 방법으로 보조 테이블을 추가로 사용
보조 테이블에는 레코드 번호(레코드 인덱스)를 저장하고, 실제 데이터를 정렬하는 대신 보조테이블의 레코드 번호를 정렬함.
그림 7.1-20 참조.(p 182)
2. 탐색
주어진 자료의 위치를 알아내는 연산
2.1 선형 탐색
탐색하고자 하는 자료와 배열의 원소를 하나씩 순차적으로 비교
n 개의 원소로 된 배열에서 선형탐색의 최악 및 평균 계 량은 O(n)
단점
- 자료가 정렬되어 있는 경우 시간이 많이 걸림.
2.2 이진 탐색
- 일반적으로 사전에 단어를 찾는 방법과 비슷함.
- 배열의 원소가 정렬되어야함.
- 배열의 중앙 원소를 찾아 값을 비교한후 비교 결과에 따라 중앙의 앞 혹은 뒷 부분을
이전과 동일 하게 검색 하는 방법
// 이진 탐색
int binary_search(int a[], int n, int x) {
int first = 0;
int last = n -1;
int middle:

while (last >= first) {
middle = (first + last) / 2;
if (a[middle] > x)
last = middle -1;
else if (a[middle] < x}
first = middle + 1;
else // 찾았음
return middle;
}
return -1;
}
그림 7.2-1 .이진 탐색의 예 (page 185)
- 최선의 경우
찾고자 하는 값이 배열의 중앙에 있음. O(n)
- 최악의 경우
찾고자 하는 원소가 배열에 없는 경우
한 번 비교시 마다 검색할 원소가 절바느오 줄어듬 O(log2 n)
이진 탐색은 배열에서 자료 원소의 삽입이나 삭제가 거의 없는 경우에 적합.
　
2.3 인덱스 순차 탐색.
정렬된 배열에서 탐색하는 방법으로, 배열의 구간 정보를 가지는 인덱스 테이블을 구축하여 탐색
이진 탐색보다 탐색 구간을 줄일수 있음.
인덱스 테이블이 커지면 이차 보조 인덱스 테이블을 구축할 수 있음.
　
1. 정렬
1.1 선택 정렬
1.2 삽입정렬
정렬되지 않은 리스트의 한 원소씩을 정렬된 리스트에 제 위치를 찾아 삽입
카드를 한 장씩 돌려받을 때 손에 이미 정렬되어 있는 카드 속에 새 카드를 삽입하는 방법
정렬 되지
않은 배열 Pass 번호 정렬된
배열
1 2 3 4 5 6 7 8
77
33
44
11
88
22
66
55 77 33
77 33
44
77 11
33
44
77 11
33
44
77
88 11
22
33
44
77
88 11
22
33
44
66
77
88 11
22
33
44
55
66
77
88 11
22
33
44
55
66
77
88
　
//삽입정렬(insertion_sort)
void insertion_sort(int a[], int n)
int pass, i;
int temp;
for (pass = 2; pass <= n; pass++) { // 두번째 항목 부터 정렬
temp = a[pass - 1];
for(i = pass -2; i >= 0 && a[i] > temp; i--) { // i >= 0 : 비교할 항목이 있음,
// a[i] > temp 비교 항목보다 현재 값이 더큼.
a[i + 1] = a[i]
}
a[i + 1] = temp
}
}
전체 비교 횟수 : 1 + 2 + 3 + ... + (n - 1) = n(n-1)/2
수행 시간 : O(n2)
최선의 경우 : 원래 정렬되어 있는 경우, 전체 비교횟수는 n-1 번
1.3 버블정렬
바로 인접해 있는 두 개의 원소를 비교하여 순서가 바뀌어 있으면 서로 위치를 바꾸어 작은 값의 원소를 배열의 위쪽에 오게 하고 큰값의 원소를 아래쪽으로 가도록 하는 것
각 pass 가 끝나면 큰 값의 원소가 제 위치로 가게됨.
자료 원소들의 움직임은 액체속의 가벼운 기포(bubble)가 위로 올라가고 무거은 것은 아래로 내려오는 움직임과 유사하여 bubble 정렬이라고 부름.

정렬 되지
않은 배열 Pass 번호
1 2 3 4 5
73
65
52
24
83
17
35
96
41
9 65
73 65
52
73 65
52
24
73 65
52
24
73
83 65
52
24
73
17
83 65
52
24
73
17
35
83 65
52
24
73
17
35
83
96 65
52
24
73
17
35
83
41
96 65
52
24
73
17
35
83
41
9
96 52
65 52
24
65 52
24
65
73 52
24
65
17
73 52
24
65
17
35
73 52
24
65
17
35
73 52
24
65
17
35
73
83 52
24
65
17
35
73
41
83 52
24
65
17
35
73
41
9
83 52
24
65
17
35
73
41
9
83
96 　 　 　
전체 비교 횟수 : 1 + 2 + 3 + ... + (n - 1) = n(n-1)/2
수행 시간 : O(n2)
최선의 경우 : 원래 정렬되어 있는 경우, 1 번의 pass로 수행 종료
알고리즘이 수행도중 배열이 완전히 정렬된 상태를 알 수있음. (어떤 패스가 한번의 원소 교환도 없이 종료됨)
한 패스에서 다음 패스로 넘어갈떄 비교해야하는 원소의 수를 하나 이상 줄임으로 정렬 연산의 속도를 개선.
정렬 되지
않은 배열 Pass 번호
1
30
20
50
10
60
70
80
90 20
30
　

교환 20
30
50
　
　
교환 20
30
10
50
　

교환 20
30
10
50
60




20
30
10
50
60
70 20
30
10
50
60
70
80 20
30
10
50
60
70
80
90 65
52
24
73
17
35
83
41
96 65
52
24
73
17
35
83
41
9
96
버블정렬(bubble_sort)
void bubble_sort(int a[], int n) {
int temp;
int last, latest, i;
latest = n-1; //최근에 발생한 교환 위치
do {
last = latest;
for (i = 1; 1 <= last; i++) {
if (a[i - 1] > a[i]) { // 교환할 항목이 발생
latest = i - 1;
temp = a[i - 1];
a[i - 1] = a[i];
a[i] = tgemp;
}
}
}while (latest != last && latgest != 0);
}
// latest == last : 교환이 일어 나지 않음
// latest == 0 : 마지막 교환이 첫번쨰와 두번째 항목에서 발생함.
　
1.4 쉘정렬(shell sort)
버블정렬에서 자료의 위치가 정렬된 위치에서 멀리 떨어져 있다면 여러번 교환이 필요함.
멀리 떨어져 있는 원소끼리 비교 교환하도록 함.
알고리즘의 개요
원래의 자료 리스트를 여러개의 부분 리스트로 그룹화
한 부분 리스트씩 다른 부분 리스트와 독립 적으로 정렬
부분리스트에 정렬 방법은 선택 정렬 혹은 삽입정렬
(부분 리스트 정렬에서는 초기 패스에 제자리로 정렬될 확률이 높다.)
부분리스트를 구성하는 원속간의 거리 g를 간격(gap)
매 패스 마다 간격의 크기를 줄여 처리(부분 리스트의 수는 줄어듬)


정렬 되지
않은 배열 Pass 번호
1(원소간의 거리 5) 2(원소간의 거리 3) 3(원소간의 거리 1)
83
25
38
49
17
10
52
30 83
25
38
49
17
10
52
30 10
25
30
49
17
83
52
38 10
25
30
49
17
83
52
38 10
17
30
49
25
83
52
38 10
17
30
49
25
83
52
38 10
17
25
30
49
52
38
83
수행 시간 : O(n(log2n)2)
1.5 합병 정렬
(1) 정렬된 배열의 합병
각 배열의 원소를 순차적으로 비교하여 작은 값을 별도의 배열에 출력
5 17 24 　 3
3 19 30 35 42
5 17 24 　 3 5
3 19 30 35 42
5 17 24 　 3 5 17
3 19 30 35 42
5 17 24 　 3 5 7 19
3 19 30 35 42
5 17 24 　 3 5 7 19 24
3 19 30 35 42
5 17 24 　 3 5 7 19 24 30 35 42
3 19 30 35 42
수행 시간 : O(n), n은 두 배열의 크기
page 167 : 배열의 합병 알고리즘
두 부분리스트를 병합하는 알고리즘(2- 원 합병, 2-way merge)
(2) 합병 정렬
2- 원 합병을 일반화 하여 임의의 m 개 부분 리스트를 합병 : 다중 합병, m-원 합병정렬
8개의 부분 리스트를 합병
pass 1 73 65 52 24 83 17 35 96
65 73 24 52 17 83 35 96
pass 2 65 73 24 52 17 83 35 96
24 52 65 73 17 35 83 96
pass 3 24 52 65 73 17 35 83 96
17 24 35 52 65 73 83 96
배열의 원소가 2m 이형태이면, k 번째 pass가 끝 났을때에 각 부분 리스트의 원소는 2k 개임
n개의 원소가 있는 배열을 합병 할려면 ^ log2n ^ 번의 패스가 필요함.
수행 시간 : O(n(log2n))
합병 정렬 알고리즘 (page 171)
주어진 최초의 배열에서 자료원소가 부분적으로 정렬되어 있는 것을 이용하여 부분리스트를 구성 하여 합병정렬
run : 정렬된 부분 리스트
그림 7.1-16 부분적으로 정렬되어 있는 부분리스트로 구성
pass 1 73 65 52 24 83 17 35 96 41 9
65 73 24 52 83 17 35 41 96 9
pass 2 65 73 24 52 83 17 35 41 96 9
24 52 65 73 83 9 17 35 41 96
pass 3 24 52 65 73 83 9 17 35 41 96
9 17 24 35 41 52 65 73 83 96
1.6 퀵정렬
가장 효율적인 방법
세 단계로 수행
1) 한 패스 동안 임의의 원소를 선정 ( pivot 원소)
2) 이 원소를 기준으로 전체를 두 부분리스트로 분할(pivot 값을 기준으로 값이 큰 원소와 값이 적은 리스트로 분류)
3) 각 부분 리스에 대하여 단계 2를 반복 수행
그림 7.1-18 퀵정렬의 전 과정
pass
1 20 88 0 44 99 11 33 55 22 77 66
-> i j <-
20 22 0 44 99 11 33 55 88 77 66
-> -> -> i j <-
20 22 0 44 55 11 33 99 88 77 66
-> -> ->j i<-
20 22 0 44 55 11 33 66 99 88 77
2 20 22 0 44 55 11 33 66 99 88 77
-> -> -> i j
20 22 0 11 55 44 33
->j i<-
20 22 0 11 33 55 44
3 20 22 0 11 33 55 44
i j
0 22 20 11
->j i<- <-
0 11 22 20
4 0
5 22 20
j i<-
20 22
6 55 44
j i<-
44 55
7 99 88 77
j i<- <-
77 99 88
8 99 88
j i<-
88 99
//퀵정렬(QuickSort)
//배열 a에 n개의 원소가 있으면 이를 오름차순으로 정렬한다
Void quick_sort(int a[], int left, int right){
if(left < right) {
pivoit = a[right];
i = left -1;
j = right;

for (;;) {
do
i++;
while ( a[i] < pivot);
do
j--;
while ( a[j] > pivot);

if (i < j)
swap(a[i], a[j]);
else
break;
}
swap(a[i], a[right]);
quick_sort(a, left, i - 1);
quick_sort(a, i + 1, right);
}
}
void main()
{
int a[n+1];
quick_sort(a, 0, n);
}
퀵정렬의 개선
1) pivot 선정 방법 개선
- 부분적으로 정렬된 경우 분할이 한쪽으로 몰릴수 있음.
- 가장 이상적인 방법은 자료의 중간 값을 선정 (추가 연산이 필요)
- 자료의 중간 위치에 있는 값을 찾아, 첫번째, 중간, 마지막의 세 자료를 우선 정렬한 다음, 중간값 과 큰값을 리스트의 마지막에서 첫번째와 두번째에 정렬한후, 중간값을 pivot으로 선정하여 정렬. (간단히 pivot을 구함)
2) 퀵정렬 과정 중에 리스트가 더 작은 리스트로 계속 분할 될 경우 어느 단계에 이르면 부분리스트의 원소가 매우 적어짐.
- 리스트가 매우 작아 지면 퀵정렬은 보조 작업 때문에 다른 정렬 알고리즘보다 횽율이 낮아짐.
- 부분 리스트의 원소 갯수가 9개 이하면 다른 알고리즘을 적용
퀵 정렬의 계산량
T(n)를 n개의 자료를 정렬하는데 소요되는 시간
T(n) = T(i) + T(n-i-1) + cn

1) 최악의 경우 계산량
분할이 한쪽으로 몰릴경우 (예 : 7, 6, 2, 1, 0 )
T(n) = T(i) + T(n-i-1) + cn 식에서 i = 0이 됨
　 T(n) = T(n-1) + cn
　 T(n-1) = T(n-2) + c(n-1)
　 T(n-2) = T(n-3) + c(n-2)
　 　 　 　
　 T(2) = T(1) + c(2)
　 　 　 　
　 T(n) = O(n2)
2) 최선의 경우
pivot의 값이 항상 중앙값이어서 리스트의 중앙에 오는 경우
T(n) = T(i) + T(n-i-1) + cn 에서 i = n/2을 대입 하면
= T(n/2) + T(n - n/2 -1) + cn
= 2*T(n/2) + cn
　
수행
횟수 　 　 　
0 T(n) = 2*T(n/2) + cn
1 2*T(n/2) = 2*2*T(n/4) + 2*cn/2
2 4*T(n/4) = 4*2*T(n/8) + 4*cn/4
　 　 　 　
　 　 　 　
i 2i*T(n/2i) = 2i*2*T(n/2i+1) + 2i*cn/2i
　 　 　 　
　 T(n) = O(n log n)
2) 평균 계산량

T(n) = O(n log n)
1.7 정렬 방법의 비교
알고리즘 평균계산량 최악의 계산량 기억장소 사용량
선택정렬 O(n2) O(n2) 원래배열 그대로 사용
삽입정렬 O(n2) O(n2) 원래배열 그대로 사용
버블정렬 O(n2) O(n2) 원래배열 그대로 사용
쉘정렬 O(n log2 n2) O(n sqrt(n)) 원래배열 그대로 사용
합병정렬 O(n log2 n) O(n log2 n) n개의 추가 장소 필요
퀵정렬 O(n log2 n) O(n2) log2n개의 추가 장소 필요
　
1.8 보조 테이블을 사용한 정렬

자료이동을 줄이는 한 방법으로 보조 테이블을 추가로 사용
보조 테이블에는 레코드 번호(레코드 인덱스)를 저장하고, 실제 데이터를 정렬하는 대신 보조테이블의 레코드 번호를 정렬함.
그림 7.1-20 참조.(p 182)
2. 탐색
주어진 자료의 위치를 알아내는 연산
2.1 선형 탐색
탐색하고자 하는 자료와 배열의 원소를 하나씩 순차적으로 비교
n 개의 원소로 된 배열에서 선형탐색의 최악 및 평균 계 량은 O(n)
단점
- 자료가 정렬되어 있는 경우 시간이 많이 걸림.
2.2 이진 탐색
- 일반적으로 사전에 단어를 찾는 방법과 비슷함.
- 배열의 원소가 정렬되어야함.
- 배열의 중앙 원소를 찾아 값을 비교한후 비교 결과에 따라 중앙의 앞 혹은 뒷 부분을
이전과 동일 하게 검색 하는 방법
// 이진 탐색
int binary_search(int a[], int n, int x) {
int first = 0;
int last = n -1;
int middle:

while (last >= first) {
middle = (first + last) / 2;
if (a[middle] > x)
last = middle -1;
else if (a[middle] < x}
first = middle + 1;
else // 찾았음
return middle;
}
return -1;
}
그림 7.2-1 .이진 탐색의 예 (page 185)
- 최선의 경우
찾고자 하는 값이 배열의 중앙에 있음. O(n)
- 최악의 경우
찾고자 하는 원소가 배열에 없는 경우
한 번 비교시 마다 검색할 원소가 절바느오 줄어듬 O(log2 n)
이진 탐색은 배열에서 자료 원소의 삽입이나 삭제가 거의 없는 경우에 적합.
　
2.3 인덱스 순차 탐색.
정렬된 배열에서 탐색하는 방법으로, 배열의 구간 정보를 가지는 인덱스 테이블을 구축하여 탐색
이진 탐색보다 탐색 구간을 줄일수 있음.
인덱스 테이블이 커지면 이차 보조 인덱스 테이블을 구축할 수 있음.
　
Report
Page 175 프로그램 7.1-7 퀵정렬 에서 pivot이 이동할때 마다 출력하도록 하시오.
Page 177 프로그램 7.1-7 pivot 선정을 활용하여 개선된 퀵정렬 프로그램을 작성하고, pivot이 이동할때 마다 출력하도록 하시오.
Page 185 프로그램 7.2-1 이진탐색에서탐색되어 가는 과정을 출력 하는 프로그램을 작성.
연습문제 풀이) 8, 10, 11, 13