희소행렬과 링크드 리스트에 대해서 질문올립니다.


(Doctor) #1

안녕하세요.
여기에 글을 쓰는 것은 3번째가 되는 것 같습니다.
많은 도움을 주신덕분에 '점프 투 자바’와 '생활 코딩’영상을 접할 수있었습니다.
이제야 발을 막 디딘 기분입니다.
아직도 대소문자 구별을 안하여 오류가 나고 변수를 외우지도 못하여 예제만 따라 가고 있습니다.

그런 초짜에겐 아직 어려운 과제가 있어서 글을 올려봅니다.
여기에 올리기엔 무척이나 부끄러운 수준이지만 저에겐 미지의 함수같아 부끄러움을 무릅쓰고 올려봅니다.

본문으로 넘어가서 희소행렬의 ADT를 작성하는 과제인데, 책을 읽고 인터넷을 찾아봐도 전부 다른 구성에 코드로만 써있으니 이해가 안가 구현을 못하겠습니다.

다음 ADT를 작성하라.

  1. 희소행렬의 값을 생성하는 구문(create)
  2. 특정 위치의 값을 확인하는 구문(retrieve)
  3. 새로운 값의 저장을 하는 구문(store)
  4. 2개의 행렬의 덧셈
  5. 2개의 행렬의 뺄셈

조건 : 행렬의 특징을 나타내며 링크드 리스트의 특징 또한 보여야 한다.

교재의 배열 추상자료형을 참고하여 비슷하게 만들거나 의사코드로 작성하라 하셨는데
참고자료란

ADT Array
objects : <i∈Index, e∈Element> 쌍들의 집합. 여기서 Index는 순서를 나타내는 원소의 유한집합이며 Element는 타입이 같은 원소의 집합

배열의 객체 정의 : <i∈Index, e∈Element> 쌍들의 집합. 여기서 Index는 순서를 나타내는 정수 값이고 Element는 같은 자료형의 원소값

연산 : a∈Array; i∈Index; x, item∈Element; n∈Integer인 모든 a, item, n에 대하여 다음과 같은 연산이 정의 된다(a는 0개 이상의 원소를 갖는 배열, item은 배열에 저장되는 원소, n은 배열의 최대 크기를 정의하는 정수값)

1.Array create(n) ::= 배열의 크기가 n인 빈 배열을 생성하고 배열을 반환한다;
2.Element retrieve(a,i) ::= if (i∈Index)
then {배열의 i번쨰에 해당하는 원소값 e를 반환한다}
else {에러 메세지를 반환한다}
3.Array store(a,i,e) ::= if (i∈Index)
then {배열 a의i번째 위치에 원소값 e를 저장하고 배열 a를 반환한다;}
else {인덱스 i가 배열 a의 크기를 벗어나면 에러 메세지를 변환한다;}
End Array

이것입니다.

또한 교재의 create, retrieve, store의 의사코드는

void create(int n){
int a[n];
int i;
for(i=0, i<n, i++){
a[i] = 0;
}
}

#define array_size
int retrieve(int *a, int i){
if(i>=0&&i<array_size) return a[i];
else {printf(“Error\n”);
return(-1);}
}

#define array_size
void store(int *a, int i, int e){
if(i>=0&&i<array_size)
a[i]=e;
else printf(“Error\n”);
}

입니다. 이와 비슷하게 희소행렬의 생성 값확인 저장을 만들어줘야 하는데 감도 안잡힙니다.

아래부터는 제 나름대로 생각해본 내용입니다.
참고자료에서 반환하다라는 말의 뜻이 이해가 안가 정확한 해석을 모르겠으나
1번에서 n 크기의 배열 공간 a을 생성했고
2번에서 a배열의 i번째 위치에 원소값 e를 넣고
3번에서 i번째 위치에 원소값e를 저장했다는 말 같습니다.

또한 문제의 바탕이 되는 희소행렬이란 저장된 값보다 0이 많아서 링크드 리스트로 구현해야되는 행렬인건 알겠습니다.
링크드 리스트란 행렬에서 특정 좌표값만을 써놓은 것이란것도 알고 있습니다,
따라서 문제 1번에서 3번까지는 희소행렬의 구현 과정인것같습니다.

하지만 희소행렬(2차원 이상 행렬)의 의사코드를 만들어본적이 없어 검색하며 짜집기 형식으로 만들어봤습니다.

위의 구문을 바탕으로 2차원 행렬을 생성해보면

void create(int n){
int row;
int col;
int value;
int row[col];
int value;
for(value=0, value<n, value++){
row[col]=0}}
이 아닐까요?
하지만 이는 희소행렬이 아니라서 답이 되진못하는것같습니다
하다보니 의사코드로의 구현은 저에겐 벅찬것같아
추상데이터타입을 찾아봤습니다.

ADT SparseMatrix
Object: <row, column, value>의 집합으로 row와 column은 정수이며 value는 item 집합의 원소이다.

Functions : 모든 a, b ∈ SparseMatrix, x ∈ item, I, j, maxCol, MaxRow ∈ index에 대하여,
SparseMatrix Create(maxRow, maxCol)::=
return maxItems까지 저장 가능한 sparseMatrix
여기서 최대 행의 수는 MaxRow이고
최대 열의 수는 maxCol이라 할때
maxitems = maxRow*maxCol이다.

SparseMatrix Transpose(a) ::=
return 모든 3원소 쌍의 행과 열의 값을 교환하여 얻은 행렬

SparseMatrix Add(a,b) :: =
if a와 b의 차원이 같으면 return 대응 항들, 즉 똑같은 행과 열의 값을 가진 항들을 더해서 만들어진 행렬
else return 에러

SparseMatrix Multiply(a,b) ::=
if a의 열의 수와 b의 행의 수가 같으면
return 다음 공식에 따라 a와 b를 곱하여 생성된 행렬
else return 에러

이렇게 쓰여있었습니다. 읽어보면 이해는 가지만
이걸가지고 값확인과 저장및 덧뺄셈 작성을 못하겠습니다.
연결리스트와 희소행렬의 값확인 저장 덧밸셈 대한 ADT가 나와있는 곳을 알수없을까 하고 글을 적어봅니다.

어제 새벽부터 쓰기시작해서 여기저기 찾아다니면서 글을 내려 적은 것이라 두서없는점 죄송합니다.


(Deneb) #2

안녕하세요. 고민한 흔적이 보여 좋습니다.

참고자료에서 반환하다라는 말의 뜻이 이해가 안가 정확한 해석을 모르겠으나

‘반환하다’ 라는 건 영단어 ‘return’ 의 번역으로, 함수 안에서 값을 돌려주는 것을 말합니다.

1번에서 n 크기의 배열 공간 a을 생성했고
2번에서 a배열의 i번째 위치에 원소값 e를 넣고
3번에서 i번째 위치에 원소값e를 저장했다는 말 같습니다.

잘 이해하셨습니다. 다만 행렬은 2차원이기 때문에 (i,j) 번째 위치가 되어야겠죠. 이 점도 알고 계신 것 같습니다.

위의 구문을 바탕으로 2차원 행렬을 생성해보면 [코드] 이 아닐까요?

해당 코드는 1차원 배열을 생성하고 값을 할당하네요. 2차원으로 확장해야합니다. 다차원 배열(multidimensional array)의 선언과 사용에 대해 알아보세요.

이렇게 쓰여있었습니다. 읽어보면 이해는 가지만
이걸가지고 값확인과 저장및 덧뺄셈 작성을 못하겠습니다.

인용하신 내용을 읽어보니, 링크드 리스트에서 한 노드를 나타내는 게 Object 인 듯 합니다. Transpose와 Multiply는 필요없고 덧셈과 뺄셈은 구현할 수 있을 거라 봅니다. 즉, 다음과 같이 구현하시면 됩니다.

(출처: Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists) - GeeksforGeeks )

더 궁금하거나 잘 이해되지 않는 부분이 있다면 답글 남겨주세요.


(Doctor) #3

친절한 답변 감사드립니다. 다차원배열에 대해서 개념을 잡고 시작해야겠습니다. 링크 남겨주신 사이트에 들어가서 좀 더 고민해보고 막히면 질문드리겠습니다. 사진으로 보니 좀더 명확해 지는것같습니다. 정말 감사드립니다.


(sh) #4

@Doctor @Deneb 보기좋네요.

이런 고퀄의 질답이 많아 질 수록, 서로에게 그리고 모두에게 도움이 된다고 생각합니다.

IMG_1072


(Doctor) #6

찾아보면 찾아볼수록 방대해져서 제 무식함을 느꼈습니다.
결국 의사코드는 포기하고 예제처럼 한글문장으로 된 간단한 ADT만 만들어서 제출하기로 마음먹었습니다.
틈틈히 더 공부해야겠습니다. 도와주셔서 감사합니다.


(WilsonSmith) #7

You can refer below resource with good explanation and example on sparse matrix,


(하하아하) #8

외국인인가 ㄷㄷ


(WilsonSmith) #9

You can refer below resource which has best explanation on sparse matrix,


(프로책팔이) #10

Aren’t these two comments equivalent? Can u erase one if u don’t mind?