[자료구조] 1-3. 알고리즘 예시 & 재귀 함수 (C/C++)

[알고리즘 예시] Selection Sort 선택 정렬

• 문제 : Sort a set of n ≥ 1 integers in non-decreasing order
• 방법 : from those integers that are currently unsorted, find the smallest and place it next in the sorted list
• pseudocode algorithm
  • for(i = 0; i < n - 1; i++){
    1. list[i]와 list[n-1] 비교 / 가장 작은 값은 list[min]에 대입
    2. list[i]와 list[min] 교환 }

#define SWAP(x, y, t) \\
	((t)=(x), (x)=(y), (t)=(t))

void sort(int list[], int n){
	int i, j, min, tmp;
	
	for(i = 0; i < n - 1; i++){
		min = i;
		for(j = i + 1; j < n; j++){
			if(list[j] < list[min])
				min = j;
		}
		SWAP(list[i], list[min], tmp);
	}
}

 

 

[알고리즘 예시] Binary Search 이진 검색

• find out if an integer key exists in the list L of n integers sorted in non-decreasing order.
• If so, return i such that L[i] = key. Otherwise, return -1.
• 방법 : L[mid]와 key 값을 계속해서 비교
  • left = L[0], right = L[n - 1]
  • mid = (left + right) / 2
  • 반복
    1. key < L[mid]
       1. key가 left와 L[mid - 1] 사이에 위치
       2. right = L[mid - 1]
    2. key == L[mid]
       1. 발견!!
       2. return mid
    3. key > L[mid]
       1. key가 L[mid + 1]과 right 사이에 위치
       2. left = L[mid + 1]

// C function (using if)

int binsearch1(int L[], int key, int left, int right){
	// L은 non-decreasing order로 정렬되어 있다고 가정
	// 발견 시 위치 반환
	// 그렇지 못하면 -1 반환
	int mid;

	while (left <= right){
		mid = (left + right) / 2;
		if (key < L[mid])
			right = mid - 1;
		else if (key == L[mid])
			return mid;
		else
			left = mid + 1;
	}

	return -1;
}

// C function (using switch)

#define COMPARE(x, y) \
((x)<(y) ? -1 : ((x)==(y)) ? 0 : 1)

int binsearch2(int L[], int key, int left, int right){
	int mid;
	while (left <= right){
		mid = (left + right) / 2;
		
		switch (COMPARE(L[mid], key)){
			case -1: left = mid + 1; break;
			case 0: return mid;
			case 1: right = mid - 1;
		}
	}

	return -1;
}

 

 

[알고리즘 예시] Binary Search 이진 검색 - 재귀 함수

// recursive version (재귀 함수 활용)
#define COMPARE(x, y) \\
	((x)<(y) ? -1 : ((x)==(y)) ? 0 : 1)

int binsearchR(int L[], int key, int left, int right){
	int m;
	if (left <= right){
		m = (left + right) / 2;
		
		switch (COMPARE(L[m], key)){
			case -1: return binsearchR(L, key, m + 1, right);
			case 0: return m;
			case 1: return binsearchR(L, key, left, m - 1);
		}
	}

	return -1;
}

// iterative version

#define COMPARE(x, y) \
((x)<(y) ? -1 : ((x)==(y)) ? 0 : 1)

int binsearch2(int L[], int key, int left, int right){
	int mid;
    
    while (left <= right){
    	mid = (left + right) / 2;
        switch (COMPARE(L[mid], key)){
        	case -1: left = mid + 1; break;
            case 0: return mid;
            case 1: right = mid - 1;
		}
	}
    
    return -1;
}

 

[알고리즘 예시] Permutation 순열 - 재귀 함수

// recursive permutation printing function
#define SWAP(x, y, t) \
((t)=(x), (x)=(y), (t)=(t))

void permutation(char* L, int i, int n){
// char list[6] = "abcde"; 일 경우,
// 다음과 같이 호출 permutation(list, 0, 5);

	int j, temp;
	
	if (i == n - 1){
		for(j = 0; j < n; j++)
			printf("%c", L[j]);
		printf("\n");
	}
	else {
		for(j = i; j < n; j++){
			SWAP(L[i], L[j], temp);
			permutation(L, i + 1, n);
			SWAP(L[i], L[j], temp);
		}
	}
}

 

 

[알고리즘 예시 ] Binomial coefficient 조합 - 재귀 함수

int BinomialR(int n, int m){
	if (m < 0 || m > n) return 0;
	else if (n == 0 && m == 0) return 1;
	else
		return (Binomial(n - 1, m) + Binomial(n - 1, m - 1));
}

• 그러나! 위 함수는 굉장히 느림(비효율적)
  • 중복 계산이 많아지기 때문

 

 

2023.09.26 - [50 shades of ZZ/C(++) 자료구조 마스터] - [자료구조] C/C++ 자료구조 마스터(?)를 위한 요점 정리

[자료구조] C/C++ 자료구조 마스터(?)를 위한 요점 정리