[자료구조] 순환 알고리즘 (이원 탐색, 순열 생성)

순환 알고리즘

 

함수가 그 수행이 완료되기 전에 자기 자신을 다시 호출(직접 순환, direct recursion)하거나

호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출(간접 순환, indirect recursion) 할 수 있다.

 

if - else 문, while문, for문으로 작성할 수 있는 어떤 프로그램도 순환으로 작성할 수 있고, 훨씬 단순하게 표현할 수 있도록 해준다.

 

---

순환 알고리즘에서 코딩부터 시도 하는 것이 아니라, 조건과 순환 구조를 미리 정리하고 코딩하는 것이 빠르다.

 

(1) 순환 호출의 종결 조건을 먼저 설정한다.

 

    -  종결되지 않으면 끝도없이 순환하게 되는 악몽에 빠진다.

 

(2) 매 호출마다 해답을 향해 한 단계씩 가까워지게끔 순환 호출을 구현하여야 한다.

 

---

아래 두가지 예를 통해 순환 알고리즘 설명하겠다.

 

1. 이원탐색

 

알고리즘 :

배열의 값이 오름차순으로 정렬되어 있다고 전제한다.

 

리스트 배열에서 중앙값을 기준으로 searchnum을 비교한다.

searchnum이 더 클 경우 : 중앙값 우측 배열 위치로 left값을 조정한다.

searchnum이 더 작을 경우 : 중앙값 좌측 배열 위치로 right값을 조정한다.

searchnum이 같을경우 : 위치를 리턴한다.

 

(1) 종결 조건

 

    -  list[middle] = searchnum 이 되어 탐색에 성공할 때

    -  배열의 좌우 인덱스가 엇갈려 탐색에 실패한 경우.

 

(2) 해답에 가까워지게 하는 순환 호출

 

    -  left나 right 인덱스를 다음 순환 호출의 매개 변수로 전달만 하면 된다.

 

코드 예시

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

int binsearch_recursion(int list[], int searchnum, int left, int right) {
	int middle;
	if (left <= right) {
		middle = (left + right) / 2;
		switch (COMPARE(list[middle], searchnum)) {
		case -1: return binsearch_recursion(list[], searchnum, middle+1, right);
		case 0: return middle;
		case 1: return binsearch_recursion(list[], searchnum, left, middle - 1);
		}
	}
	return -1;
}

더 자세한 알고리즘 설명

2020/03/17 - [SW/자료구조 & 알고리즘] - [자료구조] Binary search (with Recursion(재귀) pseudo code) 예제.

[자료구조] Binary search (with Recursion(재귀) pseudo code) 예제.

---

2. 순환 순열 생성기

 

알고리즘:

 

n ≥ 1 개의 원소를 가진 집합이 주어졌을 때 이 집합의 모든 가능한 순열을 출력해보자.

n 개의 주어진 원소에 대해 n!개의 상이한 순열이 있다.

 

'~로 시작하는 ~의 모든 순열' 이라는 표현이 바로 순환의 실마리이다.

 

list를 문자 타입 배열이라 가정하고, i = n이 될 때까지 순열을 순환적으로 생성한다.

초기의 함수 호출은 perm(list, 0, n-1); 이 된다.

 

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

void perm(char* list, int i, int n)
{/* generate all the permutations of list[i] to list [n]*/
	int j, temp;
	if (i == n) {		// i == n 일때 print 조건.
		for (j = 0; j <= n; j++)
			printf("%c", list[j]);
		printf("    ");
	}
	else { // 종료조건 i != n
	/* list[i] to list[n] has more than one permutation, generae these recursively */
		for (j = i; j <= n; j++) {
			SWAP(list[i], list[j], temp); 
			perm(list, i + 1, n);	
			SWAP(list[i], list[j], temp);
		}
	}
}

void main(void)
{
	char list[]="abc";
	perm(list, 0, 2);
}

i와 j를 통해서 모든 순열을 나타 낼 수 있다.

위와 같이 3개의 항목이 있는 순열을 나타내보겠다.

 

위의 코드의 진행과정이 이해가 가지 않는다면 아래에 어떻게 구성되어있는지 구조적으로 적었다.

for 문의 진행 과정이다.

---

for 문 i = 0, j = 0

    SWAP //(abc)

    perm i = 1, j = 1 -> for문 i = 1 , j = 1

                               SWAP //(abc)

                               perm -> i = 2 ->print //(abc)

                               SWAP  //(abc)

                               for문 i = 1 , j = 2

                               SWAP //(acb)

                               perm -> i = 2 ->print //(acb)

                               SWAP  //(abc)

    SWAP // 제자리로 돌려줌. (abc)

 

for 문 i = 0, j = 1

    SWAP //(bac)

    perm i = 1, j = 1 -> for문 i = 1 , j = 1

                               SWAP  //(bac)

                               perm -> i = 2 ->print //(bac)

                               SWAP  //(bac)

                               for문 i = 1 , j = 2

                               SWAP  //(bca)

                               perm -> i = 2 ->print //(bca)

                               SWAP  //(bac)

    SWAP  //(abc)

 

for 문 i = 0, j = 2

    SWAP //(cba)

    perm i = 1, j = 1 -> for문 i = 1 , j = 1

                               SWAP  //(cba)

                               perm -> i = 2 ->print //(cba)

                               SWAP  //(cba)

                               for문 i = 1 , j = 2

                               SWAP  //(cab)

                               perm -> i = 2 ->print //(cab)

                               SWAP  //(cba)

    SWAP  //(abc)

 

 

---

참고

c 로쓴 자료구조론/ horowitzs / 2008

https://intellipaat.com/blog/tutorial/python-tutorial/data-structures-with-python-cheat-sheet/