선택 정렬 알고리즘 (Selection Sort) 데이터 배열을 내림차순 혹은 오름차순으로 나열하는 과정에서 사용되는 정렬 알고리즘이 존재합니다. 그 중에서 선택 정렬은 데이터 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬입니다. 1 9 4 6 11 10 3 15 2 13 위와 같은 수가 있을 때 수들을 오름차순하는 선택 정렬을 해보겠습니다. 먼저, 첫번째 원소인 1부터 마지막 원소인 13까지 반복하면서 최솟값을 찾아냅니다. 찾은 후 그 값을 배열의 맨 앞 원소와 교환하고 정렬을 확정합니다. 위 배열에서는 1이 최솟값이므로 그대로 1이 정렬로 확정됩니다. 그 다음 반복에서는 확정된 정렬을 제외한 나머지 원소 배열에서 최솟값을 찾은 후 그 값을 다시 확정된 정렬을 제외한 나머지 원소 배열의 맨 ..

pipe(), dup2(), fork() 활용 연습문제 01. pipe() | 자식 프로세스에서 부모 프로세스로 메시지 "I am your child."를 보내는 프로그램을 작성하라. 자식과 부모 프로세스는 각각 주고 받은 메시지를 출력하여야 한다. (조건1) 출력 내용은 다음과 같아야 한다. PID 101 sent -> I am your child. PID 100 received -> I am your child. [실행결과] 02. pipe() | 부모 프로세스에서 자식프로세스로 메시지 "I am your parent."를 보내는 프로그램을 작성하라. 부모와 자식 프로세스는 각각 주고 받은 메시지를 출력하여야 한다. (조건1) 출력 내용은 다음과 같아야 한다. PID 100 sent -> I am y..

signal() 함수 활용 연습문제 01. signal(), pause(), alarm() | sleep() 함수를 쓰지 않고 유사한 기능을 하는 프로그램을 구현하라. 이 프로그램은 현재 프로세스를 특정 초 동안 중지시킨다. alarm()과 pause() 시스템 호출을 이용한다. 메인 함수에서는 다음과 같이 테스트 한다. system(“date”); 작성된함수(3); system(“date”); [실행결과] 02. signal(), kill() | 시그널 SIGUSR1(10)과 SIGUSR2(12)을 받아 처리하는 프로그램을 작성하라. 이 프로그램은 기본적으로 무한 루프를 수행하면서, 시그널을 기다린다. (조건1) SIGUSR1을 받으면, “Oops! SIGUSR1!”를 출력하되 종료되지 않는다. (조건..

그래프(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 ..