자료구조 (Data Structures) IT 학부

자료구조 강의 목표 컴퓨터를 이용하여 프로그램을 하는데 있어서 가장 기본이 되는 자료에 대한 다양한 형태의 구조에 대하여 학습하며, 각 구조의 특징과 주어진 상황에 따른 장단점을 파악하여, 실제적인 프로그램 작업에서 적용할 수 있는 능력을 배양한다.

강의 일정 연락처 교재 평가 유원경: wyoo@sungshin.ac.kr 강의 일정 연락처 유원경: wyoo@sungshin.ac.kr Office: 수정관 421호 , 02-920-7177 교재 주 교재 : C언어로 쉽게 풀어 쓴 자료구조 (생능 출판사, 천인국.공용해공저) 부 교재 :알기 쉽게 해설한 데이터구조, C,C++로 배우는 자료구조, C++ 자료구조론, 한번에 이해되는 C자료구조 등.. 강의 사이트 : http://cs.sungshin.ac.kr/~wyoo/lec_ds.html 평가 중간/ 기말 시험, 과제 제출 (프로그래밍 실습과제) 메일보내는 규칙: 제목에 반드시 자료구조 학번 이름 과제명 명시할것 ex) 자료구조 20111111 홍길동 과제1 출석 ( 5%) 과제( 15 %) 중간시험( 40 %) 기말시험( 40 %)

0. 자료구조 Introduction 학습목표 자료구조의 의미와 중요성을 알아본다. 자료구조에서 다루는 내용을 알아본다.

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

Introduction 자료구조 - 프로그램에서 자료들을 정리하는 구조 - 프로그램에서 자료들을 정리하는 구조 - 자료구조란 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업

Introduction 자료의 형태에 따른 분류

Introduction 기본이 되는 자료구조 리스트, 스택, 큐, 트리, 정렬, 그래프

Introduction 리스트 : 순서가 정해진 목록

Introduction 스택 : LIFO

Introduction 큐 : FIFO

Introduction 트리 : 뿌리와 가지로 구성

Introduction 정렬 : 값의 크기에 따라 나열해 놓은 것

그래프 : 노드와 노드 사이 연결관계가 설정(path) Introduction 그래프 : 노드와 노드 사이 연결관계가 설정(path)

CHAP 1:자료구조와 알고리즘

일상생활과 자료구조의 비교 Ticket Box 해야할일 리스트 A B C 일상생활에서의 예 자료구조 물건을 쌓아두는 것 스택 NULL A B C Ticket Box 전단(front) 후단(rear) 일상생활에서의 예 자료구조 물건을 쌓아두는 것 스택 영화관 매표소의 줄 큐 할일 리스트 리스트 영어사전 사전, 탐색구조 지도 그래프 조직도 트리

자료구조와 알고리즘 프로그램 = 자료구조 + 알고리즘 … (예) 최대값 탐색 프로그램 = 배열+ 순차탐색 자료구조 알고리즘 score[] 80 70 90 … 30 tmp←score[0]; for i ← 1 to n do if score[i]>tmp then tmp←score[i];

박철수의 전화번호는 바로 ㅂ부근으로 넘기면 찾을 수 있겠군 알고리즘 박철수의 전화번호는 바로 ㅂ부근으로 넘기면 찾을 수 있겠군 알고리즘(Algorithm) 컴퓨터로 문제를 풀기 위한 단계적인 절차 특정 작업을 수행하기 위한 명령어들의 집합 알고리즘이 되기 위한 5 가지 조건

알고리즘의 기술 방법 영어나 한국어와 같은 자연어 흐름도(flow chart) 유사 코드(pseudo-code) (예) 배열에서 최대값 찾기 알고리즘 1 2 3 4 5 6 7 8 9 10

자연어로 표기된 알고리즘 인간이 읽기가 쉽다. 그러나 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있다. (예) 배열에서 최대값 찾기 알고리즘 ArrayMax(A,n) 배열 A의 첫번쨰 요소를 변수 tmp에 복사 배열 A의 다음 요소들을 차례대로 tmp와 비교하면 더 크면 tmp로 복사 배열 A의 모든 요소를 비교했으면 tmp를 반환

흐름도로 표기된 알고리즘 직관적이고 이해하기 쉬운 알고리즘 기술 방법 그러나 복잡한 알고리즘의 경우, 상당히 복잡해짐. tmp←A[0] i←1 i < n A[i]>tmp tmp←A[i] tmp no yes i++

유사코드로 표현된 알고리즘 알고리즘의 고수준 기술 방법으로 알고리즘 기술에 가장 많이 사용 자연어보다는 더 구조적인 표현 방법이며, 프로그래밍 언어보다는 덜 구체적인 표현 방법임 프로그램을 구현할 때의 여러가지 문제들을 감출 수 있다. 즉 알고리즘의 핵심적인 내용에만 집중할 수 있다. ArrayMax(A,n) tmp ← A[0]; for i←1 to n-1 do if tmp < A[i] then tmp ← A[i]; return tmp; 대입 연산자가 ←임을 유의

C로 표현된 알고리즘 알고리즘의 가장 정확한 기술이 가능 반면 실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있다. #define MAX_ELEMENTS 100 int score[MAX_ELEMENTS]; //자료구조 int find_max_score(int n) { int i, tmp; tmp=score[0]; for(i=1;i<n;i++){ //알고리즘 if( score[i] > tmp ){ tmp = score[i]; } return tmp;

데이터 타입, 추상 데이터 타입 데이터(data) : 프로그램에서 처리의 대상 데이터 타입(data type) (예) (C) : int, char, float, double, array, struct… 데이터의 집합과 데이터에 적용할 수 있는 연산(operation)의 집합 (예) 추상 데이터 타입(ADT: Abstract Data Type) 데이터 타입을 추상적(수학적)으로 정의한 것 데이터의 명세와 이들 데이터에 대한 연산의 명세가 실제 데이터의 구현과 연산의 구현으로부터 분리된 방식으로 구성된 데이터 타입 데이터나 연산이 무엇(what)인가는 정의되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현(implementation )할 것인지는 정의되지 않는다. int 데이터 타입 데이터: { …,-2,-1,0,1,2,…} =>정수의 집합 연산: +, -, /, *, % => 정수간의 연산

추상 데이터 타입의 예: “자연수(양의정수)” 객체 : 집합의 개념을 사용하여 정의 연산 : 연산의 이름, 매개변수, 연산의 결과, 연산이 수행하는 기능의 기술 등 포함 Nat_No 객체: 0에서 시작하여 INT_MAX까지의 순서화된 정수의 부분범위 연산: zero() ::= return 0; is_zero() ::= if (x) return FALSE; else return TRUE; add(x,y) ::= if( (x+y) <= INT_MAX ) return x+y; else return INT_MAX sub(x,y) ::= if ( x<y ) return 0; else return x-y; equal(x,y)::= if( x=y ) return TRUE; else return FALSE; successor(x)::= if( (x+y) <= INT_MAX ) return x+1;

추상 데이터 타입과 VTR ▪사용자들은 추상 데이터 타입이 제공하는 연산만을 사용할 수 있다. ▪사용자들은 추상 데이터 타입을 어떻게 사용하는지를 알아야 한다. ▪사용자들은 추상 데이터 타입 내부의 데이터를 접근할 수 없다. ▪사용자들은 어떻게 구현되었는지 몰라도 이용할 수 있다. ▪만약 다른 사람이 추상 데이터 타입의 구현을 변경하더라도 인터페이스가 변경되지 않으면 사용할 수 있다. ▪VCR의 인터페이스가 제공하는 특정한 작업만을 할 수 있다. ▪사용자는 이러한 작업들을 이해해야 한다. 즉 비디오를 시청하기 위해서는 무엇을 해야 하는지를 알아야 한다. ▪VCR의 내부를 볼 수는 없다. ▪VCR의 내부에서 무엇이 일어나고 있는지를 몰라도 이용할 수 있다. ▪누군가가 VCR의 내부의 기계장치를 교환한다고 하더라도 인터페이스만 바뀌지 않는 한 그대로 사용이 가능하다.

성능 평가 공간적 효율성과 시간적인 부분 고려 알고리즘의 성능분석 프로그램의 성능 평가(performance evaluation)를 하기 위한 알고리즘의 효율성 공간적 효율성과 시간적인 부분 고려 정의 : 프로그램의 공간 복잡도(space complexity) 프로그램을 실행시켜 완료하는 데 필요한 공간의 양 공간 복잡도 = 고정 공간 + 가변 공간 정의 : 프로그램의 시간 복잡도(time complexity) 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간의 양 시간 복잡도 = 컴파일 시간 + 실행 시간

알고리즘의 성능분석 알고리즘의 성능 분석 기법 수행 시간 측정 알고리즘의 복잡도 분석 시간 복잡도 분석: 수행 시간 분석 두개의 알고리즘의 실제 수행 시간을 측정하는 것 실제로 구현하는 것이 필요 동일한 하드웨어를 사용하여야 함 알고리즘의 복잡도 분석 시간 복잡도 분석: 수행 시간 분석 직접 구현하지 않고서도 수행 시간을 분석하는 것 알고리즘이 수행하는 연산의 횟수를 측정하여 비교 일반적으로 연산의 횟수는 n의 함수 공간 복잡도 분석: - 수행시 필요로 하는 메모리 공간 분석

수행시간측정 컴퓨터에서 수행시간을 측정하는 방법에는 주로 clock 함수가 사용된다. clock_t clock(void); clock 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환 수행시간을 측정하는 전형적인 프로그램 #include <stdio.h> #include <stdlib.h> #include <time.h> void main( void ) {    clock_t start, finish;    double  duration;    start = clock();     // 수행시간을 측정하고 하는 코드....      // ....    finish = clock();    duration = (double)(finish - start) / CLOCKS_PER_SEC;    printf("%f 초입니다.\n", duration); }

복잡도 분석 시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시 알고리즘이 수행하는 연산의 개수를 계산하여 두 개의 알고리즘을 비교할 수 있다. 산술 연산, 대입 연산, 비교 연산, 이동 연산의 기본적인 연산: 연산의 실행횟수 연산의 수행횟수는 고정된 숫자가 아니라 입력의 개수 n에 대한 함수->시간복잡도 함수라고 하고  T(n) 이라고 표기한다. 프로그램 A 프로그램 B 워드2005 워드2000 연산의 수 =26 5n2 +6 연산의 수 = 8 3n+2

복잡도 분석의 예 n을 n번 더하는 문제: 각 알고리즘이 수행하는 연산의 개수를 세어 본다. 각 알고리즘이 수행하는 연산의 개수를 세어 본다. 단 for 루프 제어 연산은 고려하지 않음. 알고리즘 A 알고리즘 B 알고리즘 C sum ←n*n; sum ← 0; for i ← 1 to n do    sum ←sum + n; for i←1 to n do   for ←1 to n do     sum ←sum + 1;   알고리즘 A 알고리즘 B 알고리즘 C 대입연산 1    n + 1      n*n + 1      덧셈연산   n     n*n      곱셈연산 나눗셈연산 전체연산수 2   2n + 1      2n2 + 1   

연산의 횟수를 그래프로 표현 연산의 횟수 알고리즘 C 알고리즘 B 알고리즘 A 입력의 개수 n

시간복잡도 함수 계산 코드를 분석해보면 수행되는 연산들의 횟수를 입력 크기의 함수로 만들 수 있다. ArrayMax(A,n) tmp ← A[0]; for i←1 to n-1 do if tmp < A[i] then tmp ← A[i]; return tmp; 1번의 대입 연산 루프 제어 연산은 제외 n-1번의 비교 연산 n-1번의 대입 연산(최대) 1번의 반환 연산 총 연산수= 2n(최대)

빅오 표기법 n=1000인 경우 T(n)= n2 + n + 1 99% 1% 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다. (예)  n=1,000 일 때, T(n)의 값은 1,001,001이고 이중에서 첫 번째 항인 n2 의 값이 전체의 약 99%인 1,000,000이고 두 번째 항의 값이 1000으로 전체의 약 1%를 차지한다. 따라서 보통 시간복잡도 함수에서 가장 영향을 크게 미치는 항만을 고려하면 충분하다. 빅오표기법: 연산의 횟수를 대략적(점근적)으로 표기한 것 두개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다. 빅오는 함수의 상한을 표시한다. (예) n≥5 이면 2n+1 <10n 이므로 2n+1 = O(n) n=1000인 경우 T(n)= n2 + n + 1 99% 1% 연산의 횟수 입력의 개수 n

빅오 표기법 f(n) = 3n + 2의 빅오 표기법은 O(n ) 이다. 빅오 표기법(Ο) f(n) = 3n + 2의 빅오 표기법은 O(n ) 이다. 3n + 2 = O (n ) 임을 증명하기 위해서는 알고리즘의 효율을 나타내는 O ( )의 괄호 안에 들어가는 함수 g(n) = n일 때 f(n) ≤ cg(n)인 조건을 만족하는 n0과 c가 존재함을 보이면 된다.

빅오 표기법의 예

예) 피보나치 수열 알고리즘의 빈도수 구하기 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>1의 일반적인 경우에 대한 실행 빈도수 총 실행 빈도수 = 1+0+1+0+1+1+0+(n-1)+(n-1)+(n-1)+0+1+0 = 3n+2 [표 2-3] 피보나치 수열 알고리즘의 실행 빈도수 : n>1의 경우

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

성능 분석 다음의 빅오 표기법은 가장 많이 사용되는 것으로서 실행시간이 빠른 순서대로 기술한 것이다.

빅오 표기법의 종류 시간복잡도 n 1 2 4 8 16 32 logn 3 5 nlogn 24 64 160 n2 256 1024 3 5 nlogn 24 64 160 n2 256 1024 n3 512 4096 32768 2n 65536 4294967296 n! 40326 20922789888000 26313×1033

빅오 표기법이외의 표기법 빅오메가 표기법(Big Omega, Ω) 빅오메가(Big Omega, Ω) 표기법은 빅오 기호의 반대 개념이다. 알고리즘 수행 시간의 하한(Lower Bound)으로서 “최소한 이만한 시간은 걸린다”라는 의미이다. 수학적 정의 [오메가(Omega)] : 모든 n, n≥n0,에 대해 f(n) ≥ cg(n)을 만족하는 두 양의 상수 c와 n0가 존재하기만 하면 f(n) = Ω(g(n)) (f of n은 "omega" of g of n이라 읽음)이다.

빅오 표기법이외의 표기법 빅세타 표기법 모든 n≥n0에 대하여 c1|g(n)| ≤ |f(n)| ≤ c2|g(n)|을 만족하는 3개의 상수 c1, c2와 n0가 존재하면 f(n)=θ(g(n))이다. 빅세타는 함수의 하한인 동시에 상한을 표시한다. f(n)=O(g(n))이면서 f(n)= Ω(g(n))이면 f(n)= θ(n)이다. (예) n ≥ 1이면 n ≤ 2n+1 ≤ 3n이므로 2n+1 = θ(n) . 입력의 개수 n 연산의 수 상한 하한

최선, 평균, 최악의 경우 (예) 정렬 알고리즘의 수행 시간은 입력 집합에 따라 다를 수 있다. 알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있다. (예) 정렬 알고리즘의 수행 시간은 입력 집합에 따라 다를 수 있다. 최선의 경우(best case): 수행 시간이 가장 빠른 경우 평균의 경우(average case): 수행시간이 평균적인 경우 최악의 경우(worst case): 수행 시간이 가장 늦은 경우 최악의 경우 최선의 경우 평균적인 경우 A B C D E F G 입력 집합 수행시간 100 50 최선의 경우: 의미가 없는 경우가 많다. 평균적인 경우: 계산하기가 상당히 어려움. 최악의 경우: 가장 널리 사용된다. 계산하기 쉽고 응용에 따라서 중요한 의미를 가질 수도 있다.

최선, 평균, 최악의 경우 (예) 순차탐색 최선의 경우: 찾고자 하는 숫자가 맨앞에 있는 경우 ∴ O(1) P.32 program 참고 최선의 경우: 찾고자 하는 숫자가 맨앞에 있는 경우 ∴ O(1) 최악의 경우: 찾고자 하는 숫자가 맨뒤에 있는 경우 ∴ O(n) 평균적인 경우: 각 요소들이 균일하게 탐색된다고 가정하면 (1+2+…+n)/n=(n+1)/2

연산을 호출할때 구조체를 함수의 파라미터로 전달 자료 구조의 C언어 표현방법 자료구조와 관련된 데이터들을 구조체로 정의 연산을 호출할 경우, 이 구조체를 함수의 파라미터로 전달 (예) // 자료구조 스택과 관련된 자료들을 정의 typedef int element; typedef struct { int top; element stack[MAX_STACK_SIZE]; } StackType; // 자료구조 스택과 관련된 연산들을 정의 void push(StackType *s, element item) { if( s->top >= (MAX_STACK_SIZE -1)){ stack_full(); return; } s->stack[++(s->top)] = item; 자료구조의 요소 관련된 데이터를 구조체로 정의 연산을 호출할때 구조체를 함수의 파라미터로 전달

자료구조 기술규칙 상수 변수의 이름 함수의 이름 typedef의 사용 (예) typedef int element; 대문자로 표기 (예) #define MAX_ELEMENT 100 변수의 이름 소문자를 사용하였으며 언더라인을 사용하여 단어와 단어를 분리 (예) int increment;     int new_node; 함수의 이름 동사를 이용하여 함수가 하는 작업을 표기 (예)  int add(ListNode *node)    // 혼동이 없는 경우       int list_add(ListNode *node) //혼동이 생길 우려가 있는 경우 typedef의 사용 C언어에서 사용자 정의 데이터 타입을 만드는 경우에 쓰이는 키워드 (예) typedef int element;      typedef struct ListNode {              element data;              struct ListNode *link;       } ListNode;               typedef <새로운 타입의 정의>  <새로운 타입 이름>;