수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님
1. 재귀호출
- 함수가 실행 중에 자기 자신을 다시 호출하는 것이다.
- 같은 작업을 반복하는데 조금씩 상황이 바뀌는 경우에 사용한다.
- 함수에 반드시 종결 조건이 있어야 한다.
- Divide & Conquer 전략에 사용된다.
- 재귀 호출문은 if-else나 while문을 활용한 반복문으로 바꿀 수 있다.
- 컴파일러의 관점에서 재귀 호출은 새로운 함수를 호출하는 것과 같다.
- 따라서 함수를 호출할 때마다 함수의 지역 변수, 복귀 주소 등 컨텍스트 정보를 활성 레코드에 저장해야 한다.
- 장점 : 알고리즘을 깔끔하게 표현할 수 있다.
- 단점 : 함수를 실행할 때마다 메모리에 환경 변수를 저장하기 때문에 메모리의 소모가 일어난다.
2. 팩토리얼 예제
- n! = 1 x 2 x ... x (n-1) x n = (n-1)! x n
- 같은 일 (곱셈) 을 반복하면서 n = 0이면 n! = 1 이라는 종결 조건이 포함되어있기 때문에 재귀 호출을 사용할 수 있다.
long factorial (int n)
{
if (n == 0)
return 1;
else
return n * factorial (n-1);
}이와 같이 n = 0 이면 1을, n > 0 이면 n * (n-1)! 을 반환하는 형식으로 표현할 수 있다.
3. 최대공약수 (GCD) 예제
- 공통으로 나누는 수 중 가장 큰 수
- 조건 (by 유클리드 호제법)
- gcd (x, y) = gcd (y, x % y) (if (y > 0))
- gcd (x, 0) = x
ind gcd (x, y)
{
if (y == 0)
return x;
else return gcd (y, x % y);
}
4. Binary Search 이진 탐색
- 정렬된 항목 리스트에 대해서 중간값과 크기를 비교하고 그 결과에 따라 가능성이 있는 절반의 리스트에 대해서만 과정을 반복하는 탐색 알고리즘이다.
- 한 번 비교할 때마다 탐색 대상 원소의 수가 절반으로 감소한다.
- 원소의 수가 n개일 때 이진탐색은 총 log₂ⁿ 번의 비교 횟수를 요구한다. 따라서 순차 탐색보다 속도가 빠르다.
- 조건은 리스트 안에 겹치는 숫자가 없어야 한다는 것이다.
-while문과 if문을 이용한 이진탐색
#include <stdio.h>
int binsearch (int mylist[], int item, int left, int right);
void main()
{
int pos, maxnum = 12, item = 60;
int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
pos = binsearch(mylist, item, 0, maxnum - 1);
printf("position = %d", pos);
}
int binsearch (int list[], int item, int left, int right)
{
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (list[mid] == item)
return mid;
else {
if (item < list[mid]
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
- 재귀호출 형식의 이진탐색
#include <stdio.h>
int rbinsearch (int mylist[], int item, int left, int right);
void main()
{
int pos, maxnum = 12, item = 60;
int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
pos = binsearch(mylist, item, 0, maxnum - 1);
printf("position = %d", pos);
}
int rbinsearch (int list[], int item, int left, int right)
{
int mid;
if (left <= right)
{
mid = (left + right) / 2;
if (item == list[mid]
return mid;
else if (list[mid] < item)
return rbinsearch(list, item, mid + 1, right);
else
return rbinsearch (list, item, left, mid - 1);
}
return -1;
}
5. 하노이 타워 예제
- 세 개의 기둥과 크기가 다양한 원판이 존재한다.
- 해결할 문제는 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮기는 것이다.
- 조건
- 한 번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 놓일 수 없다.
- 알고리즘
- 세 개의 기둥 A, B, C 가 있고, A에서 B로 n개의 원판을 옮긴다.
1) A에서 (n-1)개의 원판을 C로 옮긴다.
2) A에 남은 1개의 원판을 B로 옮긴다.
3) C에 있는 (n-1)개를 B로 옮긴다.
- 기둥 a = 1, b = 2, c = 6 - a - b // a, b 제외한 빈 기둥이 c
- 총 이동횟수 : 2ⁿ - 1
#include <stdio.h>
void htower(int n, int a, int b);
int count = 0;
void main()
{
int n;
count = 0;
printf("Enter disc number = ");
scanf("%d", &n);
htower(n, 1, 2);
printf("# move for %d discs : %d\n", n, count);
}
void htower (int n, int a, int b)
{
int c;
count ++;
if (n == 1)
printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, b);
else {
c = 6 - a - b;
htower(n-1, a, c);
printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, c);
htower(n-1, c, b);
}
}
- Time complexity 시간 복잡도
- t(1) = 1 : 하나의 디스크 옮기는데 필요한 시간
- time to move n disks : t(n)
- t(n) = 2 t(n-1) + 1
= 2 (2 t(n-2) + 1) + 1
= ...
= 2ⁿ⁻¹ + 2ⁿ⁻² + ... + 2¹ + 2⁰
= 2ⁿ - 1 ≅ 2ⁿ
- t(n) = O(2ⁿ)
→ n 이 크면 사용하지 않는 것이 좋다.
6. Permutation 순열
- 순서를 다르게 나열하는 방법의 수
- {a, b, c, d} → ₄P₄ = 4! = 24
a) (a, Perm (b, c, d)) → Perm(b, c, d) = (b, Perm (c, d)), (c, Perm (b, d)), (d, Perm (b, c))
b) (b, Perm (a, c, d))
c) (c, Perm (a, b, d))
d) (d, Perm (a, b, c))
// i : start index of range
// n : end index of range
void perm(char list[], itn i, int n)
{
int j;
if (i == n) // list print
{
for (j = 0; j <= n; j++)
printf("%c", list[j]);
printf(" ");
}
else {
for (j = i; j <= n; j++) {
Swap(list[i], list[j]); // 두 수 교환
perm(list, i + 1; n);
Swap(list[i], list[j]);
}
}
}
'Software > Data Structures' 카테고리의 다른 글
| [자료구조] 연결 리스트 (0) | 2021.04.20 |
|---|---|
| [자료구조] 선형 자료구조 (0) | 2021.04.18 |
| [자료구조] 알고리즘 성능 분석 (0) | 2021.04.17 |
| [자료구조] C언어 기초 (0) | 2021.04.17 |
| [자료구조] Introduction (0) | 2021.04.17 |
