문제
(행렬을 표현하고 싶은데, 방법이 없어서 표로 표현합니다.)
| 0 | 0 | 2 | 0 | 0 | 0 | 12 |
| 0 | 0 | 0 | 0 | 7 | 0 | 0 |
| 23 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 31 | 0 | 0 | 0 |
| 0 | 14 | 0 | 0 | 0 | 25 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 6 |
| 52 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 11 | 0 | 0 |
다음 희소행렬의 전치를 계산해라. 선형 리스트 표현을 함고하여 표현해라.
값의 대부분이 0으로 나타나는 행렬을 희소행렬이라고 하며,
행렬을 전치 시킨 후 행렬로 표현하고 싶다
행렬로 표현할때는 동적할당을 이용해라
풀이전략
1단계 : 선형 리스트를 사용하지 않고, 전치 작업을 구현하기
전치를 구현하기전 전치란 쉽게말해 행과 열을 서로 뒤바꾸는 작업을 말한다.
이는 손쉽게 구현할 수 있는데
바로 2차원 배열을 이용하는 것이다.
예시를 들어
list[3][2] 배열이 이런식으로 저장되어 있다고 하자.
| 1 | 2 |
| 3 | 4 |
| 5 | 6 |
전치를 진행하면
| 1 | 3 | 5 |
| 2 | 4 | 6 |
이런식으로 표현된다.
그러면 list[2][3] 으로 표현되는 것이다.
그러면
list[0][1] = list[1][0]
으로 표현하면 끝나겠네? 라고 생각하면 반은 성공했다.
그러나 문제가 있다.
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
a[j][i] = a[i][j];
}이렇게 코딩을 하게되면
a[i][j]의 값이 바뀌어 버린 후
포문을 돌면서 a[i][j] 를 다시 가져올때, 이전의 값이 아니라 바뀐 값을 가져오게 됩니다.
(글로 쓰는 저도 설명을 잘하고 있는지 모르겠는데, 한 번 돌려보면 감이 오실겁니다.)
그러니 행렬 b를 선언하고, b에 저장을 하면 해결됩니다.
그러면 간단하게 1번을 마무리 하죠.
int main() {
int a[8][7] = { { 0, 0, 2, 0, 0, 0, 12},
{ 0, 0, 0, 0, 7, 0, 0},
{ 23, 0, 0, 0, 0 ,0 , 0 },
{0, 0, 0 , 31, 0, 0, 0},
{0, 14, 0, 0, 0, 25, 0},
{0, 0, 0, 0, 0, 0, 6},
{52, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 11, 0, 0}
};
int b[7][8] = { 0 };
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
printf("%d \t", a[i][j]);
}
printf("\n");
}
printf("전치를 진행합니다. \n");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
b[j][i] = a[i][j];
}
printf("\n");
}
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 8; j++) {
printf("%d \t", b[i][j]);
}
printf("\n");
}
}
2단계 선형 리스트를 사용하여, 전치작업을 구현하기
이제 문제는 이겁니다.
희소행렬을 하면서 보았을 때, 0이 너무 많습니다.
이를 어떻게 표현할지 고민을 해봅시다.
| 0 | 0 | 2 | 0 | 0 | 0 | 12 |
| 0 | 0 | 0 | 0 | 7 | 0 | 0 |
| 23 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 31 | 0 | 0 | 0 |
| 0 | 14 | 0 | 0 | 0 | 25 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 6 |
| 52 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 11 | 0 | 0 |
한가지 예시를 들어봅시다.
1행 3열에 있는 수는 뭔가요?
2입니다.
그럼 이를 배열의 느낌으로 바꾸면
list[0][2] = 2 로 표현할 수 있습니다.
그러면 (0, 2, 2) 로 표현할 수 있지 않습니까
그러니 위의 행렬은 총 7x8 개의 데이터를 가지는게 아니라
10개의 데이터를 가진다고 표현할 수 있을 것 입니다.
{0, 2, 2}, {0, 6, 12}, {1, 4, 7}, {2, 0, 23}, {3, 3, 31},
{4, 1, 14}, {4, 5, 25}, {5, 6, 6}, {6, 0, 52}, {7, 4, 11}
그러면 선형리스트로 포현하는 것은 이렇게 쉽게 끝났습니다.
그러면 이상태에서 전치를 어떻게 할까?
위의 상황보다 더 쉬워집니다.
데이터의 개수만큼
{행, 열, 값} -> {열, 행, 값}
으로 바꿔주기만 하면 됩니다.
그리고 {행, 열, 값}은 배열보다는 구조체를 이용하시는게 편합니다.
#include<stdio.h>
typedef struct {
int row;
int col;
int value;
} term;
void Transpose(term a[], term b[], int len) {
for (int i = 0; i < len; i++) {
b[i].row = a[i].col;
b[i].col = a[i].row;
b[i].value = a[i].value;
}
}
void show(term b[], int len) {
for (int i = 0; i < len; i++) {
printf("(% d, % d, %d)", b[i].col, b[i].row, b[i].value);
printf("\n");
}
printf("\n");
}
int main() {
term hang[] = { {0, 2, 2}, {0, 6, 12}, {1, 4, 7}, {2, 0, 23}, {3, 3, 31},
{4, 1, 14}, {4, 5, 25}, {5, 6, 6}, {6, 0, 52}, {7, 4, 11}
};
term after[10] = { 0 };
show(hang, sizeof(hang) / sizeof(term));
Transpose( hang, after, sizeof(hang) / sizeof(term));
show(after, sizeof(after) / sizeof(term));
}
이렇게 2단계가 마무리 됩니다.
그리고 3단계로 넘어가면서 가장 큰 산이 하나 생깁니다.
3단계 : 행, 열, 값으로 표현하는거 알겠습니다. 저는 이걸 행렬로 보고 싶습니다.
이걸 해결하려고 고민을 많이 하였습니다.
가장 간단한 접근법입니다. 2차원 멀록 배열을 선언한 다음에
값을 읽어와서
a[구조체.행][구조체.열] = 구조체.값
으로 넣어버리고 이 외에는 0으로 넣어버리자.
인터넷을 참고해서 방법을 찾아봤습니다.
멀록으로 동적 배열 하나 생성
for문 (2차원 동적 변수까지 돌아라)
멀록으로 동적 배열 하나 생성
-> 결국 동적배열을 하나 생성하고 여기에 걸린 배열을 2차원 동적 변수만큼 생성한다.이런 방법으로 만들 수 있습니다.
출처
[C언어] 38. 이차원 배열의 동적 할당 (2차원 배열의 동적 할당) (tistory.com)
[C언어] 38. 이차원 배열의 동적 할당 (2차원 배열의 동적 할당)
안녕하세요. 리습입니다. 오늘은 이차원 배열(2차원 배열)의 동적 할당에 대하여 알아보도록 하겠습니다. 이 차원 배열은 기본적으론 일반적인 동적 할당의 사용방법과 동일합니다. 다만, 2차원
programfrall.tistory.com
int **arr = NULL;
arr = (int**)malloc(sizeof(int*) * 변수1);
for(int i =0; i<변수1; i++){
arr[i] = (int*)malloc(sizeof(int)*변수2);
}해당 코드를 사용해야합니다.
결국 포인터를 두 번 사용해야 합니다. (이중포인터)
제가 이상했던건지는 모르겠는데, c언어 처음배우던 예전엔 이런 생각을 했습니다.
포인터에 포인터면 원래값이 나와야하는거 아니야?
그건 아니고 이중 포인터면
주소2 -> ( 주소 -> 값 )
값을 가리키는 주소를
가리키는 주소2입니다.
(제가 이부분에서 계속 오류가 발생해서, 2차원 배열이 동작하는 예시 코드를 하나 만들고 난 후 진행하겠습니다.)
#include<stdio.h>
#include<malloc.h>
int main() {
int x = 10;
int y = 5;
int** arr = NULL;
arr = (int**)malloc(sizeof(int*) * x);
for (int i = 0; i < x; i++) {
arr[i] = (int*)malloc(sizeof(int) * y);
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 5; j++) {
arr[i][j] = 0;
}
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 5; j++) {
printf(" %d ", arr[i][j]);
}
printf("\n");
}
free(arr);
}(아마 free 에서 오류가 날 것 입니다. 오류가 난다면 지워주시면 됩니다.)
(이 부분은 후에 집중적으로 탐구해보도록하겠습니다.)
정말 간단한 코드입니다.
0으로 초기화를 하고 출력하는 것이죠.
그래서 이걸 왜 했냐구요?
우리가 사용하는 것이라면,
행렬의 크기를 직접 손수 바꿔주면 됩니다.
이걸 모르는 사람이 사용한다고 생각했을때
행렬의 크기를 의도한 것과 다르게 설정할 수도 있을 것이고,
누구는 행과 열을 입력받고, 값을 입력받고 싶어할 수 있습니다.
그렇기 때문에 범용성이 높은 코드를 작성하기 위해 동적할당을 사용했습니다.
여튼 동적할당을 받았습니다.
우선 전치가 되기 전의 행렬을 행렬형태로 표현해봅시다.
| 0 | 0 | 2 | 0 | 0 | 0 | 12 |
| 0 | 0 | 0 | 0 | 7 | 0 | 0 |
| 23 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 31 | 0 | 0 | 0 |
| 0 | 14 | 0 | 0 | 0 | 25 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 6 |
| 52 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 11 | 0 | 0 |
다시 동적할당 코드를 볼까요?
int **arr = NULL;
arr = (int**)malloc(sizeof(int*) * 변수1);
for(int i =0; i<변수1; i++){
arr[i] = (int*)malloc(sizeof(int)*변수2);
}list[변수1] 로 동적할당을 진행한 후
list[변수2][변수1] 만큼 2차원 동적할당을 진행합니다.
그러면 변수1과 변수2는 뭘까요?
행의 크기, 열의 크기입니다.
이는 사용자가 시작할 때 행렬의 크기를 입력받아올 수 있습니다.
그러나 우리는 행렬의 크기를 모릅니다.
그러나 한가지 힌트는 있죠.
위의 표의 빨간색과 파란색을 확인해보시면 끝자리에 있는 행과 열입니다.
빨간색 = 최대열번호
파란색 = 최대행번호
라고 하면 쉽게 이해가 될 것입니다.
그러면 여기까지 진행을 해볼까요?
이야기가 길어져서 요약을 하면
-> 행의크기, 열의크기를 구한다
-> 2차원 동적할당을 받은 변수 b
-> b를 0으로 초기화한다.
-> 선형리스트에 존재하는 값의 값만 바꾼다.
-> 이를 출력한다.
#include<stdio.h>
#include<malloc.h>
typedef struct {
int row;
int col;
int value;
} term;
int main() {
term hang[] = { {0, 2, 2}, {0, 6, 12}, {1, 4, 7}, {2, 0, 23}, {3, 3, 31},
{4, 1, 14}, {4, 5, 25}, {5, 6, 6}, {6, 0, 52}, {7, 4, 11}
};
int len = sizeof(hang) / sizeof(term);
int max_col = 0;
int max_row = 0;
for (int i = 0; i < len; i++) {
if (max_col < hang[i].col)
max_col = hang[i].col;
if (max_row < hang[i].row)
max_row = hang[i].row;
}
int** arr = NULL;
arr = (int**)malloc(sizeof(int*) * max_row + 1);
for (int i = 0; i < max_row + 1; i++) {
arr[i] = (int*)malloc(sizeof(int) * max_col+1);
}
for (int i = 0; i < max_col+1; i++) {
for (int j = 0; j < max_row + 1; j++) {
arr[i][j] = 0;
}
}
for (int i = 0; i < len; i++) {
arr[hang[i].col][hang[i].row] = hang[i].value;
}
for (int i = 0; i < max_col + 1; i++) {
for (int j = 0; j < max_row + 1; j++) {
printf(" %d ", arr[i][j]);
}
printf("\n");
}
}(계속 원인을 못찾고 있는데, free를 하면 오류가 발생합니다.)
아마 제 생각으로는
free에서 종료를 시킨 후
프로그램이 종료될 때 한 번 더 종료가 되어버리니 오류가 나는거 아닐까 예상을 합니다.
4단계 : 그러면 이제 전치행렬을 행렬로 보여주세요.
다른 방법은 없다. 그냥 합치자.
해당코드는 완성품이 아니다.
#include<stdio.h>
#include<malloc.h>
typedef struct {
int row;
int col;
int value;
} term;
int main() {
term hang[] = { {0, 2, 2}, {0, 6, 12}, {1, 4, 7}, {2, 0, 23}, {3, 3, 31},
{4, 1, 14}, {4, 5, 25}, {5, 6, 6}, {6, 0, 52}, {7, 4, 11}
};
term after[10] = { 0 };
int len = sizeof(hang) / sizeof(term);
int max_col = 0;
int max_row = 0;
for (int i = 0; i < len; i++) {
if (max_col < hang[i].col)
max_col = hang[i].col;
if (max_row < hang[i].row)
max_row = hang[i].row;
}
int** arr = NULL;
arr = (int**)malloc(sizeof(int*) * max_row + 1);
for (int i = 0; i < max_row + 1; i++) {
arr[i] = (int*)malloc(sizeof(int) * max_col+1);
}
for (int i = 0; i < max_col+1; i++) {
for (int j = 0; j < max_row + 1; j++) {
arr[i][j] = 0;
}
}
for (int i = 0; i < len; i++) {
arr[hang[i].col][hang[i].row] = hang[i].value;
}
for (int i = 0; i < max_col + 1; i++) {
for (int j = 0; j < max_row + 1; j++) {
printf(" %d\t", arr[i][j]);
}
printf("\n");
}
printf("\n전치를 진행 합니다. \n\n");
for (int i = 0; i < len; i++) {
after[i].row = hang[i].col;
after[i].col = hang[i].row;
after[i].value = hang[i].value;
}
for (int i = 0; i < max_col + 1; i++) {
for (int j = 0; j < max_row + 1; j++) {
arr[i][j] = 0;
}
}
for (int i = 0; i < len; i++) {
arr[after[i].col][after[i].row] = after[i].value;
}
for (int i = 0; i < max_col + 1; i++) {
for (int j = 0; j < max_row + 1; j++) {
printf(" %d\t", arr[i][j]);
}
printf("\n");
}
}
코드가 복잡하고 반복되는 부분이 있기 때문에 중복사용을 최소화 하기 위해 분리작업을 진행하였습니다.
#include<stdio.h>
#include<malloc.h>
typedef struct {
int row;
int col;
int value;
} term;
int max_col_row(term hang[], int len, bool col_row) {
int max = 0;
if (col_row == true) {
for (int i = 0; i < len; i++) {
if (max < hang[i].col)
max = hang[i].col;
}
}
if (col_row == false) {
for (int i = 0; i < len; i++) {
if (max < hang[i].row)
max = hang[i].row;
}
}
return max;
}
void show_col_row(term a[], int len, int max_col, int max_row) {
int** arr = NULL;
arr = (int**)malloc(sizeof(int*) * max_row + 1);
for (int i = 0; i < max_row + 1; i++) {
arr[i] = (int*)malloc(sizeof(int) * max_col + 1);
}
for (int i = 0; i < max_col + 1; i++) {
for (int j = 0; j < max_row + 1; j++) {
arr[i][j] = 0;
}
}
for (int i = 0; i < len; i++) {
arr[a[i].col][a[i].row] = a[i].value;
}
for (int i = 0; i < max_col + 1; i++) {
for (int j = 0; j < max_row + 1; j++) {
printf(" %d\t", arr[i][j]);
}
printf("\n");
}
}
void Transpose(term a[], term b[], int len) {
for (int i = 0; i < len; i++) {
b[i].row = a[i].col;
b[i].col = a[i].row;
b[i].value = a[i].value;
}
}
int main() {
term hang[] = { {0, 2, 2}, {0, 6, 12}, {1, 4, 7}, {2, 0, 23}, {3, 3, 31},
{4, 1, 14}, {4, 5, 25}, {5, 6, 6}, {6, 0, 52}, {7, 4, 11}
};
term after[10] = { 0 };
int len = sizeof(hang) / sizeof(term);
int max_col = max_col_row(hang, len, true);
int max_row = max_col_row(hang, len, false);
show_col_row(hang, len, max_col, max_row);
printf("\n전치를 진행 합니다. \n\n");
Transpose(hang, after, len);
show_col_row(after, len, max_col, max_row);
}
그러면 여러가지도 가능할 것입니다.
행과 열의 크기를 입력받고
행, 열, 값을 입력받아 구조체에 저장하고
전치시키는 전치 계산기를 만들 수 있을 것이라 생각합니다.
아마 여기 까지 진행했다면 이후의 과정은 그리 어렵지 않을 것이라 생각합니다.
저는 다항식 계산기 만들기에서 이미 많은 시간을 투자해봤다 생각하는 것도 있고
개인 여가시간이 필요하기 때문에
오늘은 이쯤 하도록하겠습니다.
'ㅇ 공부#언어 > (C++) 자료구조 및 STL' 카테고리의 다른 글
| 7. 이중 연결 리스트를 이용하여 삽입, 삭제, 탐색, 조회 구현하기 (0) | 2022.10.10 |
|---|---|
| 6. 단순 연결 리스트 삽입, 탐색, 삭제, 역순 구현 (0) | 2022.10.09 |
| 4. 순차(선형)리스트를 이용하여 다항식 계산기 만들기 (0) | 2022.09.15 |
| 3. 하노이탑 (0) | 2022.09.15 |
| 2. 재귀함수를 이용하여 펙토리얼 구현하기 (0) | 2022.09.15 |