단순 연결리스트를 이용한 다항식과 계산 구현 8x^12 + (-3x^10) + 10x^6과 같이 여러개인 수식을 다항식이라 부릅니다. 단순 연결리스트를 통해서 다항식을 구현할 수 있습니다. 다항식 구현에는 특수한 헤더 노드가 추가로 사용됩니다. 헤더 노드의 헤드는 리스트의 앞부분을, 테일은 리스트의 끝부분을 가리키도록 합니다. #include #include // 노드의 타입 typedef struct { int coef; int expon; struct ListNode* link; } ListNode; // 리스트 헤더의 타입 typedef struct { int size; ListNode* head; ListNode* tail; } ListType; // 오류 함수 void error(char* me..

연결리스트로 구현된 리스트 연결리스트(Linked List)는 리스트의 항목들을 노드(node)에 분산하여 저장하는 리스트입니다. 노드의 구성으로는 데이터 필드와 링크 필드가 있습니다. 데이터 필드 : 리스트의 원소, 즉 데이터 값을 저장하는 곳 링크 필드 : 다른 노드의 주소값을 저장하는 장소 (포인터) 연결리스트의 장점으로는 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없고 크기 제한이 없다는 점이 있습니다. 반면에 단점으로는 구현이 어렵고 까다로우며 오류가 발생하기 쉬운 점이 있습니다. 연결리스트의 종류에는 단순 연결리스트, 원형 연결리스트, 이중 연결리스트가 존재합니다. 단순 연결리스트는 가장 끝의 노드는 항상 NULL을 가리키게 되며 원형 연결리스트는 NULL이 위치한 곳이 없습니다. 이중..

리스트 리스트란 n개의 element형으로 구성된 순서 있는 모임을 말합니다. 리스트를 구현하는 방법에는 배열을 이용한 구현과 연결리스트를 이용한 구현이 있습니다. 리스트 Abstract Data Type insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추가한다. insert_first(list, item) ::= 맨 처음에 요소를 추가한다. delete(list, pos) ::= pos 위치의 요소를 제거한다. clear(list) ::= 리스트의 모든 요소를 제거한다. get_entry(list, pos) ::= pos 위치의 요소를 반환한다. get_length(list) ::= 리스트의 길이를 구한..

덱 Deque(Double-ended-queue) 덱(deque)은 double-ended queue의 줄임말로써 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐입니다. 덱에 사용되는 Abstract Data Type ▪ create() ::= 덱을 생성한다. ▪ init(dq) ::= 덱을 초기화한다. ▪ is_empty(dq) ::= 덱이 공백상태인지를 검사한다. ▪ is_full(dq) ::= 덱이 포화상태인지를 검사한다. ▪ add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. ▪ add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. ▪ delete_front(dq) ::= 덱..

큐 Queue 나중에 들어온 데이터가 먼저 나가는 스택 자료구조와 달리 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 선입선출(FIFO: First-In First-Out) 큐를 사용하는 방식에는 선형 큐, 원형 큐, 덱이 있습니다. 선형 큐 배열을 선형으로 사용하여 구현된 큐이며, 삽입을 계속하기 위해서는 요소들을 이동시켜야 합니다. 데이터를 넣을때마다 번거로움이 있다는 문제점이 있는 방식입니다. 또한 인덱스를 감소하지는 않고 증가만 하면서 사용하는 방식이기에, 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없기 때문에 비효율적인 부분이 있습니다. #include #include #define MAX_QUEUE_SIZE 5 typedef int element; typedef..

스택을 응용한 예시로는 괄호 검사, 스택의 응용1 : 괄호 검사 프로그램 괄호의 종류에는 대괄호 [ , ] 중괄호 { , } 소괄호 ( , ) 가 있습니다. 프로그램을 구현하기 위해 다음 조건을 만족해야 합니다. 1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 3. 괄호 사이에는 포함 관계만 존재한다. 검사가 필요해 보이는 잘못된 괄호 사용의 예시 (a(b) a(b)c) a{b(c[d]e}f) 알고리즘 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 삭제한 후 짝이 맞는지를 검사합니다. 이 때, 스택이 비어 있으면 조건1 또는 조건2 등을 위배하게 되고 괄호의 짝이..

스택(Stack) 쌓아놓은 더미, 즉 메모리가 쌓인 더미 영역을 말합니다. 스택의 특징 후입선출(LIFO:Last-In First-Out)로써 가장 최근에 들어온 데이터가 가장 먼저 나갑니다. 스택 추상 데이터 타입 (ADT) 객체: 0개 이상의 원소를 가지는 유한 선형 리스트 연산: 매개변수 s는 스택을 의미 ▪ create(size) 최대 크기가 size인 공백 스택을 생성한다. ▪ is_full(s) if(스택의 원소수 == size) return TRUE; else return FALSE; ▪ is_empty(s) if(스택의 원소수 == 0) return TRUE; else return FALSE; ▪ push(s, item) if( is_full(s) ) return ERROR_STACKFUL..

동적 메모리 할당이란 프로그램의 실행 도중에 메모리를 할당 받는 것입니다. 필요한 만큼만 할당을 받고 또 필요한 때에 사용하고 반납합니다. 이로 인해 메모리를 효율적으로 관리하고 사용이 가능합니다. 메모리 영역은 스택(Stack :: 지역변수, 매개변수), 힙(Heap :: 동적 할당), 데이터(Data :: 전역변수, static), 코드(Code, Text :: 코드, 함수, 제어문) 으로 이루어져 있는데 동적 할당의 경우 힙 영역에 저장됩니다. main() { int *pi; pi = (int *)malloc(sizeof(int)); // 동적 메모리 할당 // ... // ... 동적 메모리 사용 // ... free(pi); // 동적 메모리 반납 } C에서 동적 메모리를 사용하는 함수로 mal..

배열을 이용하여 행렬(matrix)을 표현하는 2가지 방법이 있습니다. (1) 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법 (2) 0이 아닌 요소들만 저장하는 방법 (1) 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법 이 방법의 장점은 행렬의 연산들을 간단하게 구현할 수 있다는 점이 있으며, 단점은 희소 행렬의 경우 너무 많은 메모리 공간을 낭비한다는 점이 있습니다. #include #define ROWS 3 #define COLS 3 // 행렬 전치 void matrix_transpose(int A[ROWS][COLS], int B[ROWS][COLS]) { for (int r = 0; r

함수의 매개변수로 포인터 전달 포인터는 다른 변수의 주소를 값으로 가지는 변수입니다. 포인터의 연산자 *(asterisk)는 포인터가 가리키는 값을 의미합니다. 즉, int *a = &b 로 선언했을 때 포인터 변수a는 변수b의 주소를 값으로 가지며 *a는 변수 b가 가진 값을 가리키는 것입니다. 이것을 다른 말로 'dereferncing' 한다고 말합니다. 포인터를 이야기하면 항상 나오는 개념이 배열입니다. 포인터는 배열과 매우 비슷합니다. 배열 int a[4] 를 선언했다고 합시다. 우리가 배열에 들어있는 특정 인덱스의 값에 접근하려면 a[0] = 2, a[2] = 30 등 이러한 방식으로 사용합니다. 이것은 포인터에서 *a = 2, *a = 30 과 유사합니다. 지정 영역에는 차이가 있지만 둘 다 ..

리눅스 기본 명령어 리눅스 기본 명령어 사용방법에 관한 문제들입니다. (1) 루트 디렉터리 (/) 아래의 디렉터리 구조를 cd, pwd, ls 명령어를 이용해 탐색해보자 1-1. 루트 아래의 구조를 탐색하여 두 단계 정도를 트리 모양으로 그리시오. (2) 자신이 그린 트리에서 임의의 파일 혹은 디렉터리를 지정했을 때 그 절대경로명과 상대경로명을 적어보자 2-1. ced계정의 홈 디렉터리로 갈 수 있는 절대 경로와 상대 경로를 입력하시오 >> cd /home/ced >> cd ../../home/ced 2-2. root 디렉터리안의 snap - core18 - 1988 안에 있는 디렉터리들에 접근하기 위한 절대 경로와 상대 경로를 입력하시오 >> cd /snap/core18/1988 >> ../../sna..

가상머신 사용자 계정 생성과 삭제 VMware Ubuntu 18.04 버전의 가상머신에서 작업한 내용입니다. 리눅스 명령어를 사용하여 사용자 계정을 생성하고 삭제하는 방법, 사용자 계정의 암호를 변경하는 방법을 알아보겠습니다. 01. 두 개의 계정 추가하기 root 권한을 얻어 adduser 명령어를 통해 두 개의 계정을 생성하는 과정입니다. useradd 명령어는 계정 생성은 가능했으나 계정 진입이 안되어 adduser 명령어를 사용하였습니다. 02. 추가한 두 개의 계정으로 각각 로그인 후 useradd, passwd, groupadd 등의 명령어 실행해보기 Root 권한 없이는 계정을 추가하거나 group을 생성하는 것이 불가능하고 현재 로그인 된 계정의 암호를 변경하는 것은 가능합니다. 03. 다..