completeness: 모든 정답 사례를 찾아낼 수 있다.

soundness: 어떠한 오답 사례도 정답 사례라고 잘못 판단하지 않는다. 

 

true/false positive/negative 개념을 동원하면 이해하기가 비교적 쉽다.

true positive = 참이라고 예측했고 실제로도 참인 경우

false positive = 참이라고 예측했으나 실제로는 거짓인 경우

false negative = 거짓이라고 예측했으나 실제로는 참인 경우

true negative = 거짓이라고 예측했고 실제로도 거짓인 경우

 

예를 들어 보자.

A B C D E F 라는 사람이 있고, A B C 는 거짓말 쟁이고, D E F는 보통 사람이라고 하자.

그리고 우리는 보통 사람을 찾아내는 알고리즘을 구현해야 한다.

 

우리가 만든 알고리즘이 completeness를 만족한다면 그 알고리즘은 반드시 D E F 에 대해서 보통 사람이라고 이야기한다. 하지만 이것이  A B C가 거짓말 쟁이임을 말하지는 않는다. 즉, completeness를 만족하지만 soundness를 만족하지 않았다면 A B C 중 최소 한 명 이상을 평범한 사람이라고 잘못 지적한 것이다. (false positive)

 

우리가 만든 알고리즘이 soundness를 만족한다면 그 알고리즘은 A B C를 평범한 사람이라고 잘못 지적하지는 않는다. 만약 soundness는 만족하지만 completeness를 만족하지 않는다면, A B C 에 대해서는 거짓말 쟁이임을 잘 찾아내지만, D E F 중에서 최소 한 명을 거짓말 쟁이라고 잘못 판단하게 될 것이다. (false negative)

 

따라서, completeness와 soundness를 전부 만족한다면, 어떠한 false 결정도 하지 않게 된다.

 

completeness 만족 & soundness 만족 => D E F 보통 사람 / A B C 거짓말 쟁이 (완벽하게 모든 사례 정답!)

completeness 만족 & soundness 불만족 => A D E F 보통 사람 / B C 거짓말 쟁이 (이 경우 A가 false positive)

completeness 불만족 & soundness 만족 => E F 보통 사람 / A B C D 거짓말 쟁이 (이 경우 D가 false negative)

저작자표시 비영리 변경금지

'컴퓨터 프로그래밍' 카테고리의 다른 글

authentication vs authorization 차이  (1) 2020.07.14
[BOJ 9078] 이웃하는 두 수만 정렬하는 문제  (0) 2020.07.14
Docker run 명령어 정리  (0) 2020.07.14
[Ubuntu 18.04 / Docker] Cannot connect to the Docker daemon at unix://XXX or tcp://XXX 에러가 날 경우  (0) 2020.03.04
Git clone 등 에서 SSL CA cert 문제가 나는 경우  (0) 2020.03.02

문제 출처: https://www.acmicpc.net/problem/9078

문제

주어진 숫자 열을 정렬하는데, 사용할 수 있는 연산은 이웃하는 두 숫자를 다른 두 수 사이나 숫자열의 맨 앞 혹은 맨 뒤에 끼워 넣는 것 뿐이다. 즉, 한 번에 숫자를 하나씩 옮기는 것이 아니라, 이웃하는 숫자를 두 개씩 묶어서 옮긴다. 4 1 5 3 2의 경우 다음과 같이 정렬할 수 있다.

4 1 5 3 2 → 3 2 4 1 5 → 3 4 1 2 5 → 1 2 3 4 5

그러나 2 1 3의 경우에는 어떻게 하더라도 정렬할 수 없다.

이와 같이 입력으로 1에서 N까지의 서로 다른 N의 정수로 구성된 숫자 열이 주어졌을 때, 그것이 위의 연산만으로 정렬가능한지 여부를 결정하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 정수 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄에는 N개의 정수가 공백을 사이에 두고 주어진다.

출력

각 테스트 케이스에 대해서 정렬 가능하면 YES를, 아니면 NO를 한 줄에 하나씩 출력한다.

 

내 해답: https://github.com/jeongmincha/solving-algorithm/blob/master/BOJ/9078.py

설명

이미 정렬 가능한 배열 = A (예를 들어 12)가 있다고 가정했을 때, 이후에 원소를 2개 추가한다고 했을 때, 그 추가되는 두 개의 숫자도 이미 정렬되어 있어야만 새로운 배열의 정답이 YES가 됩니다.
(예를 들어 12 배열에 3,4를 추가한다면->1234, 3412, 3124, 즉 3과 4는 어떤 곳에 위치하든 정렬된 상태여야만 합니다)

 

여기서 count 변수를 각 배열의 원소 뒤에 오는 다른 원소의 크기 비교를 한 값을 전부 합한 sum값이라고 합시다.
1. 1234의 경우
34가 뒤에 추가되었으나 count가 변하지 않음.
2. 3412의 경우
34가 앞에 추가되었으므로 count가 +4 (3이 12보다 크므로 +2, 4가 12보다 크므로 +2해서 총 +4)
3. 3124의 경우
3이 앞에 추가되었으므로 count가 +2 (3이 12보다 크므로 +2, 4는 뒤에 왔으므로 count 변화 없음)

즉, 기존에 이미 정렬 가능한 배열에서 새로운 원소를 추가시킬 때마다 count의 변화는 짝수로 변하게 됨.

참고로 위 사례에서는 12와 같이 짝수개의 원소 배열부터 시작했지만, 123과 같이 홀수개의 원소 배열에서 출발하더라도 같은 논리를 도출하게 됨. 또한, 태초에 12나 123같은 정렬된 배열에 대해서 count값은 0을 가지므로 어떠한 길이의 배열도 count가 짝수여야 YES가 됨.

 

블로그 백업중... https://jeongmincha.github.io/posts/00007/ 로 이동

저작자표시 비영리 변경금지

'컴퓨터 프로그래밍' 카테고리의 다른 글

authentication vs authorization 차이  (1) 2020.07.14
[컴퓨터 공학, 알고리즘] completeness vs soundness  (3) 2020.07.14
Docker run 명령어 정리  (0) 2020.07.14
[Ubuntu 18.04 / Docker] Cannot connect to the Docker daemon at unix://XXX or tcp://XXX 에러가 날 경우  (0) 2020.03.04
Git clone 등 에서 SSL CA cert 문제가 나는 경우  (0) 2020.03.02
| 문제


주어진 그래프가 만약 DAG(Directed Acyclic Graph, 방향성 비사이클 그래프)라면, 그 그래프의 꼭짓점들을 위상 정렬 하는 프로그램을 구현하라. DFS(Depth-First Search, 깊이 우선 탐색) 과정을 진행하는 동안, 작은 숫자의 꼭짓점들을 먼저 방문하도록 설계해야 한다.


입력(표준 입력)

첫 번째 에는 꼭짓점의 개수를 입력한다.

다음 줄부터, 그래프 G의 인접 리스트가 서로 연결되어 있는 꼭짓점인 x와 y로 표현되어야 한다. 이 것은 꼭짓점 x에서 꼭짓점 y로 나아가는 간선이 존재함을 의미한다.


출력(표준 출력)

첫 번째 줄에는, 주어진 그래프 G가 DAG라면 1을 출력하고, 아니면 0을 출력하게 한다.

그리고 그래프가 DAG이면 그 다음 줄에, 위상 순서대로 꼭짓점들을 출력해야 한다.


example)

입력

출력 

9

1 4

1 5

2 5

4 5

4 6

6 9

7 6

7 8

8 9

EOF 입력(윈도우에서는 Ctrl+Z)

1

7 8 3 2 1 4 6 9 5 





| 소스 코드


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

#define WHITE			0
#define GRAY			1
#define BLACK			2

#define TREE_EDGE		1
#define BACK_EDGE		2
#define FORWARD_EDGE	3
#define CROSS_EDGE	4

#define TRUE			1
#define FALSE			0

typedef struct _vertex{
	int color;
	int f;
	int d;
} Vertex;

typedef struct _VertexInfo{
	int out_degree;
	int * list;
} VertexInfo;

Vertex * vertex;
VertexInfo * vertexInfo;
int numV, time;
int * topoList;
int topo_num=0;
int isDAG = TRUE;

void addEdge(int fromV, int toV){
	int i=0;
	int cur=0;

	for(i=0; i < numV; i++)
	{
		if(vertexInfo[fromV].list[i] == 0)
			break;
		cur ++;
	}
	vertexInfo[fromV].list[cur] = toV;
}

void DFS_Visit(int fromV){
	int i=0, toV;

	/* DISCOVERED */
	time++;
	vertex[fromV].color = GRAY;
	vertex[fromV].d = time;

	for(i=0; i < vertexInfo[fromV].out_degree; i++){
		toV = vertexInfo[fromV].list[i];
		switch(vertex[toV].color)
		{
		case WHITE:
			DFS_Visit(toV);
			break;

		case GRAY:
			isDAG = FALSE;
			break;

		case BLACK:
			break;
		default:
			break;
		}
	}

	/* FINISHED */
	vertex[fromV].color = BLACK;
	topoList[numV-(topo_num++)] = fromV;
	time ++;
	vertex[fromV].f = time;
}

void Sort(int * list, int num)
{
	int i=0, j=0, tmp;

	for(i=0; i < num; i++)
	{
		for(j=i+1; j < num; j++)
		{
			if(list[i] > list[j])
			{
				tmp = list[i];
				list[i] = list[j];
				list[j] = tmp;
			}
		}
	}
}


void DFS(void)
{
	int i;
	for(i=1; i <=numV; i++)
	{
		vertex[i].d = 0;
		vertex[i].f = 0;
		vertex[i].color = WHITE;
		Sort(vertexInfo[i].list, vertexInfo[i].out_degree);
	}

	time = 0;
	for(i=1; i <=numV; i++)
	{
		if(vertex[i].color == WHITE)
		{
			DFS_Visit(i);
		}
	}
}


int main(void)
{
	int i=0, j=0;
	int fromV, toV;

	scanf("%d", &numV);

	/* INITIALIZATION START! */
	vertexInfo = (VertexInfo*)malloc(sizeof(VertexInfo)*(numV+1));
	for(i=1; i <=numV; i++){
		vertexInfo[i].list = (int*)malloc(sizeof(int)*numV);
		vertexInfo[i].out_degree = 0;
	}
	for(i=1; i <=numV; i++){
		for(j=0; j < numV; j++){
			vertexInfo[i].list[j] = 0;
		}
	}
	vertex = (Vertex*)malloc(sizeof(Vertex)*(numV+1));
	topoList = (int*)malloc(sizeof(int)*(numV+1));
	/* INITIALIZATION END! */
	

// INPUT
	while(scanf("%d %d", &fromV, &toV)!=EOF){
		addEdge(fromV, toV);
		vertexInfo[fromV].out_degree ++;
	}
	DFS();

// OUTPUT
	printf("%d\n", isDAG);
	if(isDAG)
	{
		for(i=1; i <=numV; i++)
			printf("%d ", topoList[i]);
	}

	return 0;
}


저작자표시 비영리 변경금지

'컴퓨터 프로그래밍' 카테고리의 다른 글

다차원 배열 할당시 '인접한 메모리 할당하기'  (0) 2014.02.20
배열의 이름은 포인터가 아니다?  (0) 2014.02.16
알고리즘 - Connected Component  (0) 2014.02.15
알고리즘 - Priority Queue(우선순위 큐를 구현하라)  (0) 2014.02.15
알고리즘 - Heap Sort (힙 소트(힙 정렬)를 구현하라)  (0) 2014.02.15
| 문제


비방향성 그래프 G의 커넥티드 컴포넌트를 의미하는 DFS를 구현하라. DFS 과정을 진행하는 동안, 작은 숫자를 가진 꼭짓점들을 먼저 방문하도록 설계하고, 컴포넌트 숫자는 1로 시작한다.


입력(표준 입력)

첫 번째 줄에는, 꼭짓점의 숫자 N을 입력한다.

다음 줄 부터, 그래프 G의 인접 리스트를 두 정수 x,y로 표현한다. 이것은 x로 시작해서 y로 끝나는 간선이 있음을 의미한다.


출력(표준 출력)

첫 번째 줄에는, 커넥티드 컴포넌트의 숫자를 출력한다.

다음 줄부터 N개의 줄에는, 각각의 꼭짓점의 커넥티드 숫자를 출력한다.



example)

입력 

출력 

6

1 2

1 4

2 5

3 6

2

1

1

2

1

1

2





| 소스 코드

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

#define TRUE		1
#define FALSE		0

int numV;
int * list;
int * Qlist;
int * rep;

typedef struct _vertex;

typedef struct _vertex
{
	int groupname;
	int value;
	int rank;
	struct _vertex * parent;
} Vertex;

Vertex * vertex;

void MAKE_SET(Vertex * x, int value)
{
	x->value = value;
	x->parent = x;
	x->rank = 0;
}

Vertex * FIND_SET(Vertex * x)
{
	if(x != x->parent)
		x->parent = FIND_SET(x->parent);
	return x->parent;
}

void LINK(Vertex * x, Vertex * y)
{
	if(x->rank > y->rank){
		y->parent = x;			// 랭크가 큰 놈이 부모가 되도록!
	}
	else{
		x->parent = y;
		if(x->rank == y->rank){
			y->rank = y->rank + 1;
		}
	}
}

void UNION(Vertex * x, Vertex * y)
{
	LINK(FIND_SET(x), FIND_SET(y));
}

int SAME_COMPONENT(Vertex * x, Vertex * y)
{
	if(FIND_SET(x) == FIND_SET(y))
		return TRUE;
	else
		return FALSE;
}

int main(void)
{
	int * tmp_list;
	int v1, v2;
	int i=0, j=0, tmp=0;
	int order = 0;
	int compNUM = 0;

	scanf("%d", &numV);
	vertex = (Vertex*)malloc(sizeof(Vertex)*(numV+1));
	list = (int*)malloc(sizeof(int)*(numV+1));
	tmp_list = (int*)malloc(sizeof(int)*(numV+1));
	
	for(i=1; i<=numV; i++)
		MAKE_SET(&vertex[i], i);

	while(scanf("%d %d", &v1, &v2) != EOF){	
		if(FIND_SET(&vertex[v1]) != FIND_SET(&vertex[v2])){
			UNION(&vertex[v1], &vertex[v2]);
		}
	}
	for(i=1; i<=numV; i++){
		list[i] = FIND_SET(&vertex[i])->value;
		tmp_list[i] = FIND_SET(&vertex[i])->value;
	}

	for(i=1; i<=numV; i++)
	{
		tmp = list[i];
		if(tmp != 0)
		{
			compNUM ++;
			for(j=i+1; j<=numV; j++){
				if(tmp == list[j])
					list[j] = 0;
			}
		}
	}
	Qlist = (int*)malloc(sizeof(int)*(compNUM+1));
	order = 1;
	for(i=1; i<=numV; i++){
		if(list[i] != 0){
			Qlist[order++] = list[i];
		}
	}
	for(i=1; i<=numV; i++){
		for(j=1; j<=numV; j++){
			if(tmp_list[i] == Qlist[j]){
				list[i] = j;
			}
		}
	}
	
	printf("%d\n", compNUM);
	for(i=1; i<=numV; i++)
		printf("%d\n", list[i]);

	return 0;
}


저작자표시 비영리 변경금지

'컴퓨터 프로그래밍' 카테고리의 다른 글

배열의 이름은 포인터가 아니다?  (0) 2014.02.16
알고리즘 - Topological Sort (위상 정렬)  (0) 2014.02.15
알고리즘 - Priority Queue(우선순위 큐를 구현하라)  (0) 2014.02.15
알고리즘 - Heap Sort (힙 소트(힙 정렬)를 구현하라)  (0) 2014.02.15
알고리즘 - DFS(Depth-First Search) 깊이 우선 탐색 소스 코드  (0) 2014.02.15

| 문제


입력(표준 입력)

각각의 줄에는 최대 3개의 정수들을 포함하고 있어야 한다.

3개의 입력 정수들 중,

첫 번쨰 숫자가 0이면 결과를 출력하고 프로그램을 종료한다. (terminate)

첫 번째 숫자가 1이면 두 번째 숫자를 삽입한다. (insert)

첫 번째 숫자가 2이면 가장 큰 숫자를 추출한다. (extract)

첫 번째 숫자가 3이면, 두 번째 숫자 인덱스의 원소를 세 번째 숫자로 바꾼다.

우선순위 큐의 인덱스는 1로 시작한다고 가정하자.

우선순위 큐의 최대 인덱스 값은 100000이다.


출력(표준 출력)

첫 번째 줄에, 추출된 원소들을 출력한다.

두 번째 줄에, 현재 힙을 출력한다.


example)


입력 

출력 

1 16

1 15

1 10

1 14

1 7

1 9

1 3

1 2

1 8

1 1

3 2 4

2

2

0

16 14

10 8 9 4 7 1 3 2 


| 소스 코드

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

#define minus_inf -32767

int PARENT(int index){ return index/2; }
int LCHILD(int index){ return index*2; }
int RCHILD(int index){ return index*2+1; }

void array_swap(int arr[], int a, int b)
{
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void Heapify(int arr[], int current, int length)
{
	int left, right, largest;
	left=LCHILD(current);
	right=RCHILD(current);

	if((right<=length) && (arr[right]>arr[current]))
		largest = right;
	else
		largest = current;

	if((left<=length) && (arr[left]>arr[largest]))
		largest = left;

	if(largest != current)
	{
		array_swap(arr, current, largest);
		Heapify(arr, largest, length);
	}
}

void PRINT(int arr[], int length)
{
	int i=0;
	for(i=1; i<=length; i++)
		printf("%d ", arr[i]);
}

int EXTRACT_MAX(int arr[], int length)
{
	if(length < 1)		// "heap underflow"
		return minus_inf;
	int max = arr[1];
	arr[1] = arr[length];
	length --;
	Heapify(arr, 1, length);
	return max;
}

void INCREASE_KEY(int arr[], int index, int key)
{
	int tmp=0;
	if(key < arr[index])		// not increasing, then fail.
		return;

	arr[index] = key;
	while(index>1 && arr[PARENT(index)]<arr[index])
	{
		/* EXCHANGE CURRENT WITH PARENT */
		tmp = arr[index];
		arr[index] = arr[index/2];
		arr[index/2] = tmp;

		index = PARENT(index);
	}
}

void INSERT(int arr[], int length, int key)
{
	arr[length] = minus_inf;
	INCREASE_KEY(arr, length, key);
}

int main(void)
{
	int arr[100000];
	int ext[100000];
	int length=0, extlength=0;

	int op, tmp, i;
	int index, num;

	int quit=0;

	//INSERT(arr, length, 1); length++;
	//INSERT(arr, length, 2); length++;

	while(quit==0)
	{
		scanf("%d", &op);
		switch(op)
		{
		case 0:// print
			quit=1;		// terminate this program.
			break;

		case 1:// insert
			scanf("%d", &num);
			length++;
			arr[length] = num;
			INCREASE_KEY(arr, length, num);
			break;

		case 2:// extract
			extlength++;
			ext[extlength] = arr[1];

			tmp = arr[1];
			arr[1] = arr[length];
			arr[length] = tmp;

			length--;
			Heapify(arr, 1, length);
			break;

		case 3:// replace
			scanf("%d %d", &index, &num);
			arr[index] = num;
			if(index != 1 && arr[index] > arr[PARENT(index)])
				INCREASE_KEY(arr, index, num);
			else
				Heapify(arr, index, length);
			break;
	
		default:
			break;
		}
	}

	for(i=1; i<=extlength; i++)
		printf("%d ", ext[i]);

	printf("\n");
	for(i=1; i<=length; i++)
		printf("%d ", arr[i]);

	return 0;
}


저작자표시 비영리 변경금지

'컴퓨터 프로그래밍' 카테고리의 다른 글

알고리즘 - Topological Sort (위상 정렬)  (0) 2014.02.15
알고리즘 - Connected Component  (0) 2014.02.15
알고리즘 - Heap Sort (힙 소트(힙 정렬)를 구현하라)  (0) 2014.02.15
알고리즘 - DFS(Depth-First Search) 깊이 우선 탐색 소스 코드  (0) 2014.02.15
ADC 모듈을 이용해서 측정한 광전압에 따라 반응하기 소스 코드 (HBE-MCU-All in One)  (0) 2014.02.15

| 문제


입력(표준 입력)

첫번째 줄에, 입력할 숫자들의 개수 N와 정수 k를 입력합니다.

다음줄 부터 N개의 줄만큼, 각각의 줄마다 하나의 입력 변수를 입력해야 합니다.


출력(표준 출력)

첫 번째 줄에는, 내림차순으로 가장 큰 k개의 원소들을 출력해 냅니다.

두 번째 줄에는, 가장 큰 k 원소들을 추출해낸 후에 힙을 출력해 냅니다.

 

ex) 

 

입력 

출력 

10 4

16

14

10

8

7

9

3

2

4

1

16 14 10 9

8 7 3 4 2 1 

 

 | 소스 코드 

#include <stdio.h>

void array_swap(int * arr, int a, int b)
{
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void Heapify(int * arr, int parent_position, int heap_size)
{
	int left, right, largest;
	left=2*parent_position+1;
	right=2*parent_position+2;

	if((left<heap_size)&&(arr[left]>arr[parent_position]))
		largest = left;
	else
		largest = parent_position;

	if((right<heap_size)&&(arr[right]>arr[largest]))
		largest = right;

	if(largest != parent_position)
	{
		array_swap(arr, parent_position, largest);
		Heapify(arr, largest, heap_size);
	}
}

void Build_Heap(int * arr, int length)
{
	int parent_position;

	for(parent_position=length/2-1; parent_position>=0; parent_position--)
		Heapify(arr, parent_position, length);
}

void Heap_Sort(int * arr, int length, int k)
{
	Build_Heap(arr, length);
	int last_row;
	int count = 0;

	for(last_row = length-1; last_row>0; last_row--)
	{
		if(count == k)
			break;
		array_swap(arr, 0, last_row);
		length--;
		count ++;

		Heapify(arr, 0, length);
	}
}
int main(void)
{
	int arr[100000];
	int length = 10;
	int N, k, i;

	// input
	scanf("%d %d", &N, &k);
	for(i=0; i<N; i++)
	{
		scanf("%d", &arr[i]);
	}
	Heap_Sort(arr, N, k);

	// output
	for(i=N-1; i>(N-1)-k; i--)
		printf("%d ", arr[i]);

	printf("\n");
	for(i=0; i<=(N-1)-k; i++)
		printf("%d ", arr[i]);

	printf("\n");

	return 0;
}


저작자표시 비영리 변경금지

'컴퓨터 프로그래밍' 카테고리의 다른 글

알고리즘 - Connected Component  (0) 2014.02.15
알고리즘 - Priority Queue(우선순위 큐를 구현하라)  (0) 2014.02.15
알고리즘 - DFS(Depth-First Search) 깊이 우선 탐색 소스 코드  (0) 2014.02.15
ADC 모듈을 이용해서 측정한 광전압에 따라 반응하기 소스 코드 (HBE-MCU-All in One)  (0) 2014.02.15
EEPROM을 이용한 비밀번호 시스템 만들기 소스 코드 공개 (HBE-MCU-All in One)  (0) 2014.02.15

+ Recent posts

티스토리툴바