2016-05-02_조재찬_스터디일지_버블정렬과 재귀 알고리즘

  버블정렬 알고리즘

: 인접한 두 값를 비교하여 정렬하는 방법이다. 한쪽에서 다른 한쪽으로 크기를 비교, 교환해가면서 정렬한다. (오름차순 또는 내림차순)

{3, 2, 4, 1}

오름차순 정렬시 가장 큰 값을 배열의 마지막으로 먼저 보냄 (맨앞에서부터 순차적으로 3번의 비교)

swap이 일어나는 과정

#include <stdio.h> void BubbleSort(int ary[], int len); // 배열의 주소값, 전달할 데이터 수 int main(void) { int arr[4]={3, 2, 1, 4}; int i; BubbleSort(arr, sizeof(arr)/sizeof(int)); // 전체배열 16바이트/ 4바이트 (int) 배열 for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; } void BubbleSort(int ary[], int len) { int i, j; int temp; for(i=0; i<len-1 ;i++) // for문 3회 실행 ( 3,2 / 2,4/ 4,1) { for(j=0; j<(len-i)-1; j++) { if(ary[j]>ary[j+1]) // 앞의 배열값이 크면 swap, 부등호를 <로 바꾸면 내림차순 { temp=ary[j]; ary[j]=ary[j+1]; ary[j+1]=temp; } } } }

Output:

1 2 3 4

재귀 함수

 : 함수내에서 자기 다신을 다시 호출하는 함수

탈출조건을 구성하는 것이 중요

factorial - 재귀함수 활용 소스

factorial : 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다. 

0!=1,     1!=1

4! = 1x2x3x4 = 24

n factorial f(n)은 수식적으로 다음과 같이 표현

n이 0이면, f(n)=1

n이 1과 같거나 크면, f(n)=n X f(n-1)

factorial 함수를 소스로 옮기면 다음과 같다.

int Factorial(int n)

{

if(n == 0)

return 1;

else

return n * Factorial(n-1);

}    

피보나치 수열

: 처음 두 항은 0과 1이 주어진 상태에서, 세 번째 항부터는 바로 앞의 두 항의 합이 된다

0, 1, 1, 2, 3, 5, 8, 13, 21...

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값 (0과 1은 처음 주어진 수)

피보나치 수열의 수학적 수식 (n=1은 0, n=2는 1) 

fib(n) = fib(n-1) + fib(n-2)

다음과 같이 재귀적 알고리즘에 의해 함수를 정의한다. 

int Fibo(int n)

{

if(n ==1)

return 0;    // n=1은 0 반환

else if(n == 2)

return 1;    // n=2는 1 반환

else

return Fibo(n-1) + Fibo(n-2);    // 피보나치 수학적 수식 그대로 계산후 반환

}

이진 탐색 알고리즘의 재귀적 구현

반복 패턴

1. 탐색 범위의 중앙에 목표값이 있는지 확인

2. 없다면 탐색범위를 반으로 줄여 다시 탐색

탐색 실패=재귀의 탈출 조건

first(탐색시작지점)가 last보다 커지는 경우, 즉 역전되는 경우는 값이 없음을 의미하고 재귀에서 탈출

if(first > last)

return -1     // 탐색 실패시 -1 반환

#include <stdio.h> int BSearchRecur(int ar[], int first, int last, int target) //인자는 배열, 탐색의 시작과 끝 지점, 타겟이 된다. { int mid; if(first > last) return -1; // -1의 반환은 탐색의 실패를 의미 mid = (first+last) / 2; // 탐색대상의 중앙을 찾는다. if(ar[mid] == target) return mid; // 검색된 타겟의 인덱스 값 반환 else if(target < ar[mid]) return BSearchRecur(ar, first, mid-1, target); else return BSearchRecur(ar, mid+1, last, target); } int main(void) { int arr[] = {1, 3, 5, 7, 9}; int idx; //인덱스 idx = BSearchRecur(arr, 0, (sizeof(arr)/sizeof(int))-1, 7); // first는 0이기 때문에 last의 인덱스값은 -1을 해줘야 함, 타켓은 7 if(idx == -1) // -1의 반환은 탐색 실패 printf("탐색 실패 \n"); else printf("타겟 저장 인덱스: %d \n", idx); idx = BSearchRecur(arr, 0, (sizeof(arr)/sizeof(int))-1, 2); if(idx == -1) printf("탐색 실패 \n"); else printf("타겟 저장 인덱스: %d \n", idx); return 0; }

Output:

타겟 저장 인덱스: 3 // {1,3,5,7,9} 탐색 실패 // 타켓 2는 배열에 없으므로 탐색 실패

하노이 타워

위 풀이 과정은 원반이 4개인 하노이 타워에서도 아래와 같이 3단계의 패턴으로 간략화할 수 있다.

2,3개의 원반을 가지고 풀이하면 본질을 이해할 수 있다.

즉 가장 큰 원반을 옮기기위해선 그 위의 원반들을 A에서(from)

경유지를 통해(by) 목적지로(to) 옮기게 된다.

하노이타워 함수의 인자는  원반의 수 n과

위에서 적은것과 같이 from, by, to가 된다.

목적 : 큰 원반 n개를 A에서 C로 이동

HanoiTowerMove(n, from, by, to); // 원반의 번호는 위로갈수록 n-1,    A,    B,    C

1. 작은 원반 n-1개를 A에서 B로 이동

HanoiTowerMove(n-1, from, to, by);     

// A,    C,    B (C가 경유지가 됨)

2. 큰 원반 1개를 A에서 C로 이동

1개는 그대로 1개, printf( . . . . );   

3. 작은 원반 n-1개를 B에서 C로 이동

HanoiTowerMove(n-1, by, from, to);

// B,    A,    C    

함수의 호출순서가 잘 파악되지 않는다면 visual studio에서 "한단계식 코드 실행"을 하며 디버깅을 하는 것도 좋은 방법이다.

#include <stdio.h> void HanoiTowerMove(int n, char from, char by, char to) { if(n==1) // 이동할 원반의 수가 1개라면 { printf("원반1을 %c에서 %c로 이동 \n", from, to); } else { HanoiTowerMove(n-1, from, to, by); // 3단계 중 1단계 printf("원반%d을(를) %c에서 %c로 이동 \n", n, from, to); // 3단계 중 2단계 HanoiTowerMove(n-1, by, from, to); // 3단계 중 3단계 } } int main(void) { // 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기 HanoiTowerMove(3, 'A', 'B', 'C'); return 0; }

Output:

원반1을 A에서 C로 이동 원반2을(를) A에서 B로 이동 원반1을 C에서 B로 이동 원반3을(를) A에서 C로 이동 원반1을 B에서 A로 이동 원반2을(를) B에서 C로 이동 원반1을 A에서 C로 이동