1 장기본개념 1
자료와정보 컴퓨터 주기억장치 자료 정보 보조기억장치 자료, 프로그램 자료구조 자료저장, 이용알고리즘 프로그램 I = P(D) 2
자료구조의영역 3
자료구조 기본개념 선형구조 배열 ( 연속리스트 (continuous list) 스택 (stack), 큐 (queue) 연결리스트 (linked list) 비선형구조 트리 (tree), 그래프 (graph) 자료구조응용 탐색, 정렬 4
선형구조 배열 : 스택 : 큐 : 연결리스트 : 5
비선형구조 트리 그래프 1 : N N : M 6
알고리즘과프로그램 알고리즘 (algorithm) 특정문제를해결하기위해기술한일련의논리의순서 프로그램 (program) 알고리즘을컴퓨터가이해하고실행할수있는특정 프로그래밍언어로표현한것 program = algorithm + data structure 7
알고리즘의특징 입력 : 외부제공자료가있을수있음 출력 : 한가지이상의결과생성 명확성 : 각명령은명확 유한성 : 한정된단계실행후종료 유효성 : 컴퓨터처리가능 8
알고리즘기술방법 알고리즘기술언어사용 자연어에의한표현한글또는영문슈도코드 (PSEUDO CODE) 도형에의한표현흐름도 (FLOW CHART) 박스 (BOX) 다이어그램 9
정수형자료 자료의종류와표현 (1) 4byte (short : 2byte, int 와 long : 4byte) 10 진수 35 표현 0 1 31 0 000 0000 0000 0000 0000 0000 0010 0011 부호부정수부 실수형자료 4byte (float : 4byte, double 과 long double : 8byte) 10 진수 -45.75 표현 0 1 7 8 31 1 100 0010 0010 1101 1100 0000 0000 0000 부호부지수부가수부 10
자료의종류와표현 (2) 문자형자료 영문자 : 1byte, 한글문자 : 2byte A는 ASCII 코드인 01000001 이저장 논리형자료 참 (true, 1) 또는거짓 (false, 0) &&(AND), (OR),!(NOT) 포인터형자료 저장장소의주소를표현하기위한자료형 int i, *pi : i는정수변수, pi는정수에대한포인터변수 pi = &i : &i는 i의주소값을 pi의값으로지정 *pi = 10 : 포인터 pi가가리키는장소에 10을저장 11
자료와자료형 자료 현실세계의관찰이나측정을통해수집된값이나사실 프로그램의처리대상이되는모든것 자료형 자료의집합과이자료에적용할수있는연산의집합 예 ) integer 자료형 - 자료 : 정수 ( -2,-1,0,1,2 ), 연산자 : +, -, *, /, mod 추상자료형 (ADT) 은객체의명세와그연산의명세가그객체의표현과연산의구현으로부터분리된자료형 12
추상자료형 추상화 (abstraction) 자세한것은무시하고, 필수적이고중요한속성만으로단순화시키는과정 추상자료형 (abstraction data type : ADT) 자료형의논리적정의 자료와연산의본질에대한명세만정의한자료형 자료가무엇이고, 각연산의기능을정의 추상화와구체화의관계 추상화 구체화 자료 추상자료형 자료형 연산 알고리즘 프로그램 13
자연수의추상자료형 ADT Natno object : { i i integer, i 0} function : for all x, y Natno zero() ::= return 0; iszero(x) ::= if (x=0) then return true else return false; succ(x) ::= return x + 1; add(x, y) ::= return x + y; subtract(x, y) ::= if x < y then return 0 else return x - y; equal(x, y) ::= if x = y then return true else return false; End Natno 14
순환 (recursion) 순환의종류 직접순환 : A A 간접순환 : A B A 순환방식의적용 분할정복 (divide and conquer) 의특성을가진문제에적합 어떤복잡한문제를직접간단하게풀수있는작은문제로분할하여해결하려는방법 15
16 순환알고리즘과비순환알고리즘 n! 의계승 (factorial) 함수를정의 순환정의 일때일때 1 1 2 1) ( 1 1! n n n n n 때일일때 1 1 )! ( 1 1! n n n n n
Factorial 순환함수 (1) 순환알고리즘 Factorial(n) // n 은음이아닌정수 if (n <= 1) then return 1 else return (n factorial(n-1)); end Factorial() Factorial(4) = (4 Factorial(3)) = (4 (3 Factorial(2))) = (4 (3 (2 Factorial(1)))) = (4 (3 (2 1))) = (4 (3 2)) = (4 6) = 24 17
Factorial 순환함수 (2) 비순환함수표현 n-factorial(n) if (n <= 1) then return 1; fact 1; for( i 2; i<= n; i i+1) do{ fact fact*i; } return fact; end n-factorial() 18
성능분석과성능측정 성능분석 (performance analysis) 프로그램을실행하는데필요한시간과공간추정 성능측정 (performance measurement) 컴퓨터가실제로프로그램을실행하는데걸리는시간측정 19
공간복잡도 Sp = Sc + Se 고정공간 + 가변공간 시간복잡도 Tp = Tc + Te 컴파일시간 + 실행시간 성능분석 20
연산시간표기법 연산시간표기법 Big-Oh (O), Big-Omega (Ω), Big-Theta (θ) Big-Oh (O) f, g가양의정수를갖는함수일때, 두양의상수 a, b가존재하고, 모든 n b에대해 f(n) a g(n) 이면, f(n) = O(g(n)) f(n) = 3n + 2 : f(n) = O(n) (a=4, b=2) f(n) = 1000n 2 +100n 6 : f(n) = O(n 2 ) (a=1001, b=100) f(n) = 6 2 n + n 2 : f(n) = O(2 n ) (a=7, b=4) f(n) = 100 : f(n) = O(1) (a=100, b=1) 21
연산시간표현 22
연산시간함수의변화 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 84 2 n n 3 n 2 n nlog 2 n log 2 n 2 1 2 4 8 16 32 64 128 23
2 장배열과레코드 24
배열 (array) 자료를컴퓨터기억장치내의연속적인기억장소에저장하여순차적으로또는임의적으로접근할수있는가장간단한선형자료구조 < 인덱스, 원소 > 쌍의집합 원소들은모두같은형 (type), 같은크기 접근방법은직접접근 배열이름이 a 라면, a[ 인덱스 ]= 원소값 인덱스 0 1 2 3 4 5 6 7 8 9 원소값 7 3 9 5 2 9 2 10 30 25
배열의추상자료형 26
배열 (array) 1 차원배열 A[0] A[1] A[2] A[3].. A[99] A(L) A(L+1) A(L+2) A(L+3).. A(U) 원소또는멤버 배열원소의수 : U( 상한값 ) L( 하한값 ) + 1 A[100] 이라고배열을선언하면 A[0] 부터 A[99] 까지사용 A[-2:3] 은 A[-2], A[-1], A[0], A[1], A[2], A[3] 을나타냄. ( 다른언어에서사용 ) Address(i) = Address(A(L)) + i 27
배열 (array) 2 차원배열 (1) 2 차원배열 (n m) 행 (row) A[0][0] A[0][1] A[0][2] A[0][m-1] 열 (Column) A[1][0] A[2][0]. A[n-1][0] A[n-1][m-1] 28
배열 (array) 2 차원배열 (2) 2 차원배열 (n m) 2차원배열의저장방법 행우선저장방법 A[0][0] A[0][1] A[0][2] A[0][m-1] A[1][0] A[2][0]. A[n-1][0] A[n-1][m-1] Address(A(i,j)) = Address(A(L1,L2)) + (i-l1)*(u2-l2+1)*k + (j-l2)*k 29
배열 (array) 2 차원배열 (3) 2 차원배열 (n m) 2차원배열의저장방법 열우선저장방법 A[0][0] A[0][1] A[0][2] A[0][m-1] A[1][0] A[2][0]. A[n-1][0] A[n-1][m-1] Address(A(i,j)) = Address(A(L1,L2)) + (j-l2)*(u1-l1+1)*k + (i-l1)*k 30
배열의표현 - 2 차원배열 (4) 2 차원배열의선언 : a[n 1, n 2 ] n 1 : 행의수, n 2 : 열의수, 원소수 :n 1 n 2 2 차원배열을 1 차원메모리표현 행 A[2,3] 열 0 1 2 0 1 [0,0] [0,1] [0,2] [1,0] [1,1] [1,2] 행우선 0 행 1 행 [0,0] [1,0] [0,1] [1,1] [0,2] [1,2] 열우선 0 열 1 열 2 열 31
배열의표현 - 2 차원배열 (5) 2 차원배열 a[m, n] 일경우, 처음원소 : a[0,0] 주소가 α 일때, 임의의원소 a[i,j] 의주소 행우선 : α + i*n +j 열우선 : α + j*m +i 0 1 0 1 3 A[2,3] 일때 A[1,0] 의주소행우선 : 1+1x3+0 열우선 : 1+0x2+1 32
배열 (array) 3 차원배열 3 차원배열 a[n 1, n 2, n 3 ] : < 면, 행, 열 > n 1 개의 2차원배열 ( 크기가 n 2 Ⅹn 3 ) 을차례로 1차원메모리에순차적으로사상 a[0, 0, 0] 의주소를 α라할때, a[i 1, i 2, i 3 ] 의주소 : α + i 1 n 2 n 3 + i 2 n 3 +i 3 α α+ n 2 n 3 α+(n 1-1) n 2 n 3 n 2 n 3 원소 n 2 n 3 원소 n 2 n 3 원소 a[0, n 2, n 3 ] a[1, n 2, n 3 ] a[n 1, n 2, n 3 ] 33
순서리스트 (1) 순서를가진원소들의순열 물리적순서가아닌원소의특성에의한논리적순서를의미 리스트 (list) 는단순히원소들의순열 (sequence) 리스트 L=(e 1, e 2,, e n ) L 은리스트이름, e i 는리스트원소 공백리스트 ( 원소가하나도없는리스트 ) 의표현 : L=( ) 리스트의각원소는선행자 (predecessor) 와후속자 (successor) 를가짐 요일 = ( 월, 화, 수, 목, 금, 토, 일 ) 34
순서리스트 (2) S = (a 1,a 2,,a n ) 리스트길이 (n) : 유한 리스트읽음 (left right, right left) : access i번째원소검색 (1 i n) : retrieve i번째에새로운값저장 (1 i n) : update i번째에새로운원소삽입 : insert i i+1 i번째원소삭제 : delete i+1 i 35
리스트를처리하는연산 36
다항식의 1 차원배열표현 (1) < 표현 1> 계수를순서적으로표현 p(x)=a n x n +a n-1 x n-1 + +a 1 x+a 0 a n a n-1 a n-2 a 1 a 0 coef[o] [1] [2] [n-1] [n] 2X 4 +10X 3 +X 2 +6 : (2, 10, 1, 0, 6) < 표현 2> 0 이아닌계수만을취한표현 b(x)=b m-1 x em-1 +b m-2 x em-2 + +b 0 x e0 (e m-1, b m-1, e m-2, b m-2,, e 0, b 0 ) 2X 4 +10X 3 +X 2 +6 : (4, 2, 3, 10, 2, 1, 0, 6) 37
다항식의 1 차원배열표현 (2) 예 )A=5X 10 +2 일경우 < 표현1> A=(n, a n, a n-1,, a 1, a 0 ) 10 5 0 0 0 0 0 0 0 0 2 < 표현 2> A =(m,e m-1,b m-1,e m-2,b m-2,,e 0,b 0 ) 10 5 0 2 38
다항식의 2 차원배열 2X 8-6X 5 +10X 3 +X 2-2 : (8, 2, 5, -6, 3, 10, 2, 1, 0, -2) < 표현 2> 0 이아닌계수만을취한표현방법으로 p[5,2] 에표현 p[0] [1] [2] [3] [4] 지수 [0] 8 5 3 2 0 계수 [1] 2-6 10 1-2 39
다항식의 ADT(1) 40
다항식의 ADT(2) 41
두다항식덧셈알고리즘 (1) 42
두다항식덧셈알고리즘 (2) 43
희소행렬 44
행렬의배열표현 45
희소행렬의표현방법 행렬은 < 행, 열, 값 > 으로원소를식별 0이아닌원소에대해열이 3인 2차원배열로표현 효율적인연산을위해행과열을오름차순으로저장 B= 7 6 76 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 3 0 25 0 0 0 0-19 0 0 56 0 0 0 0 0 0 0 13 0 0 3 0 0 0 C[9,3] b[0] [1] [2] [3] [4] [5] [6] [7] [8] [0] [1] [2] 7 6 8 0 0 76 0 4 13 2 5 3 3 1 25 4 0-19 4 3 56 5 5 13 6 2 3 46
희소행렬의전치 (1) 전치행렬 (transposed matrix) 원소의행과열을교환시킨행렬 원소 <i, j, v> <j, i, v>, 예 ) <0, 4, 13> <4, 0, 13> 간단한전치행렬알고리즘 ( 행우선표현 ) for (j 0; j <= n-1 ; j j+1 ) do for (i 0; i <=m-1 ; i i+1 ) do b[j, i] a[i, j]; 희소행렬의전치 행우선, 행내에선열오름차순으로저장된경우, 각열별로차례로모든원소를찾아행의오름차순으로저장하는작업을반복 47
전치행렬을저장한배열 48
희소행렬의전치 (2) 49
희소생렬의전치알고리즘 50
희소행렬의구조체선언 51
희소행렬의전치프로그램 52
문자열추상자료형 53
문자열연결 #define MAX_SIZE 100 /* 문자열의최대크기 */ char s[max_size]="dog"; char t[max_size]="house"; char s[]="dog"; char t[]="house"; s[0] s[1] s[2] s[3] d o g \0 t[0] t[1] t[2] t[3] t[4] t[5] h o u s e \0 s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9] d o g h o u s e \0 문자열 s와 t를 strcat(s, t) 연결함수로연결한결과 54
문자열삽입 #include <string.h> #define MAX_SIZE 100 /* 가장긴문자열의길이 */ char string1[max_size], *s = string1; char string2[max_size], *t = string2; s t temp temp temp temp a m o b i l e \0 u t o \ 0 \ 0 초기상태 a \ 0 strncpy(temp,s,i) 호출후 a u t o \ 0 strcat(temp,t) 호출후 a u t o m o b i l e \ 0 strcat(temp,s+i) 호출후 55
레코드 논리적으로서로연관이있는자료원소들의집합체 집합체의이름 : 레코드이름 레코드집합체내의각자료원소 : 필드 ( 항목, field) 학번 이름 나이 출생지 성별 76543 홍길동 18 서울 M int char short char Char 4byte 9byte 2byte 5byte 1byte 56
C 언어에서의레코드구현 (1) 57
Typedef 를이용한구조체정의 58
레코드와파일 레코드들의모음 ( 집합체 ) : 파일 (file) 순차파일 (sequence file) : 파일내의모든레코드들의논리적구조가동일한파일 키필드 (key field) : 레코드를구별할수있는특정필드 키순차파일 (key-sequenced file) : 키필드의값에따라레코드들이정렬된파일 학번이름나이출생지성별 76543 홍길동 18 서울 M 76545 김철수 20 경기 M 76612 박영희 19 충청 W 76615 이기수 21 전라 M 76724 정미영 20 경상 W 76811 최미숙 21 강원 W 59
3 장스택과큐 60
스택의정의 자료의입력과출력이한쪽 끝에서만이루어짐 삽입 삭제 후입선출리스트 (LIFO, Last In First Out) 5 여유 PUSH, POP 연산 4 공간 top 포인터로삽입과삭제가이루어짐 top P x Y 3 2 1 Z 0 bottom -1 61
스택의자료삽입과삭제 삽입 : Push, 삭제 : Pop top을스택포인터 (stack pointer) 라함 top top A top B A top C B A top D C B A top C B A top B A top E B A 62
스택의추상자료형 (1) 63
스택의추상자료형 (2) 64
스택의순차표현 1 차원배열, Stack[n] 을이용한순차표현 스택을표현하는가장간단한방법 n은스택에저장할수있는최대원소수 스택의 i 번째원소는 Stack[i-1] 에저장 변수 top은스택의톱원소를가리킴 ( 초기 : top = -1) 첫번째원소 두번째원소 i 번째원소 n 번째원소 stack[0] stack[1] stack[i-1] stack[n-1] 65
C 배열을이용한스택의구현 (1) #include <stdio.h> #include <stdlib.h> #define STACK_SIZE 100 typedef int element; /* element를 int 타입으로정의 */ element stack[stack_size]; void push(int *top, element item) { if(*top >= STACK_SIZE - 1) { /* 스택이만원인경우 */ printf(" Stack is full\n"); return;} stack[++(*top)] = item;} /* top은 top+1로 */ 66
C 배열을이용한스택의구현 (2) element pop(int *top) { if (*top == -1){ /* 스택이공백인경우 */ printf("stack is empty\n"); exit(1);} else return stack[(*top)--]; } /* top 은 top-1 로 */ element delete1(int *top) { if (*top == -1){ /* 스택이공백인경우 */ printf("stack is empty\n"); exit(1);} else return stack[(*top)--]; } /* top 은 top-1 로 */ 67
C 배열을이용한스택의구현 (3) int isempty(int *top) { if (*top = = -1) return 1; /* 공백이면 1, 공백이아니면 0 */ else return 0;} element peek(int top) { if (top == -1) { /* 스택이공백인경우 */ printf("stack is empty\n"); exit(1);} else return stack[top]; } 68
스택과큐의응용분야 스택의응용분야 시스템스택, 서브루틴호출 인터럽트처리, 컴파일러 수식의계산 순환 큐의응용분야 작업스케줄링 버퍼관리 69
스택의응용분야 (1) 시스템스택 프로그램간의호출과복귀에따른실행순서관리 항상스택의톱에는현재실행되는함수의활성화레코드존재 p : main() f 1 () f 2 () 스택 f 1 () 호출 α: end f 2 () 호출 β: end end β α 70
Factorial 순환함수 71
수식의표현 수식의표기법 중위표기 : A+B 전위표기 : +AB 후위표기 : AB+ 72
스택을이용한수식계산 (1) 수식의표기법 : A+B*C-D/E 스택을이용한후위표기식의계산 중위표기 : A+B*C-D/E 전위표기 : -+A*BC/DE 후위표기 : ABC*+DE/- 후위표기식 ABC*+DE/- AT 1 +DE/- T 2 DE/- T 2 T 3 - T 4 T 1 연산 BC* T 2 A+T 1 T 3 D/E T 4 T 2 T 3 73