그래프(Graph) 표현 그래프의 표현 방법에는 인접 행렬, 인접 리스트, 인접 배열이 존재합니다. 인접 행렬(adjacency matrix) 방법 간선 (i, j)가 존재하면 원소(i, j) = 1을 저장하며 그렇지 않으면 원소(i, j) = 0이 됩니다. 정점의 총 개수가 N이라고 할 때 인접 행렬은 N X N 행렬입니다. 무방향 그래프의 경우 대각선 행렬을 중심으로 대칭적이지만 방향 그래프의 경우 반드시 대칭적이지 않고 비대칭일 수도 있습니다. 또한 가중치가 있는 그래프의 경우 원소(i, j)는 1 대신에 가중치를 저장합니다. 인접 리스트(adjacency list) 방법 정점의 총 개수가 N이라고 할 때 각 정점에 인접한 정점들을 N개의 연결리스트로 표현한 방법입니다. i번째 리스트는 정점 i에 ..

그래프 Graph 그래프는 객체 간의 관계를 표현하는 자료구조입니다. 지도에서 지점들의 연결 상태, 도로망, 과목 선후수 관계, 전기회로의 소자 간 연결 상태, 사람들 간의 친분 관계 등을 그래프로 표현할 수 있습니다. 즉, 그래프란 현상이나 사물을 정점(vertex)과 간선(edge)로 표현한 것입니다. 그래프의 정의는 G = (V, E) 로 주어지며 V는 정점 집합, E는 간선 집합입니다. 정점(vertex) 객체를 의미하며 노드라고도 불립니다. V(G) : 그래프 G의 정점들의 집합을 의미합니다. 간선(edge) 정점들간의 관계를 의미하며 링크(link)라고도 불립니다. E(G) : 그래프 G의 간선들의 집합을 의미합니다. G1과 G2는 무방향 그래프, G3는 방향 그래프입니다. 방향성 존재 여부에..

우선순위 큐에 대하여 배워보았으니 이제 우선순위 큐를 어디에 사용하고 어떻게 응용하는 지에 대하여 알아보겠습니다. 힙 정렬(heap sort) 힙 정렬(heap sort)은 히프를 사용하는 정렬 알고리즘입니다. 먼저 정렬할 요소들을 최대 히프에 삽입하고 히프에서 하나씩 요소를 삭제하여 저장하면 정렬이 되는 방식입니다. 힙 정렬이 가장 유용한 경우는 가장 큰 값이 몇 개만 필요한 경우입니다. 힙 정렬 알고리즘 void heap_sort(element a[], int n) { int i; HeapType* h; h = create(); // 히프 생성 init(h); for (i = 0; i < n; i++) { insert_max_heap(h, a[i]); // 최대 히프로 삽입 } for (i = (n ..

fork(), exec() 함수 활용 연습문제 01-01. fork() | 부모 프로세스가 자식 프로세스 2개를 생성하고 각 자식 프로세스는 다시 자손 프로세스 2개를 생성하는 프로그램을 작성하라. [실행결과] 01-02. fork(), execl() | 프로그램 myprog1과 myprog2를 작성한 후, 조건에 따라 프로그램을 작성하라. 작성하는 프로그램명은 myexec이다. myexec의 사용법은 “$ myexec [a|b]”이다. 즉, 입력으로 ‘a’ 혹은 ‘b’를 받는다. (조건1) 파라미터로 ‘a’를 입력하면, “myprog1 14”를 수행하되, exec() 함수로는 execl()을 사용한다. (조건2) 파라메터로 ‘b’를 입력하면, “myprog2 12”를 수행하되, exec() 함수로는 e..

우선순위 큐 (priority queue) 우선순위 큐는 우선순위를 가진 항목들을 저장하는 큐입니다. 일반적으로 큐는 선입선출(FIFO)기반의 자료구조로 알려져있는데 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가게 됩니다. (ex. 구급차, 소방차가 다른 차들보다 먼저 나가는 일) 우선순위 큐의 종류에는 최소 우선순위 큐와 최대 우선순위 큐가 있으며 구현방법에는 배열, 연결리스트, 히프(heap)가 있습니다. 우선순위 큐의 구현방법 - 배열 우선 순위큐는 완전 이진 트리이므로 각 노드에 순서대로 번호를 붙일 수 있습니다. 붙여진 번호가 배열의 인덱스인 것입니다. 배열을 이용하여 트리를 구현하는 방법과 동일합니다. 배열을 이용하면 다음과 같은 규칙에 의해서 부모노드와 자식노드를 찾기가 쉽습니다. - 왼..

이진 탐색 트리 이진 트리의 핵심입니다. 탐색 트리는 탐색 작업을 효율적으로 하기 위한 자료구조입니다. 루트 노드를 기준으로 왼쪽 서브 트리의 key값은 루트 노드보다 작고 오른쪽 서브 트리의 key값은 루트 노드보다 큽니다. 따라서 이진 탐색 트리를 중위순회하면 오름차순 정렬이 됩니다. 탐색 연산 주어진 키 값이 루트 노드의 키 값과 같으면 탐색에 성공합니다. 주어진 키 값이 루트 노드의 키 값보다 작으면 왼쪽 서브트리를 탐색합니다. 주어진 키 값이 루트 노드의 키 값보다 크면 오른쪽 서브트리를 탐색합니다. 이진탐색트리에서의 탐색을 구현하는 방법으로는 순환적 방법과 반복적 방법이 있습니다. 순환적인 탐색 함수 TreeNode *search(TreeNode *node, int key) { if ( nod..

시스템 호출4 : stat(), chmod() 연습문제 01-01. 명령줄 인수로 파일 이름을 입력받아 사용자에 실행권한 'x'를 추가하는 프로그램을 작성하시오. [실행결과] 01-02. 명령줄 인수로 파일 이름을 입력받아, 그룹에 읽기권한 'r'과 쓰기권한 'w'를 추가하는 프로그램을 작성하시오. [실행결과] 01-03. 명령줄 인수로 권한과 파일 이름을 입력 받아, 그 파일의 권한을 변경하는 프로그램을 작성하시오. [실행결과]

시스템 호출3 : opendir(), readdir(), closedir(), lstat() 연습문제 01-01. 명령줄 인수로 받은 파일의 소유자와 그룹의 이름을 프린트하는 프로그램을 작성하라. 명령줄 인수로 한 개 이상의 파일을 받을 수 있어야 한다. getpwuid()와 getgrgid()를 사용하라. [실행결과] 01-02. 파일의 이름들만 출력하는 프로그램을 작성하라. 디렉토리, 문자/블록장치, FIFO, 소켓, 심볼릭링크 등은 출력되지 않고 일반파일만 출력되어야 한다. [실행결과] 01-03. 사용자 옵션에 따라 필요한 정보만을 출력하는 프로그램을 작성하라. 적어도 -s, -F, -n 옵션은 처리되도록 한다. 쉘 명령 ls -s, ls -F, ls -n과 같은 출력을 내도록 한다. 출력되는 파..

시스템 호출2 : lseek(), open(), read(), write() 연습문제 01-01. 실수 20개를 생성하여 파일에 모두 저장한 후, 이를 읽어서 출력하는 프로그램을 작성하시오. 실수는 (double)rand()/MAX_NUM으로 생성할 수 있다. 이후 이 파일로 인해 생성된 파일을 cat 명령어로 출력해 본 후 설명하라. 실행결과 01-02. 텍스트 파일의 줄들을 역순으로 바꾸어 파일로 출력하는 프로그램을 작성하라. 첫 줄이 마지막 줄이 되고 마지막 줄이 첫 줄이 되어야 한다. [실행결과]

NULL 링크에 중위 후속자 (inorder successor)를 저장시켜 놓은 이진 트리입니다. 중위 후속자란 중위 순회의 순서에서 그 다음에 이어질 차례의 노드입니다. 중위 후속자로 인해 순환 호출 없이도 중위 순회가 간편하다는 장점이 있습니다. 스레드 이진 트리 구조체 typedef struct TreeNode { int data; struct TreeNode *left, *right; int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE } TreeNode; 중위 후속자를 찾는 함수 TreeNode *find_successor(TreeNode *p) { // q는 p의 오른쪽 포인터 TreeNode *q = p->right; // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른..

시스템 호출1 : open(), close(), read(), write() 연습문제 01-01. 명령줄 인수로 받은 텍스트 파일 내의 문자의 수와 단어의 수와 줄의 수를 출력하는 프로그램을 작성한다. 명령줄 인수가 없는 경우, 표준입력에서 받은 내용을 대상으로 한다. 쉘 명령어 wc와 같은 출력 결과를 내는지 확인하라. read() 가 읽은 바이트 수가 글자 수와 같으므로 그 값을 글자수를 카운트하는 변수 chn에 저장한다. ch에는 read로 읽은 문자들이 들어있는 buffer에서 반복문을 돌려 그 값이 단어를 구분하는 조건들에 부합하고 이전 글자가 역조건에 부합하면 단어 수를 증가시킨다. 줄바꿈을 만나면 줄 수를 증가시킨다. 실행결과 01-02. 파일에 직각삼각형을 출력하는 프로그램을 작성하시오. ..

파일시스템과 파일입출력 : fread(), fseek(), fopen(), fclose(), fwrite() 연습문제 01-01. 파일 내용안의 소문자를 모두 대문자로 변경하는 프로그램을 작성하시오. 입력파일로부터 문자 하나를 받고 대문자로 변환하여 출력파일에 저장하는 방식으로 작성합니다. 입력파일은 기본적으로 열고 입력파일이 없으면 표준 출력합니다. 인자가 3인 경우 출력파일에 출력합니다. 실행결과 01-02. 텍스트 파일을 역순으로 출력하는 프로그램 ch12reverse.c를 작성하라. 파일 스트림의 끝 위치를 먼저 구해주고 1부터 끝위치까지 반복하는 반복문에서 파일 끝 위치의 바로 앞 위치에서 문자 하나를 받아서 출력파일에 저장하는 방식으로 작성한다. 실행결과