가전제품 이것저것 이야기

1. 쓰레드 기법을 사용하여 공유 변수를 사용해 통신하는 생산자 / 소비자 프로그램

2. 세마포를 사용하여 공유 변수에 대해서 상호배제를 구현한 프로그램

: flag 변수를 통해 producer 의 printf가 consumer의 printf보다 항상 먼저 나오도록 구현한다.

- > mutex = 1, flag = 0으로 초기화한다.

1. 순차 탐색

: 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사한다.

1) 시간 복잡도

- 평균 비교 횟수

if 탐색 성공 : (n+1)/2

if 탐색 실패 : n번 비교

따라서 시간복잡도는 O(n)이다.

2) 코드

2. 개선된 순차 탐색

: 리스트 끝에 탐색 키를 저장한다.

(* 탐색 키 : 찾는 값 )

1) 코드

3. 이진 탐색(binary search)

1) 동작 방식

: 정렬된 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분에 배열에 있는지 알아내어

탐색의 범위를 반으로 줄여 가며 탐색을 진행한다.

2) 코드

3) 시간 복잡도

: log2(N)

4. 색인 순차탐색

: 인덱스 테이블을 사용하여 탐색의 효율을 증대시킨다.

-> 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.

1) 시간 복잡도

O( (m+n)/m )

5. 보간 탐색

: 사전이나 전화번호부를 탐색하는 방법이다.

1) 작동 방식

: 탐색 키가 존재할 위치를 예측하여 탐색한다.

이진 탐색과 유사하나, 리스트를 불균등 분할하여 탐색한다.

2) 시간 복잡도

O(log(n))

3) 탐색 위치

4) 코드

6. 균형 이진탐색트리

- 이진탐색 vs 이진탐색트리 

1) 이진탐색 : 배열 사용하므로 삽입 / 삭제가 매우 비효율

2) 이진탐색트리 : 트리를 사용하므로 삽입 / 삭제가 매우 빠르다.

3) 시간 복잡도

- 균형 트리 : O(logn)

- 불균형 트리 : O(n), 순차탐색과 동일하다.

7. AVL 트리

: 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 이진탐색트리이다.

- 트리가 비균형 상태이면 스스로 노드를 재배치하여 균형 상태로 유지시킨다.

1) 개념

균형 인수 : (왼쪽 서브트리 높이 - 오른쪽 서브트리 높이)

모든 노드의 균형 인수가 +-1 이하이면 AVL 트리이다.

2) 시간복잡도

O(logn) : 균형 트리이므로

3) 삽입 연산 시,

Ex 1) LL

Ex 2) LR

Ex 3) RL

Ex 4) RR

1. 최단 경로 

: 정점 u와 정점 v가 연결되는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로이다.

MST와 최단 경로의 차이

MST는 각 정점에 한 번씩 도달해야 하고, 총 비용은 가능한 모든 조합 중 최소여야 한다.

반면, 최단 경로는 가능한 최저 비용으로 시작 정점에서 목표 정점까지 도달하는 것이다.

알고리즘 -> 다익스트라, 플로이드

2. 다익스트라 알고리즘 - 최단경로

1) 동작 방식

2) 핵심 코드

void shortest_path(GraphType* g, int start)
{
    int i, u, w;
    
    for (i = 0; i<g->n; i++) /* 초기화 */
    {
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
        previous[i] = start;
    }
    
    found[start] = TRUE;    /* 시작 정점 방문 표시 */
    distance[start] = 0;
    
    for (i = 0; i<g->n-1; i++) {
        
        u = choose(distance, g->n, found);
        found[u] = TRUE;
        
        print_path(start, u);
        
        printf("<%d>\n", distance[u]);

        for (w = 0; w<g->n; w++){
            if (!found[w]){
                if (distance[u] + g->weight[u][w] < distance[w]){
                    distance[w] = distance[u] + g->weight[u][w];
                    previous[w] = u;
                }
            }
        }
    }
}

if (distance[u] + g->weight[u][w] < distance[w]){

                    distance[w] = distance[u] + g->weight[u][w];

                    previous[w] = u;

}

: (u까지의 거리와 u에서 w까지의 거리를 더한 것)이 (w까지의 총 거리)보다 적으면

(w까지의 총 거리)를 (u까지의 거리와 u에서 w까지의 거리를 더한 것)으로 변경한다.

3) 전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES    100
#define INF    1000000    /* 무한대 (연결이 없는 경우) */

typedef struct GraphType {
    int n;    // 정점의 개수
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int distance[MAX_VERTICES];/* 시작정점으로부터의 최단경로 거리 */
int found[MAX_VERTICES];        /* 방문한 정점 표시 */
int previous[MAX_VERTICES];
                                
int choose(int distance[], int n, int found[])      // 아직 방문하지 않은 노드들 중 가장 거리가 짧은 노드 선택
{
    int i, min, minpos;
    min = INT_MAX;
    minpos = -1;
    for (i = 0; i<n; i++)
        if (distance[i]< min && !found[i]) {
            min = distance[i];
            minpos = i;
        }
    return minpos;
}

void print_status(GraphType* g)
{
//    static int step=1;
    
//    printf("STEP %d: ", step++);
//    printf("distance: ");
    
    for (int i = 0; i < g->n; i++) {
        
        if (distance[i] == INF)
            printf(" * ");
        else
            printf("%2d ", distance[i]);
    }
    
    printf("\n");
    printf("        found:    ");
    
    for (int i = 0; i<g->n; i++)
        printf("%2d ", found[i]);
    printf("\n\n");
}

void print_path(int start, int end)     // 뒤에서부터 출력하기 위해 재귀로 구현
{
   int u = end ;
   if(start == end) {
      printf("%d -> ", start);
      return;
   }
   else {
      print_path(start, previous[u]);
      printf("%d -> ", u);
   }
}

//
void shortest_path(GraphType* g, int start)
{
    int i, u, w;
    
    for (i = 0; i<g->n; i++) /* 초기화 */
    {
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
        previous[i] = start;
    }
    
    found[start] = TRUE;    /* 시작 정점 방문 표시 */
    distance[start] = 0;
    
    for (i = 0; i<g->n-1; i++) {
        
        u = choose(distance, g->n, found);
        found[u] = TRUE;
        
        print_path(start, u);
        
        printf("<%d>\n", distance[u]);

        for (w = 0; w<g->n; w++){
            if (!found[w]){
                if (distance[u] + g->weight[u][w] < distance[w]){
                    distance[w] = distance[u] + g->weight[u][w];
                    previous[w] = u;
                }
            }
        }
    }
}

// 그래프 초기화
void graph_init(GraphType *g)
{
     // 구현
    g->n = 0;
    for(int i=0; i<MAX_VERTICES; i++){
        for(int j=0; j<MAX_VERTICES; j++){
            if(i == j){
                g->weight[i][j] = 0;
            } else {
                g->weight[i][j] = INF;
            }
        }
    }
}

void insert_edge(GraphType *g, int start, int end, int key)
{
    if( start >= g->n || end >= g->n ){
        fprintf(stderr,"그래프 : 정점 번호 오류");
        return;
    }
     
     // ƒ⁄µÂ ª¿‘
    g->weight[start][end] = key;
    g->weight[end][start] = key;
}

/*  */
void read_graph(GraphType *g, char *filename)
{
     // 구현
    int number, u, v, key;
   
    FILE *fp;
    fp = fopen(filename, "rt");
   
    if (fp == NULL)
    {
        printf("file %s open error!\n", filename);
        return;
    }
   
    fscanf(fp, "%d\n", &number);
    g->n = number;
    
    // 구현: while (fscanf(fp, "%d\n", &n) != EOF) {...} 을 사용한다.
    while(fscanf(fp, "%d\n", &u) != EOF && fscanf(fp, "%d\n", &v) != EOF && fscanf(fp, "%d\n", &key) != EOF){
       
        insert_edge(g, u, v, key);
    }

    fclose(fp);
}


int main(void)
{
    GraphType g;
    
    graph_init(&g);
    read_graph(&g, "input.txt");
    
    shortest_path(&g, 4);
    
    return 0;
}

4) 시작 정점부터 경로를 출력하기 위해 previous[u]라는 배열을 하나 더 선언하였다.

previous[u] = u 전의 노드이다.

void print_path(int start, int end)     // 뒤에서부터 출력하기 위해 재귀로 구현
{
   int u = end ;
   if(start == end) {
      printf("%d -> ", start);
      return;
   }
   else {
      print_path(start, previous[u]);
      printf("%d -> ", u);
   }
}

//
void shortest_path(GraphType* g, int start)
{
    int i, u, w;
    
    for (i = 0; i<g->n; i++) /* 초기화 */
    {
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
        previous[i] = start;
    }
    
    found[start] = TRUE;    /* 시작 정점 방문 표시 */
    distance[start] = 0;
    
    for (i = 0; i<g->n-1; i++) {
        
        u = choose(distance, g->n, found);
        found[u] = TRUE;
        
        print_path(start, u);
        
        printf("<%d>\n", distance[u]);

        for (w = 0; w<g->n; w++){
            if (!found[w]){
                if (distance[u] + g->weight[u][w] < distance[w]){
                    distance[w] = distance[u] + g->weight[u][w];
                    previous[w] = u;
                }
            }
        }
    }
}

: 처음에 previous 배열을 모두 start로 초기화시켜준다.

: 그리고 노드를 하나씩 정해갈 때마다 previous[u]값을 설정한다.

: print_path에서 재귀를 통해 뒤에서부터 출력한다.

5) 시간 복잡도

: O(n^2)

3. 플로이드 알고리즘 - 최단경로

1) 작동 방식

: 모든 정점 사이의 최단 경로를 찾는다.

:  (i 에서 j로 가는 거리)와 (i -> k + k ->j 로 가는 거리) 중에 더 짧은 경로로 간다.

2) 전체 코드

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES	100	
#define INF	1000000	/* 무한대 (연결이 없는 경우) */

typedef struct GraphType {
	int n;	// 정점의 개수
	int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int A[MAX_VERTICES][MAX_VERTICES];

void printA(GraphType *g)
{
	int i, j;
	printf("===============================\n");
	for (i = 0; i<g->n; i++) {
		for (j = 0; j<g->n; j++) {
			if (A[i][j] == INF)
				printf("  * ");
			else printf("%3d ", A[i][j]);
		}
		printf("\n");
	}
	printf("===============================\n");
}

void floyd(GraphType* g)
{

	int i, j, k;
	for (i = 0; i<g->n; i++)
		for (j = 0; j<g->n; j++)
			A[i][j] = g->weight[i][j];
	printA(g);

	for (k = 0; k<g->n; k++) {
		for (i = 0; i<g->n; i++)
			for (j = 0; j<g->n; j++)
				if (A[i][k] + A[k][j] < A[i][j])
					A[i][j] = A[i][k] + A[k][j];
		printA(g);
	}
}

int main(void)
{
	GraphType g = { 7,
	{{ 0,  7,  INF, INF,   3,  10, INF },
	{ 7,  0,    4,  10,   2,   6, INF },
	{ INF,  4,    0,   2, INF, INF, INF },
	{ INF, 10,    2,   0,  11,   9,   4 },
	{ 3,  2,  INF,  11,   0, INF,   5 },
	{ 10,  6,  INF,   9, INF,   0, INF },
	{ INF, INF, INF,   4,   5, INF,   0 } }
	};
	floyd(&g);
	return 0;
}

3) 시간 복잡도

O(n^3)

- 다익스트라 알고리즘도 모든 정점부터 시작하는 최단 경로를 구하려면 O(n^2)을 n번 반복해야 하기 때문에

시간복잡도가 O(n^3)가 된다.

4. 위상 정렬

: 방향이 있는 그래프에서 선행 순서를 위배하지 않으면서도 모든 정점을 방문하는 알고리즘이다.

1) 동작 방식

: 선수 노드가 없는 노드를 선택한다.

: 선택한 노드의 선행 관계를 삭제한다.

: 선택되지 않은 노드들 중 선수 노드가 없는 노드를 다시 선택한다.

x 모든 정점이 선택될 때까지 반복

2) 전체 코드

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

typedef struct GraphNode
{
	int vertex;
	struct GraphNode *link;
} GraphNode;

typedef struct GraphType {
	int n;	// 정점의 개수
	GraphNode *adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화 
void graph_init(GraphType *g)
{
	int v;
	g->n = 0;
	for (v = 0; v<MAX_VERTICES; v++)
		g->adj_list[v] = NULL;
}
// 정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
	if (((g->n) + 1) > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}
// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType *g, int u, int v)
{
	GraphNode *node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	node = (GraphNode *)malloc(sizeof(GraphNode));
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;
}

#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
	element stack[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init(StackType *s)
{
	s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType *s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->stack[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->stack[(s->top)--];
}

// 위상정렬을 수행한다.
int topo_sort(GraphType *g)
{
	int i;
	StackType s;
	GraphNode *node;

	// 모든 정점의 진입 차수를 계산
	int *in_degree = (int *)malloc(g->n * sizeof(int));
	for (i = 0; i < g->n; i++)			// 초기화
		in_degree[i] = 0;
	for (i = 0; i < g->n; i++) {
		GraphNode *node = g->adj_list[i];//정점 i에서 나오는 간선들
		while (node != NULL) {
			in_degree[node->vertex]++;
			node = node->link;
		}
	}
	// 진입 차수가 0인 정점을 스택에 삽입
	init(&s);
	for (i = 0; i < g->n; i++) {
		if (in_degree[i] == 0) push(&s, i);
	}
	// 위상 순서를 생성 
	while (!is_empty(&s)) {
		int w;
		w = pop(&s);
		printf("정점 %d ->", w);		//정점 출력
		node = g->adj_list[w];	//각 정점의 진입 차수를 변경
		while (node != NULL) {
			int u = node->vertex;
			in_degree[u]--;			//진입 차수를 감소
			if (in_degree[u] == 0) push(&s, u);
			node = node->link;   // 다음 정점
		}
	}
	free(in_degree);
	printf("\n");
	return (i == g->n);	// 반환값이 1이면 성공, 0이면 실패
}
//	
int main(void)
{
	GraphType g;

	graph_init(&g);
	insert_vertex(&g, 0);
	insert_vertex(&g, 1);
	insert_vertex(&g, 2);
	insert_vertex(&g, 3);
	insert_vertex(&g, 4);
	insert_vertex(&g, 5);

	//정점 0의 인접 리스트 생성
	insert_edge(&g, 0, 2);
	insert_edge(&g, 0, 3);
	//정점 1의 인접 리스트 생성
	insert_edge(&g, 1, 3);
	insert_edge(&g, 1, 4);
	//정점 2의 인접 리스트 생성
	insert_edge(&g, 2, 3);
	insert_edge(&g, 2, 5);
	//정점 3의 인접 리스트 생성
	insert_edge(&g, 3, 5);
	//정점 4의 인접 리스트 생성
	insert_edge(&g, 4, 5);
	//위상 정렬 
	topo_sort(&g);
	// 동적 메모리 반환 코드 생략
	return 0;
}

1. 동시성 제어 기법

1) 잠금 -> 대부분 이 방법 사용

: 트랜잭션의 실행 순서를 강제로 제어한다.

2) 타임스탬프

: 최대한 병행 수행을 보장하나,

: 직렬 가능한 스케줄에 위배될 가능성이 있으면 실행 취소한다.

2. 잠금

: 하나의 트랜잭션을 수행하는 동안 특정 데이터 항목에 대해 다른 트랜잭션이 동시에 접근하지 못하도록 하는 기법이다.

1) 공유 잠금 (S-lock)

2) 배타 잠금 (X-lock)

1. 동시성 제어

: 다중 사용자 DBMS에서 필요하다.

: 동시에 실행되는 트랜잭션들 간에 간섭이 발생하여 일관성이 깨지지 않도록 트랜잭션 실행 순서를 제어하는 기법이다.

2. 트랜잭션에서의 연산

1) read(x)

: 이름이 x인 데이터베이스 항목을 트랜잭션의 지역변수 x로 읽어들인다.

x는 테이블, 레코드, 필드 등

2) write(x)

: 지역변수 x에 저장된 값을 데이터베이스 항목 x에 저장한다.

** write 연산 수행 시 그 결과가 디스크에 저장될 수도 있고 그렇지 않을 수도 있다.

대부분의 dbms는 성능 향상을 위해 메모리 buffer를 사용한다.

3. 동시성 제어가 필요한 이유

: 트랜잭션들에 정의된 명령들 간 끼어들기가 가능하다.(interleaving)

- 스케줄

: 끼어들기 방식에 의해 실행되는 순서

: 스케줄은 전적으로 운영체제의 권한이다.

: 사용자는 어떠한 스케줄로 트랜잭션들이 실행되는지 미리 예측하기 어렵다.

- 끼어들기 방식의 문제점

: 서로간의 간섭에 의해서 잘못된 데이터를 생성할 수 있다.

: 갱신 분실, 연쇄 복귀, 불일치 분석 현상이 발생가능하다.

4. 갱신 분실

T1이 read를 수행하고 write 하기 전에 T2가 read를 다시 수행하면 x값이 overwrite 되어서 사라진다.

5. 연쇄 복귀

: T3가 복귀(rollback)하면 T4에서 한 수행도 복귀되어야 한다.

but T4가 이미 완료된 이후라면 복귀 불가능하다.(지속성 위배)

완료되지 않은 트랜잭션의 쓰기 연산에 의해 갱신된 데이터를 다른 트랜잭션이 읽었기 때문에 (dirty read)

6. 불일치 분석

7. 끼어들기로 인한 문제점 해결방안

1) 트랜잭션들을 하나씩 순차적으로 실행한다.

2) 직렬 스케줄 생성 -> 시스템 성능 저하 발생

3) 직렬 가능한 스케줄 생성 -> 끼어들기를 최대한 허용하면서 직렬 스케줄과 동일한 결과를 갖도록 실행 순서를 제어한다.

6. 직렬 스케줄

: 각 트랜잭션의 연산들이 끼어들기 방식으로 실행되지 않고, 순차적으로 실행되는 스케줄이다.

7. 직렬 가능한 스케줄

: 직렬 스케줄과 실행 결과가 동일한 스케줄이다.

- 직렬 가능한 스케줄인지 판단하는 방법

: 스케줄에 나타난 연산들의 순서를 바꿔 직렬 스케줄을 만들 수 있으면 직렬 가능한 스케줄이다.

ex) C1와 C2의 실행 순서를 바꿔 직렬 스케줄로 만들 수 있들 수 있으면 직렬 가능 스케줄

- C1, C2의 실행 순서를 바꿀  수 있는 경우

: C1과 C2가 서로 다른 데이터 항목에 대한 연산일 경우 -> 교환 가능하다.

: C1과 C2가 같은 데이터 항목이지만,

C1과 C2가 모두 read 연산일 경우, -> 교환 가능하다.

C1과 C2 중 하나라도 write 연산일 경우, -> 교환 불가능하다.

1) 직렬 스케줄로 변환 가능한 경우

2) 직렬 스케줄로 변환 불가능한 경우

: 직렬 스케줄로 바꾸기 위해서는 (1)과 (4)의 순서를 바꾸거나 (2)와 (3)의 순서를 바꿔야 하는데,

같은 데이터이고 write 가 들어가기 때문에 바꿀 수 없다.

1. 트랜잭션이란?

: 하나의 논리적인 작업 단위를 구성하는 연산들의 집합이다.

: 실행 중 멈추거나 중단되지 않는 최소 작업 단위

: 데이터베이스 응용 프로그램은 트랜잭션의 집합이다.

1) 트랜잭션의 예 1

-> 만약 이체 업무 중간에 멈춘다면?

계좌에 잘못된 정보가 저장되므로 

모든 연산을 완벽히 수행하던지, 아예 처음상태로 돌아가던지 해야 한다. -> all or nothing

2) 트랜잭션의 예 2

: 다중 사용자 환경에서 트랜잭션이 동시에 실행되는 다른 트랜잭션에 의해 영향을 받는다.

- 예금 인출이 동시에 두 지점에서 이루어진다면 오류가 발생한다.

3) 따라서,

앞의 상황이 발생하지 않도록 사전에 DBMS에서 트랜잭션 처리 기능을 갖춰야 한다.

2. 트랜잭션이 지켜야 할 조건

- ACID 특성

Atomicity(원자성)

:  트랜잭션에서 정의된 연산들은 모두 성공적으로 실행되던지, 아니면 실행 전 상태로 되돌아가야 한다.(all-or-nothing)

Consistency(일관성)

: 트랜잭션 실행 전과 후에 데이터베이스 내용이 일관성이 있어야 한다.

Isolation(고립성)

: 트랜잭션이 실행되는 과정에서 갱신된 데이터는 그 트랜잭션이 완료될 때까지 다른 트랜잭션이 참조할 수 없다.

Durability(지속성/영속성)

: 트랜잭션이 성공적으로 완료되면 그 갱신된 내용은 영구적으로 

1) 원자성 : 트랜잭션은 성공하거나 실패하거나 둘 중 하나!

-> 실패하더라도 원래 상태로 되돌려놔야 한다.

2) 일관성 : 계좌이체 전과 후의 두 계좌의 잔액의 합은 동일해야 한다.

3) 고립성 : 트랜잭션이 완료될 때까지 다른 트랜잭션이 참조하지 못하게 하는 특성이다.

* 고립성이 만족되는지 확인하려면? 

- 동시에 실행하는 트랜잭션들의 실행 결과가 순차적으로 실행된 결과와 동일한지 확인하면 된다.

* 해결 방법 *

- 각 트랜잭션을 순차적으로 실행한다. 다만, 다중 프로그래밍 환경에서 순차적으로 하는 것은 성능 면에서 문제 발생한다.

- 상호 간의 간섭이 일어나지 않도록 하는 기법이 필요하다.

4) 지속성 : 트랜잭션이 성공적으로 완료되면 그 갱신된 내용은 영구적으로

3. 트랜잭션 상태 전이

- 동작 : 트랜잭션이 시작되고 연산들이 정상적으로 실행중인 상태

- 부분완료 : 트랜잭션에 정의된 모든 연산의 실행이 끝난 상태

- 완료 : 트랜잭션이 성공적으로 종료된 상태

- 실패 : 트랜잭션이 성공적으로 완료되지 않고 더 이상 실행되지 못 하는 상태

- 중단 : 실행 이전으로 복귀된 상태