탐색 알고리즘

민정·2022년 4월 11일
algorithm
0

알고리즘 이론 정리

목록 보기
1/6

이진 탐색은 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 1/21/2로 나눈 두 부분 중에서 한 부분만을 검색하는 탐색 알고리즘이다.

이진 탐색으로 특정 숫자 K를 찾는 알고리즘은 아래와 같다.
1. 오름차순으로 데이터를 정렬한다.
2. 중간 숫자와 K를 비교하여
(1) 중간 숫자 == K: 탐색 성공
(2) 중간 숫자 > k: 뒷부분 반에서 다시 탐색
(3) 중간 숫자 < k: 앞부분 반에서 다시 탐색

재귀 함수로 구현한 이진 탐색 알고리즘

int BinarySearchRecur(int* list, int left, int right, int key) {
	int mid;							// 중간 숫자의 index를 저장할 변수 mid
	if (left <= right) {				// left==right인 순간까지 탐색
		mid = (left + right) / 2;		
		if (list[mid] == key) {			// 중간 숫자 == key
			return mid;
		}
		else if (list[mid] < key) {		// 중간 숫자 < key
			return BinarySearchRecur(list, mid + 1, right, key);
		}
		else {							// 중간 숫자 > key
			return BinarySearchRecur(list, left, mid - 1, key);
		}
	}
	else {
		printf("%d는 배열에 없습니다.", key);
		return -1;
	}
}

반복문으로 구현한 이진 탐색 알고리즘

int BinarySearchIter(int* list, int left, int right, int key) {
	int mid;						// 중간 숫자의 index를 저장할 변수 mid
	while (left <= right) {			// left==right인 순간까지 탐색
		mid = (left + right) / 2;
		if (list[mid] == key)		// 중간 숫자 == key
			return mid;
		else if (list[mid] < key)	// 중간 숫자 < key
			left = mid + 1;			// 앞부분 반에서 다시 탐색
		else	// 중간 숫자 > key
			right = mid - 1;		// 뒷부분 반에서 다시 탐색
	}
	printf("%d는 배열에 없습니다.", key);
	return -1;
}

전체 코드

(1) 0~99 사이의 난수로 탐색할 배열을 생성한 다음, 선택 정렬을 이용하여 오름차순으로 정렬한다.
(2) 재귀 함수와 반복문으로 구현한 이진 탐색 함수를 실행한다.
(3) 탐색한 값이 몇 번째 수인지 출력하고, 재귀 함수로 구현한 이진 탐색 함수는 탐색 횟수를 함께 출력한다.

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

void selectionSort(int* list, int length);
int BinarySearchRecur(int* list, int left, int right, int key, int*count);
int BinarySearchIter(int* list, int left, int right, int key);
int main() {
	int* count = malloc(sizeof(int)); 		// 재귀 함수로 구현한 이진 탐색의 탐색 횟수
	*count = 0;
	int* arr = malloc(sizeof(int) * 10); 	// 탐색할 배열

	if (arr == NULL) { 						// 메모리 할당에 실패한 경우
		printf("malloc error");
		exit(1);
	}

	srand(time(NULL)); 						// time을 seed로 가지는 srand함수 호출
	for (int i = 0; i < 10; i++) {
		arr[i] = rand() % 100; 				// 0~99 사이의 난수 생성
	}

	selectionSort(arr, 10); 				// 오름차순으로 정렬 (선택정렬 알고리즘 사용)
	for (int i = 0; i < 10; i++) {
		printf("%d\t", arr[i]); 			// 생성된 배열값 출력
	}
	printf("\n");
	
	int key;
	printf("키를 입력하세요: "); 				// 탐색할 값 입력 (재귀함수로 구현한 이진 탐색 사용)
	scanf_s("%d", &key);
	int index = BinarySearchRecur(arr, 0, 9, key, count)+1;
	if (index != 0) printf("%d는 %d번째 수입니다. (탐색 횟수: %d)\n", key, index, *count);

	printf("키를 입력하세요: "); 				// 탐색할 값 입력 (반복문으로 구현한 이진 탐색 사용)
	scanf_s("%d", &key);
	index = BinarySearchIter(arr, 0, 9, key) + 1;
	if (index != 0) printf("%d는 %d번째 수입니다.\n", key, index);

	free(count);
	free(arr);
}
// 선택 정렬을 이용하여 오름차순으로 정렬
void selectionSort(int* list, int length) {
	int min;									
	int temp;
	for (int i = 0; i < length - 1; i++) {
		min = i;
		for(int j=i+1; j<length; j++){
        	// i보다 뒤쪽에 list[i]보다 작은 수가 있다면, 해당 index를 min에 저장
			if (list[j] < list[min]) { 
				min = j;
			}
		}
        // 가장 작은 데이터를 선택하여 앞으로 보냄
		temp = list[min];
		list[min] = list[i];
		list[i] = temp;
	}
}
// 이진 탐색 알고리즘: 재귀 함수로 구현
int BinarySearchRecur(int* list, int left, int right, int key, int*count) {
	int mid;
	if (left <= right) {
		(*count)++;
		mid = (left + right) / 2;
		if (list[mid] == key) {
			return mid;
		}
		else if (list[mid] < key) {
			return BinarySearchRecur(list, mid + 1, right, key, count);
		}
		else {
			return BinarySearchRecur(list, left, mid - 1, key, count);
		}
	}
	else {
		printf("%d는 배열에 없습니다.", key);
		return -1;
	}
}
// 이진 탐색 알고리즘: 반복문으로 구현
int BinarySearchIter(int* list, int left, int right, int key) {
	int mid;
	while (left <= right) {
		mid = (left + right) / 2;
		if (list[mid] == key)
			return mid;
		else if (list[mid] < key)
			left = mid + 1;
		else
			right = mid - 1;
	}
	printf("%d는 배열에 없습니다.", key);
	return -1;
}

선택 알고리즘

선택 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다.

이 문제는 정렬되어 있지 않은 입력의 숫자들 중에서 피봇을 선택하여 분할하는데, 피봇보다 작은 숫자의 그룹을 small group, 피봇보다 큰 숫자의 그룹을 large group이라고 한다. 이렇게 분할했을 때 알아야 할 것은 small group의 크기이다.

만약 small group에 k번째 작은 숫자가 속했다면 small group에서 k번째 작은 숫자를 찾고,
large group에 속했다면 large group에서 (k-|small group|-1)번째로 작은 숫자를 찾아야 한다.
small group의 크기는 피봇의 인덱스 p에 대하여 |small group| = (p-1) - left +1으로 구할 수 있다.

k번째로 작은 숫자를 찾는 알고리즘을 의사코드(pseudo code)로 정리하면 아래와 같다.

findNum(A, left, right, k)
입력: A, left, right, k (단, 1<=k<=|A|, |A|=right-left+1)
출력: A[left]~A[right]에서 k번째 작은 원소
1. 피봇을 A[left]~A[right]에서 랜덤하게 선택한 후 피봇과 A[left]의 자리를 바꾼다.
2. 피봇보다 작은 숫자는 A[left]~A[p-1], 큰 숫자는 A[p+1]~A[right]로 옮기고 피봇은 A[p]에 놓는다.
3. S = (p-1)-left+1
4. if(k <= S) Selection(A, left, p-1, k)
5. else if (k = S+1) return A[p]
6. else Selection(A, p+1, right, k-S)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define SIZE 15											// 배열 길이
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

void makeArray(int* list, int length);
void printArray(int* list, int length);
int findNum(int* list, int left, int right, int k);
int main() {
	int* list = malloc(sizeof(int) * SIZE);
	int K = -1;
	srand(time(NULL));
	makeArray(list, SIZE);
	printArray(list, SIZE);

	printf("몇 번째로 작은 숫자를 검색할까요?(1~%d): ", SIZE);
	scanf_s("%d", &K);
	
	if (K != -1) {
		int K_num = findNum(list, 0, SIZE - 1, K);
		printf("%d 번째로 작은 숫자는 %d입니다.\n", K, K_num);
	}
	free(list);
}
void makeArray(int* list, int length) { 				// 배열 생성 함수
	for (int i = 0; i < length; i++) {
		list[i] = rand() % 100 + 1; 					// 1~100 난수 생성
	}
}
void printArray(int* list, int length) { 				// 배열 원소 출력 함수
	for (int i = 0; i < length; i++) {
		printf("%d\t", list[i]);
	}
	printf("\n");
}
int findNum(int* list, int left, int right, int k) {
	int pivot_index = rand() % (right - left) + left;	// 피봇 인덱스 랜덤하게 선택 (left~right 사이의 난수)
	int pivot = list[pivot_index], temp;
	int low = left;
	int high = right + 1;
	SWAP(list[left], list[pivot_index], temp);			// 피봇 <-> list[left]
	do {
		do
			low++;
		while (list[low] < pivot);						
		do
			high--;
		while (list[high] > pivot);
		if (low < high) {
			SWAP(list[low], list[high], temp);
		}
	}while (low < high);
	SWAP(list[left], list[high], temp); 
	int S = (high - 1) - left + 1; 						// small group 크기
	if (k <= S) { 										// k번째 작은 수가 small group 안에 있으면
		return findNum(list, left, high - 1, k);
	}
	else if (k == S+1) { 								// k번째 작은 수가 피봇이면
		return list[high];
	}
	else { 												// k번째 작은 수가 large group 안에 있으면
		return findNum(list, high + 1, right, k - S);
	}
}

선택 알고리즘은 피봇을 랜덤하게 정하기 때문에, 피봇을 잘못 선택하면 한 그룹에 너무 치우치게 분할되어 알고리즘의 수행 시간이 길어진다. 나쁜 분할은 두 그룹 중의 하나의 크기가 입력 크기의 3/43/4 이상인 분할을 의미하고, 좋은 분할은 그 반대의 분할을 의미한다.
예를 들어, 아래와 같이 16개의 숫자가 있다면 좋은 분할이 되는 피봇을 선택할 확률과 나쁜 분할이 되는 피봇을 선택할 확률은 1/21/2로 동일하다.

좋은 분할만 연속하여 이뤄졌다면 입력 크기가 n에서부터 3/43/4배로 연속적으로 감소되므로,
n+(3/4)n+(3/4)2n+...+(3/4)in=n[1+3/4+(3/4)2+...+(3/4)i]<=2nn + (3/4)n + (3/4)^{2}n + ... + (3/4)^{i}n= n[1 + 3/4 + (3/4)^{2} + ... + (3/4)^{i}] <= 2n이 되어 시간 복잡도는 O(n)이다.

이진 탐색과 선택 알고리즘은 부분 문제들을 취합하는 과정이 별도로 필요하지 않다는 공통점이 있다. 선택 알고리즘은 주로 중앙값(median)을 찾는데 활용한다.

이진 탐색 트리

아래와 같은 이진 탐색 트리를 생성하고, 특정 key값을 탐색하는 코드이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX(a, b) ((a)>(b))?(a):(b)
/* 노드 구조체 */
typedef struct TreeNode{
	int key;
	struct TreeNode* left, * right;
}TreeNode;
/* 노드 생성 함수 */
TreeNode* createNode(int key) {
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	node->key = key;
	node->left = node->right = NULL;
	return node;
}
/* 노드 삽입 함수 */
TreeNode* insert(TreeNode* node, int key) {
	if (node == NULL)
		return createNode(key);					// 생성한 노드의 주소를 return
	if (key < node->key) {
		node->left = insert(node->left, key); 	// 생성한 노드를 node->left에 대입
	}
	else if (key > node->key) {
		node->right = insert(node->right, key); // 생성한 노드를 node->right에 대입
	}
	else {	
		return node;							// 중복된 key값은 삽입되지 않는다.
	}
	return node; 								// 자식 노드를 추가한 root 노드를 return
}
/* 전위 순회: root->왼쪽 하위 트리->오른쪽 하위 트리 */
void preOrder(TreeNode* root) {
	if (root != NULL) {
		printf("[%d] ",root->key);			
		preOrder(root->left);
		preOrder(root->right);
	}
}
/* 중위 순회: 왼쪽 하위 트리->root->오른쪽 하위 트리*/
void inOrder(TreeNode* root) {
	if (root != NULL) {
		inOrder(root->left);
		printf("[%d] ", root->key);
		inOrder(root->right);
	}
}
/* 트리에 동적 할당된 주소 반환 */
void freeTree(TreeNode* root) {
	if (root != NULL) {
		if (root->right == NULL && root->left == NULL)
			free(root);							// 단말 노드부터 주소 반환
		freeTree(root->left);
		freeTree(root->right);
	}
}
/* 탐색 함수: key값으로 노드를 탐색한다. */
TreeNode* searchNode(TreeNode* node, int key) {
	if (node == NULL) 							// 노드를 못찾은 경우-> NULL return
		return NULL;
	if (key == node->key) {						// 노드를 찾은 경우->노드의 주소 return
		return node;
	}
	else if (key > node->key) {					// 오른쪽 하위 트리를 다시 탐색
		return searchNode(node->right, key);
	}
	else {										// 왼쪽 하위 트리를 다시 탐색
		return searchNode(node->left, key);
	}
}
int main() {
	TreeNode* root = NULL;
	root = insert(root, 35);
	root = insert(root, 68);
	root = insert(root, 35); 					// 중복되는 값은 삽입되지 않는다.
	preOrder(root);
	printf("\n");

	root = insert(root, 22);
	root = insert(root, 17);
	root = insert(root, 55);
	preOrder(root);
	printf("\n");

	root = insert(root, 30);
	root = insert(root, 34);
	root = insert(root, 65);
	preOrder(root);
	printf("\n");
	
	inOrder(root);								// 중위 순회하면 오름 차순으로 출력된다.
	printf("\n");
	
	if (searchNode(root, 67))					// key값이 67인 노드 탐색
		printf("Found\n");
	else
		printf("Not Found\n");
    
    freeTree(root);								// 동적 할당된 주소 반환
}

AVL 트리

왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1보다 크면, 노드를 재배치해준다.

  • LL 타입: 오른쪽으로 회전시킨다.
  • RR 타입: 왼쪽으로 회전시킨다.
  • LR 타입: 중간 노드를 기준으로(R인 부분) 왼쪽 회전시켜 LL 타입으로 만든 다음, 오른쪽으로 회전시킨다.
  • RL 타입: 중간 노드를 기준으로(L인 부분) 오른쪽 회전시켜 RR 타입으로 만든 다음, 왼쪽으로 회전시킨다. 
typedef struct AVLNode{
	int key;
	struct AVLNode* left, * right;
}AVLNode;

AVLNode* createNode(int key) {
	AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
	node->key = key;
	node->left = node->right = NULL;
	return node;
}
int getHeight(AVLNode* node) {
	int height = 0;
	if (node != NULL) {
		height = 1 + max(getHeight(node->left), getHeight(node->right)); // root 노드가 있는 층수까지 더하기 위해 +1
	}
	return height;
}
int getBalance(AVLNode* node) {
	if (node == NULL)
		return 0;
	return getHeight(node->left) - getHeight(node->right);
}
AVLNode* rotateRight(AVLNode* parent) {
	AVLNode* child = parent->left;
	parent->left = child->right;
	child->right = parent;
	return child;
}
AVLNode* rotateLeft(AVLNode* parent) {
	AVLNode* child = parent->right;
	parent->right = child->left;
	child->left = parent;
	return child;
}
AVLNode* insert(AVLNode* node, int key) {
	if (node == NULL)
		return createNode(key);
	if (key < node->key) {
		node->left = insert(node->left, key);
	}
	else if (key > node->key) {
		node->right = insert(node->right, key);
	}
	else {
		return node;
	}
	int balance = getBalance(node);
	/* LL */
	if (balance > 1 && key < node->left->key) {
		return rotateRight(node);
	}
	/* LR */
	if (balance > 1 && key > node->left->key) {
		node->left = rotateLeft(node->left);
		return rotateRight(node);
	}
	/* RL */
	if (balance < -1 && key < node->right->key) {
		node->right = rotateRight(node->right);
		return rotateLeft(node);
	}
	/* RR */
	if (balance < -1 && key > node->right->key) {
		return rotateLeft(node);
	}
	return node;
}
profile
민정
이전 포스트

간단한 알고리즘 문제들 모음

다음 포스트

분할 정복 알고리즘

0개의 댓글