2.2 집합

충북대학교 전기전자컴퓨터공학부 알고리즘 연구실

이충세(csrhee@chungbuk.ac.kr)

목차

2.1 순서 리스트

– 2.1.1 순서 리스트의 개념

– 2.1.2 순서 리스트의 연산과 표현

2.2 집합

– 2.2.1 집합의 개념 – 2.2.2 집합의 연산 – 2.2.2 집합의 연산

2.3 배열

– 2.3.1 1차원 배열 – 2.3.2 2차원 배열

2.4 행렬

– 2.4.1 행렬의 종류

– 2.4.2 희소 행렬과 전치행렬

2.1 순서 리스트

데이터 객체가 일정한 논리적 순서로 나 열된 선형리스트

– 성적 = { } – 요일 ={월요일, 화요일,…, 일요일}

F , D , D , C , C , B , B , A ,

A

+

+

+

– 요일 ={월요일, 화요일,…, 일요일}

2.1.2 순서리스트의 연산과 표현

① 리스트의 길이 구하기

② 리스트를 오른쪽에서 왼쪽으로 읽기,또는 반대로 잃기

③ 리스트 내의 i번째에 요소를 검색(retrieval)하기

③ 리스트 내의 i번째에 요소를 검색(retrieval)하기

④ 리스트의 i번째 위치에 새로운 값을 저장(store)하 기

⑤ 리스트의 i번째 위치에 새로운 요소를 삽입(insert) 하기

⑥ 리스트 내의 i번째 위치에 요소를 삭제(delete)하기

3.1.2 순서리스트의 연산과 표현

순서 리스트를 위해 제공되는 추상적 데이터 타입

– isEmpty(): 리스트가 공백이면 true 값을 반환, 공백이 아니 면 false 값을 반환.

– size(): 리스트의 크기를 반환.

– get(index): 리스트의 index 번째의 원소 반환.

– indexOf (x): 리스트에서 첫 번째x의 index 반환,x가 없으면 –1반환.

– remove(index): index 번째의 원소를 제거하고 반환.

– add(index,x): index 번째의 x를 산입.

– out put(): 왼쪽부터 오른쪽 순으로 리스트원소를 출력.

2.2 집합

집합의 개념

– 수학, 컴퓨터 분야에 응용 – 집합 = {A, B, C}

– 부분집합

– 전집합, 교집합, 합집합, 차집합 – 보집합(complement)

• 예: 전집합={1,2,3,…, 10}

• A={1,2,3,4}, B={2,3,4,57}

3.2 집합

집합의 대해 몇 가지 연산

– NEWSET(name)

• 공집합의 생성

– ADD(element, name, added)

• 원소를 포함한 새로운 집합의 출력

• 더하고자 하는 원소가 이미 집합에 있으면 added는 “거짓”을 출력

출력

– Delete(element, name, deleted)

• 집합에서 지정하는 원소를 제거.

• 제거 되었으면 deleted는 “참”이고 ,아니면 “거짓”이 됨.

– EMTPY(name)

• 주어진 집합의 공집합 여부 검사

• 공집합이면 “참”, 아니면 “거짓”을 출력

– ISELEMENT(element, name)

• 지정하는 원소가 주어진 집합에 존재하는 가의 여부 검사

2.2 집합

집합의 연산

– Bit Map

• 전집합의 원소들이 순서화되어 있다고 가정;

• 각각의 원소에 1개의 비트를 할당;

• 어떤 집합을 나타낼 때 그 집합에 속하는 원소의 비트는

• 어떤 집합을 나타낼 때 그 집합에 속하는 원소의 비트는 1,아니면 0.

– 예: 전집합 = {A,B,C,…, Z,Y,Z}

집합 A= {B,C,F,H,K}

011001010010000000000000 집합 B= {A,C,E,G,L,K,M}

101010101010100000000000

2.3 배열

1차원 배열

– 의미: 색인과 값의 쌍의 집합 – 연산: 검색과 저장

– Java 의 선언문: int [] A=new int[10];

– Java 의 선언문: int [] A=new int[10];

– 시작주소 : Base(a)

– 각 요소의 크기 : element_size – a[i]의 위치는:

Loc(a[i])=base(a)+i*element_size

2차원 배열 A의 선언

– Object[][] A = new Object[u ₁ ,u ₂ ];

– u ₁ ,u ₂ 는 행과 열의 개수;

– Base(A)는 A[0][0]의 번지이고.

행 우선 순위

행 우선 순위

Loc(A[i,j])=base(A)+(i*u ₂ +j)*elementsize 열 우선 순위

Loc(A[i,j])=base(A)+(j*u ₁ +I)*elementsize

2.4 행렬

2.4.1 행렬의 종류

– 정방행렬: 행의 수 m 와 열의 수 같은 경우

– 희소행렬: 대부분의 요가의 값이 0 으로 구성된 행렬

– 삼각행렬: 정방 행렬의 대각선 위나 아래의 모든 요소들이 0 인 행렬.

• 하위삼각행렬

• 상위삼각행렬

– 3원 대각 행렬: 정방 행렬에서 주 대각선과 그 주 대각선 바 로 위와 아래의 대각선 요소가 0이 아닌 행렬.

– 전치행렬: 한 행렬의 행과 열을 서로 교환하여 구성되는 행 렬.

8 4 2 3 8 11 4 15 11 0 8 7 4 0 1 9

4 1 13 1 2 8 13 0 15 9 0 9 3 7 1 9

(a) (b)

희소 행렬의 표현

– 행렬은 일반적으로 2차원 배열 a[m][n]에 저장한 다.

– 희소행렬의 경우는 대부분이 0이므로 3원소로 0이 아닌 요소만을 표현한다.

아닌 요소만을 표현한다.

– 희소 행렬은 2차원 배열 a[t+1][3]에 저장한다.

• t는 0이 아닌 요소의 개수;

• 배열a의 0번째 행에는 희소 행렬의 행의 수, 열의 수, 0이 아닌 요소의 수를 각각 a[0][0],a[0][1],a[0][2]에 저 장한다.

• 행 번호 i가 증가하는 순서로 저장하면 행이 같으면 열 j 가 증가하는 순서로 저장한다

◈ 예1: 희소 행렬의 예 ◈ 예2: 3 원소로 표현한 희소 행렬 7 0 0 11 0 –7 1 2 3

0 5 1 0 0 0 a[0] 6 6 8 0 0 0 -3 0 0 a[1] 1 1 7 0 0 0 0 0 0 a[2] 1 4 11

2.4.2 희소 행렬과 전치 행렬

0 0 0 0 0 0 a[2] 1 4 11 45 0 0 0 0 0 a[3] 1 6 -7 0 0 14 0 0 0 a[4] 2 2 5 a[5] 2 3 1 a[6] 3 4 -3 a[7] 5 1 45 a[8] 6 3 14

◈ 예: 3 원소로 표현한 희소 행렬의 전치 행열

1 2 3 B[0] 6 6 8 B[1] 1 1 7 B[2] 1 5 45

◈

전치 행렬을 구하는 것 은 모든 요소의 위치 [i][j]를 [j][i]로 옮기 는 것 ,즉 행렬의 행과 열을 바꾸는 연산이다.

이 때, 대각선 상에 있

B[2] 1 5 45 B[3] 2 2 5 B[4] 3 2 1 B[5] 3 6 14 B[6] 4 1 11 B[7] 4 3 -3

이 때, 대각선 상에 있 는 요소는 i=j이므로 변 하지 않는다.

따라서 앞의 [예2]와 같이

표현된 행렬의 전치 행

렬은 다음과 같다.

전치 행렬 연산

Class Term {

private int col;

private int row;

private int value;

}

B[0].col = A[0].rowl;

B[0].value=t;

if (t > 0) { q = 1;

for (i=1; I < A[0].col; i++) for (j=1; j <= t; j++)

}

Term [] A= new Term[100];

Term [] B= new Term[100];

Public void TRANSPOSE(Term []

A, Term [] B) {

int t,i,j,q;

t = A[0].value;

B[0].row = A[0].col;

for (j=1; j <= t; j++) if A[j].col == i) {

B[q].row=A[j].col;

B[q].col=A[j].row;

B[q].value=A[j].value;

q++;

} }

}

2.4.2 희소 행렬과 전치 행렬

알고리즘 분석

– 외부 for루프가 n번 수행 – 내부 for루프가 t번 수행 – 총 수행시간: O(nt)

일반적인 2차원 배열로 표현 할 경우

일반적인 2차원 배열로 표현 할 경우

for(j=1;j<=n;j++) for(i=1;i<=m,i++) B[j,i] = A[i,j];

– 2차원 배열의 t=nm

– 총 수행시간: O(n ² m)

Void FastTransfose(Term [] A, Term [] B) { int [] s=new int[100];

int [] t=new int[100];

int i,j,n,terms;

n=A[0].col; terms=A[0].value;

B[0].row=n; B[0].col=A[0].row;

B[0].value=terms;

if (terms > 0) { for (i=0; i<n; i++)

17/18

for (i=1; i<+terms; i++) s[A[i].col]++; t[1] = 1;

for (i=2; i <= n ; i+) t[i] = t[i-1] + s[i-1];

for (i=1; i <= terms; i++) {

j = t[A[i].col]++; B[j].row = A[i].col;

A[j].col=A[i].row; B[j].value=A[i].value;

} }

알고리즘 구현 방법

 행렬 a의 각 행의 원소들의 개수를 결정함으로 써 진행된다.

 a의 원소들을 하나씩 b의 올바른 위치로 옮긴 다.

알고리즘 분석

알고리즘 분석

 O(n + t) 시간에 알고리즘 구현

 변수 사용

•

•

s = 2 1 2 2 0 1