컴퓨터 이론66 18. 희소행렬의 전치 (Fast Transpose) 이전 글에서 봐왔던 것처럼 일반적인 2차원 배열을 통한 행렬을 전치시키는 것은 O(row * col)만큼의 시간이 들어간다. 행렬이 희소행렬 표현법으로 표현된 경우 전치시키기 위해 O(col^2 * row)만큼의 시간이 들어간다. 즉, 저장 공간의 효율성을 위해 시간을 포기한 것이다. 그래서 일반적인 Transpose알고리즘 보다 빠른 전치 알고리즘을 사용한다. 희소행렬의 빠른 전치 (Fast Transpose 알고리즘) 희소행렬의 빠른 전치를 위한 알고리즘은 아래와 같다. void Fast_Transpose(term a[], term b[]){ int rowTerms[a[0].col], startingPos[a[0].col]; int i, j, numCols = a[0].col, numTerms = a.. 2023. 3. 31. 17. 희소행렬 희소행렬이란? 희소행렬이란 행렬 중에서 대부분의 원소가 0으로 이루어진 행렬을 의미한다. 이러한 행렬은 2차원 배열로 표현하기에는 비효율적이므로 효율적으로 표현하고 연산을 수행하기 위해 희소행렬 표현방법이 사용된다. 희소행렬을 표현할 때에는 0이 아닌 원소들만 저장하는 방식으로 표현된다. 희소행렬 표현 희소행렬을 표현할 때에는 표현할 원소의 행 인덱스, 열 인덱스, 원소 값을 한 번에 표현한다. typedef struct{ int row; int col; int value; }term; 행, 열, 원소 값을 한번에 저장하기 위해 구조체를 이용하여 값을 저장한다. 희소행렬의 전치 희소행렬의 예시와 표현방법 전치된 값을 보면 아래와 같다. 희소행렬 희소행렬 표현법 희소행렬 전치 15 0 0 22 0 -15 .. 2023. 3. 31. 16. 행렬 표현 2009 개정 교육과정에서부터 수학의 어려움을 줄이기 위해 행렬이 교육과정에서 제외되어 왔다 하지만 인공지능 분야 등 컴퓨터의 다양한 계산을 위해서는 행렬이 필수적으로 필요하므로 행렬에 대해서도 알아보도록 하겠다. 우리는 이미 행렬과 유사한 것을 프로그래밍에서 배워왔다. 그것은 2차원 배열이다. 행렬의 연산 방법은 수학을 공부하면서 배우도록 하고 이번 글에서는 행렬의 전치에 대해서 알아보도록 하겠다. 행렬의 구현 3X3 행렬은 2차원 배열에서 아래와 같이 구현할 수 있다. int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; 행렬의 전치 행렬의 전치란 주어진 행렬에서 행과 열의 위치를 바꾸어 새로운 행렬을 만드는 과정이다. void transpose_mat(.. 2023. 3. 31. 15. 큐 큐(Queue) 란? 큐는 데이터를 저장할 수 있는 자료구조 중 하나로 선입선출 (First In First Out) 방식으로 동작한다. 일상생활에서는 대기줄을 생각하면 된다. 먼저 줄을 선 사람이 먼저 나가고 나중에 줄을 선 사람이 나중에 나간다. 큐는 스택과 마찬가지로 배열 혹은 포인터를 이용하여 구현할 수 있다. 배열을 이용한 큐 구현 rear 변수를 통해 데이터를 삽입하고, front 변수를 통해 데이터를 꺼낸다. #include #define MAX_SIZE 100 int queue[MAX_SIZE]; int front = 0; int rear = -1; ENQUEUE 함수 큐에 데이터를 삽입하는 함수이다. 또한 배열이 가득 차 있다면 queue overflow가 발생하여 삽입되지 않는다. vo.. 2023. 3. 30. 14. 스택 스택이란? 스택은 데이터를 저장할 수 있는 자료구조 중 하나로 후입선출(Last In First Out) 방식으로 동작한다. 일상생활에서 닭꼬치를 생각하면 편할 것이다. 만들때는 먼저 넣은 것이 아래로 가게 되고 먹을 때는 나중에 넣은 것이 먼저 먹을 수 있게 된다. 스택은 배열을 이용하거나 연결리스트를 이용하여 구현할 수 있다. 배열을 이용한 스택 구현 배열을 이용한 스택을 구현할 때에는 전역변수 혹은 포인터를 이용하여 배열을 전달하면 된다. 또한 top이라는 변수를 통해 stack의 크기와 현재 스택 인덱스를 알 수 있다. #include #define MAX_SIZE 100 int stack[MAX_SIZE]; int top = -1; PUSH 함수 스택에 데이터를 삽입하는 함수이다. 또한 배열이 .. 2023. 3. 30. 13. 이중 연결리스트 지금까지 단일 연결리스트를 공부해 왔다. 단일 연결리스트는 이전 노드로 갈 수 없다는 단점이 존재하여 이전 노드로 돌아갈 수 있도록 원형으로 구성하여 어떤 노드든 참조가 가능할 수 있도록 하였다. 하지만, 현재 노드에서 바로 이전 노드를 참조하려 할 때는 모든 노드를 거쳐야 한다는 불편한 점이 존재한다. 이중 연결리스트란? 이중 연결리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가진 연결리스트이다. 이전 노드와 다음 노드를 모두 가리키기 때문에 양방향 탐색이 가능하며 삽입, 삭제가 용이하다. 노드의 구조체 정의 단일 연결리스트와는 다르게 포인터가 2개 있는 것을 확인할 수 있다. // 노드에 대한 구조체 정의 typedef struct Node *NodePointer; typedef st.. 2023. 3. 28. 이전 1 ··· 6 7 8 9 10 11 다음