Microsoft PowerPoint - Chap2 [호환 모드]

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chap2 [호환 모드]"

진혁 예
5 years ago
Views:

1 2.4 Sparse matrix ADT

2 2.4 Sparse matrix ADT 일반적으로 matrix 는 m 개의행 (row) 과 n 개의열 (column) 로구성되며, m x n (m by n 으로읽음 ) 으로표시된다. 2 차원배열에의한 matrix 의표현 (A[6,6] à A[row m, column n]) col 0 col 1 col 2 col 3 col 4 col 5 row row row row row row column n개 row m 개 예제 ) A[0, 3] == 22 A[1, 2] == 3 A[2, 3] == -6 A[4, 0] == 91 [ row, column ], 예, 0 층의 3 번방 36 개 (6*6) element 중 8 개의 element 만이 non-zero 임 à Sparse Matrix 23

3 Sparse Matrix 의표현 ((index, value), ) à 2 차원의경우는 (row, col, value) 으로표현됨 (row, col) Non-0 value Index 필드 2 차원예 ) à 3 차원의경우는 (row, col, depth, value) 으로표현됨 Index 필드 à ( (0, 3, 0.3), (1, 1, 1.1), (2, 2, 2.2), (2, 3, 2.3) ) major: row 의오름차순, minor: column 의오름차순 à 즉, 위정렬의 major 는 row 이다. (row major: 가로를기준으로삼고, 그기준에해당하는 col 을본다 ) 24

4 Sparse_Matrix ADT (2 차원 ) struct Sparse_Matrix is objects: <row, column, value>, triple들의집합, 여기서, 2차원인덱스를구성하는 row와 column은정수이고, 유일한조합을형성한다. 그리고, value는 item 집합에서온다. functions: for all a, b Sparse_Matrix, x Item, i, j, max_col, max_row index Sparse_Matrix Create (max_row, max_col) ::= max_row * max_column한 max_items을반환한다. Sparse_Matrix Transpose (a) ::= a의모든 tuple들의 row와 column을바꾼 matrix를반환한다. Sparse_Matrix Add (a, b) ::= 만약, a와 b가똑같은차수를가졌다면, 서로대응되는 item을더해서만든 matrix를반환하고, 그렇지않으면 error 리턴. Sparse_Matrix Multiply (a, b) ::= 만약, a의 column수가 b의 row 수와같다면, 다음공식에의해따라 a와 b를곱해서만든 matrix d를반환한다. 공식 : d[i][j] = (a[i][k] b[k][j]), 아니면 error 리턴. End Sparse_Matrix 25

5 Create 연산의구현방법 Sparse_Matrix Create (max_row, max_col) ::= #define MAX_TERMS 101 /* term 의최대수 +1 */ typedef struct { int row; /* row들의개수, 예, 건물의층수 */ int col; /* column들의개수, 예, 각층에서방호수 */ int value; /* 0이아닌 value들의총수 */ } term; term a [MAX_TERMS]; 다음 page 에 array a 를이용한표현예 à next page. 26

6 col 0 col 1 col 2 col 3 col 4 col 5 row row row row row row a[0].row: row 들의개수 ( 총 6 층 ) - a[0].col: column 들의개수 ( 방 6 개 ) - a[0].value: non-0 value 들의총수 a[0] [1] [2] [3] [4] [5] [6] [7] [8] array a 를이용한표현 row col value a 는 Row-major 순서를선택 27

7 Matrix 곱셈 : C = A B C A n C ij = a ik b kj k=1 i 번째 row j 번째 col. = x Row-major B Column-major K 만증가 a 11 b 11 + a 12 b 21 + a 13 b 31 + a 14 b 41 (row, col, value) triple 들의순서가 row-major order 로되었다고할때, matrix 곱셈을위해바람직한가? ( 참고 : row-major order 란, 한 row 를모두처리한후, 다음 row 를처리하는방식 ) ( 참고 : column-major order 란, 한 column 를모두처리한후, 다음 column 를처리하는방식 ) A 는 row-major order (i) 가바람직하다. (row i 를축으로한다 ) B 는 column-major order (j) 로하는것이효율적이다. (column j 를축으로한다 ) B (i, j) (j, i) B T 예 : (1, 3) x (3, 1) à (1, 3) x (1, 3) : 계산간편해짐 28

8 Matrix 변경 (transpose) A matrix row col value a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] B matrix (=A T ) row col value b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] row-major order (i 중심정렬 ) 변형하여, 새로운 row-major order 로만듦 (column 이었던 j 를 row 로변경하여재정렬 ) 29

9 Matrix 를변형하는알고리즘 void transpose (term a[ ], term b[ ]) /* b 는 a 의변형이된다 */ { int n, i, j, currentb; n = a[0].value; /* 총 element 수 */ b[0].row = a[0].col; /* b 의 col 수를 a 의 col 수와같게함 */ b[0].col = a[0].row; /* b 의 row 수를 a 의 col 수와같게함 */ b[0].value = n; if (n > 0) { /* 0 이아닌 value 가있는 element 존재수 */ currentb = 1; for (i=0; i < a[0].col; i++) /* A 에있는 col 수 만큼변경 */ for (j=1; j <= n; j++) /* A 중현재 col i 와같은 col 찾기 */ if (a[j].col == i) { b[currentb].row = a[j].col; b[currentb].col = a[j].row; b[currentb].value = a[j].value; currentb++; } } } < 알고리즘분석 > a[0].col 만큼반복 (6) a[0].value 만큼반복 (8) 시간복잡도 : O (columns elements) but, elements 의개수를알려면 : 결국, O (columns rows) 이므로, O (columns 2 rows) à Bad!, let s find fast algo. 30

10 더빨리변형할수있는알고리즘 A matrix Index: row col value a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] B matrix (=A T ) row col value b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] 순서 Starting_pos: A 의 col. Idx 값 : 이걸만들면, B 의시작주소로쓰이게된다. 1. A 행렬을읽고, row_terms 와 starting_pos 를만든다. 2. A 행렬을읽고, 특정 col.# 를가진 element 를세어서 Row_terms: B 의특정 row 의 element 로삽입하고, 삽입수만큼 starting_pos를증가시킨다. 31

11 #define MAX_COL 50 /* column 의최대수 */ void fast_transpose (term a[ ], term b[ ]) { int row_terms [MAX_COL], starting_pos [MAX_COL]; int i, j, num_cols = a[0].col, num_terms = a[0].value; b[0].row = num_cols; b[0].col = a[0].row; b[0].value = num_terms; if (num_terms > 0) { /* 0 이아닌 matrix 라면 */ for (i=0; i < num_cols; i++) row_terms [i] = 0; for (i=1; i <= num_terms; i++) row_terms [a[i].col]++; starting_pos [0] = 1; for (i=1; i < num_cols; i++) starting_pos [i] = starting_pos[i-1] + row_terms[i-1]; for (i=1; i <= num_terms; i++) { j = starting_pos[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; } } } <FAST 알고리즘분석 > 각 row terms 을위한값을구함 각 row terms 의시작점을구함 변환된행렬에옮김 각 for 루프는각각 num_cols, num_terms, num_cols-1, 그리고, num_terms 만큼수행된다. 그러므로, O (columns + elements) Worst case 시간복잡도 ( 즉, element 수가 O (columns rows)) 에서도 2 차원 array 로표현된경우최종적으로 : à O (columns rows) 32

12 2.5 다차원 array 의표현

13 다차원 array 의표현 a[upper 0 ][upper 1 ] [upper n-1 ] n-1 à element 개수는 upper i 들의곱 : upper i Row major order 와 column major order 가있다. 우리는 row major order 를학습한다. 2 차원 array :: A[upper 0 ][upper 1 ] 의경우, upper 0 는 0 부터 upper 0-1 까지의 row 가있다. (row 0, row 1,, row upper0-1 의순서로배치되어있음 ) 각각의 row 는 upper 1 개만큼의 element 를가진다. 예 : A[3][2]: 3 개의각 row 마다, 2 개씩의 column element 를가진다. 2 차원에서의주소계산방법 만약 α 가 A[0][0] 의주소라면 ( 즉, A[0][0] 는 A array 의시작주소를지칭 ), A[i][0] 의주소는 α + i upper 1 /* row 의크기가 upper 1 인 i 개의 row */ A[i][j] 의주소는 α + i upper 1 + j, 이때, 0 i < upper 0, 0 j < upper 1 c.f.) 3 차원 A[i][j][k] 의주소는? (A[upper 0 개 ][upper 1 개 ][upper 2 개 ] 라할때 ) α + (i upper 1 upper 2 )+ (j upper 2 ) + k i=0 34

14 다차원 array 에대한 intuitions Array 안에있는 element 총개수는? n-1 P upperi i=0 예 ) a[10][10][10] 변수 Upper n-1 = 변수 Upper 2 = 값은 10 à 10*10*10 = 1000 (units) Upper n-1 를예와같이 Upper 2 라고가정한다 Upper 0 Upper 1 Upper 2 starting address 이런것이 Upper 0 개예, 100개짜리가 10 개 a: a[0][0] [0] a[0][0] [1] a[0][0] [uppern-1-1] a[0][1] [0] a[0][1] [uppern-1-1] a[0][2] [0] a[1][0] [0] Upper 2 개예에서, 10개 Upper 2 개예에서, 10개 Upper 2 개예에서, 10개 이런것이 Upper 1 개예, 10개짜리가 10 개 35

15 어떻게검색할것인가? - 시작주소 + 옵셋 (offset) - 값 (value) - a 를시작주소 (starting-address) 로가정한다. 1- 차원 array a[u 0 ] 2- 차원 array a[u 0 ][u 1 ] à a[i][j] a[0]: a a[1]: a + 1 a[u 0-1]: a + (u 0-1) a[i] = a + i 0 1 u a a+1 a+(u 1-1) 1 u 0-1 i a[i][j] = a + i u1 + j cf) a[u0][u1][u2] à a[i][j][k] = a + (i u1 u2) + (j u2 ) + k cf) a[i][j][k][w] = a + (i u1 u2 u3) + (j u2 u3 ) + (k u3 ) + w j 36

16 3 차원확장 3- 차원 array a[u 0 ][u 1 ][u 2 ] a[i][j][k] = a + i u 1 u 2 + j u 2 + k = a + u 2 [i u 1 + j] + k 이제, N 차원인경우로생각 : a[u 0 ][u 1 ] [u n-1 ] a[i 0 ][i 1 ] [i n-1 ] n-1 n-1 = a +åi j a j j=0 a n-1 = 1 a j =Õu k 0 j < n-1 k=j+1 37

17 N 차원확장 ( 정리 ) Array A[upper 0 ][upper 1 ] [upper n-1 ] 에대해, α가 A[0][0] [0] 의주소이면, A[i 0 ][i 1 ] [i n-1 ] = α + i 0 upper 1 upper 2 upper n-1 + i 1 upper 2 upper 3 upper n-1 + i 2 upper 3 upper 4 upper n-1 + i n-2 upper n-1 + i n-1 a = n-1 upper, 0 j < n-1 j k n-1 = α + i j a j, 여기서 : j=0 a n-1 = 1 ( 최대차원인경우 ) 분석 :: a j 는다음차원인 a j+1 (0 j < n-1) 로부터한번의곱셈 (upper j+1 a j+1 ) 으로계산함 그러므로, 모든 a j (0 j < n-1) 를미리구해놓은다음 ( 어떻게? n-2 번의곱셈으로 ), a[i 0 ][i 1 ] [i n-1 ] 의주소를구해야할때, n-1 번의곱셈 (O(n)) 을하고, n 번의덧셈으로 a[i 0 ][i 1 ] [i n-1 ] 의주소를구할수있다. 최종적인 time complexity: O(n) k = j+1 38

18 2.6 String ADT

19 2.6 String ADT Definition: 프로그래밍언어의문자집합으로부터취해진일련의문자들 Structure String is objects : a finite set of 0 or more characters. functions: for all s, t String, i,j,m non-negative integers String Null(m) ::= 최대길이가 m 문자인스트링을반환하지만, 초기에는 NULL( ) 로초기화해서반환한다. Integer Compare(s, t)::= 만약 s 와 t 가같으면, 0 을반환하고, s 가선행하면 -1, 그렇지않으면 +1 을반환한다. Boolean IsNull(s)::= if (Compare(s, NULL)) FALSE 반환한다. else TRUE 반환한다. Integer Length(s)::= if (Compare(s, NULL)) s 안에있는문자수를반환하고, else 0 을반환한다. String Concat(s, t)::= if (Compare(t, NULL)) s 뒤에 t 를붙인것를반환하고, else 그냥 s 만을반환한다. String Substr(s, i, j)::= if ((j>0) && (i+j-1) < Length(s)) s 문자열중 i 번째부터시작해서 i+j-1 까지의문자열반환, else NULL 을반환한다. 40

20 String Insertion #include <string.h> #define MAX_SIZE 100 /* 가장큰스트링의크기 */ char string1 [MAX_SIZE] = { amobile }, *s = string1; char string2 [MAX_SIZE] = { uto }, *t = string2; strings (s, t, 1); /* 다음페이지에있는 string insertion function call */ s t a m o b i l e \0 u t o \0 temp \0 초기치 temp a \0 (a) strncpy(temp, s, 1) 수행결과 temp temp a u t o \0 (b) strcat(temp, t) 수행결과 a u t o m o b i l e \0 (c) strcat(temp, (s+1)) 수행결과 41

21 String Insertion Function void strings (char *s, char *t, int i) /* 스트링 s 중에 i 번째위치에스트링 t 를삽입한다. */ { char string[max_size], *temp = string; if (i < 0 i > strlen(s)) { fprintf(stderr, 당신이원하는위치는 array 크기를넘었습니다^^;; 다시하세요 ~ \n ); exit(1); } if (!strlen (s) ) /* 스트링 s가빈경우이므로, */ strcpy (s, t); /* s는비었으니, 그냥 t를 s에쓴다. */ else if (strlen (t)) { strncpy (temp, s, i); /* s에서 i개만큼의문자 (character) 만을 temp에 copy한다. */ strcat (temp, t); /* temp에 t를붙인, 새로운 temp를만든다. */ strcpy (s, temp): /* s를 temp로 overwrite한다. 이제 s에는 temp가들어있다.*/ } } 참고 ) strlen(s): 스트링 s의길이를반환한다. strcpy(s, t) : t를 s에복사한다. strncpy (s, t, n): n개만큼만 t를 s에복사한다. strcat (s, t) : s뒤에곧바로 t를붙인 s응만든다. 42

22 String Pattern Matching 두개의 string 이름, (1) STRING 과 (2) PAT 에서, (1) STRING 의 substring 인 (2) PAT 가시작되는위치를찾는문제 예제 ) STRING = a b c d e f g h i, PAT = g h i STRING a b c d e f g h i start = 0, PAT start = 1, PAT start = 2, PAT g h i g h i g h i Yes!! Bingo~! start index = 6 start = 3, PAT g h i start = 4, PAT g h i start = 5, PAT g h i start = 6, PAT g h i 43

23 Substring 찾는문제푸는방법들 방법 #1: 순차적검사 (Sequential examination) 방안 계산시간 : O (m n), ( 이때, m: STRING 의길이, n: PAT 의길이 ) 방법 #2: 진보된순차적검사방안 STRING 에남아있는문자개수보다 PAT 가더길면, 더이상희망이없음 : 중지! PAT 의첫문자와마지막문자만먼저 check 해나간후, 추후중간검사. 계산시간 : (m: STRING 의길이, n: PAT 의길이 ) STRING = a a a a, PAT = a a a b à O (m) But, Worst Case? O (m n) ß 어떤상황에서이렇게되는지생각해보시오! 방법 #3: No backward moving 방안 Knuth, Moris and Pratt 에의해제안됨 원 STRING 에대해서 PAT 를비교해나갈때, mismatch 가일어나도원 STRING 을다시읽지않고 (No Rescanning) STRING pointer 는 forward moving 만을계속하는방법 방법 : pattern PAT 에대해서 failure function f 를정의한후, 이를통해 skip 해도되는부분에대한검사시도를하지않는방법을사용한다. ( 자세한내용은개별학습으로한다.) 44

Chapter 4. LISTS

Chapter 4. LISTS 연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는