너무나도 어려웠던 5장.. 재귀함수를 비재귀함수로 구현하는게 힘들었다.
5장은 두고두고 계속 봐야할 것 같다. 특히 Q5, Q7
연습문제_Q1 > 재귀 함수 호출을 사용하지 않고 factorial 함수를 작성하세요.
#include <stdio.h>
int factorial(int n) {
int total=1; // 0팩토리얼은 1. 0팩토리얼 값. 그리고 1까지 포문 진행(1은 의미없어서 안해줘도 되긴함)
for(int i=n; i>0; i--) {
total*=i;
}
return total;
}
int main() {
int N;
printf("숫자 입력 : ");
scanf("%d", &N);
printf("%d ! = %d\n", N, factorial(N));
return 0;
}
//제공된 정답
///*--- n factorial 반환 ---*/
//int factorial(int n)
//{
// int fact = 1;
//
// while (n > 1)
// fact *= n--;
// return fact;
//}
연습문제_Q2 > 재귀 함수 호출을 사용하지 않고 gcd 함수를 작성하세요.
#include <stdio.h>
int gcd(int x, int y) { //처음 입력된 x,y는 0보다 커야함. 그리고 x>y(아닐경우 알아서 순서 바뀌어지긴 함)
int num;
while(y!=0) {
num = y;
y = x % y;
x = num;
}
return x;
}
int main() {
int x, y;
puts("두 정수의 최대공약수를 구합니다.");
printf("정수를 입력하세요 : ");
scanf("%d", &x);
printf("정수를 입력하세요 : ");
scanf("%d", &y);
printf("최대공약수는 %d입니다.\n", gcd(x,y));
return 0;
}
연습문제_Q3 > 배열 a의 모든 요소의 최대공약수를 구하는 다음 함수를 작성하세요.
int gcd_array(const int a[]. int n);
#include <stdio.h>
#include <stdlib.h>
int gcd_array(const int a[], int n) {
int x=a[0];
for(int i=0; i<n-1; i++) {
int y = a[i+1];
int num;
while(y!=0) {
num = y;
y = x % y;
x = num;
}
}
return x;
}
int main() {
int *a;
int N;
printf("배열의 길이 : ");
scanf("%d", &N);
a = calloc(N, sizeof(int));
for(int i=0; i<N; i++) {
printf("요소 %d: ", i);
scanf("%d", &a[i]);
}
printf("배열의 모든 요소의 최대공약수 : %d\n", gcd_array(a, N));
return 0;
}
// 제공된 정답
//
// /*--- 정수 x, y의 최대 공약수를 반환 ---*/
//int gcd(int x, int y)
//{
// if (y == 0)
// return (x);
// else
// return (gcd(y, x % y));
//}
///*--- 요솟수 n인 배열 a의 모든 요소의 최대 공약수를 구합니다. ---*/
//int gcd_array(const int a[], int n)
//{
// if (n == 1) // 배열 요소가 1개일 때를 위한 코드.
// return (a[0]);
// else if (n == 2)
// return (gcd(a[0], a[1]));
// else
// return (gcd(a[0], gcd_array(&a[1], n - 1)));
//}
연습문제_Q4 > 아래 recur2 함수를 보고 하향식 분석과 상향식 분석을 수행해 보세요.
void recur2(int n)
{
if(n>0) {
recur2(n-2);
printf("%d\n", n);
recur2(n-1);
}
}
하향식 분석
위에서 아래로, 계단식으로, 실행되는 순서로 들어갔다가 나옴.
n이 4일때
recur2(4) -> recur2(2); printf(“4\n”); recur2(3);
recur2(2) -> recur2(0); printf(“2\n”); recur(1);
recur2(0) -> nothing
recur2(1) -> recur2(-1); printf(“1\n”); recur2(0);
recur2(-1) -> nothing
recur2(0) -> nothing
recur2(3) -> recur2(1); printf(“3\n”); recur2(2);
recur2(1) -> recur2(-1); printf(“1\n”); recur2(0);
recur2(-1) -> nothing
recur2(0) -> nothing
recur2(2) -> recur2(0) printf(“2\n”); recur(1);
recur2(0) -> nothing
recur(1) -> recur2(-1) printf(“1\n”); recur2(0);
recur2(-1) -> nothing
recur2(0) -> nothing
상향식 분석
아래에서 위로, 실행경우중 가장 작은 수부터 점점 올라가며 분석하여 정리.
n>0일때 실행이므로 n=1부터 시작.
recur2(1) -> recur2(-1); printf(“1\n”); recur2(0); = -1과 0은 작업 없고, 결국엔 1 출력
recur2(2) -> recur2(0); printf(“2\n”); recur2(1); = 0은 작업없고, 2출력한 뒤 위의 recur2(1)의 작업인 1 출력
recur2(3) -> recur2(1); printf(“3\n”); recur2(2); = recur2(1)의 작업인 1출력한 뒤 3 출력하고 위의 recur2(2)의 작업인 2 1 출력
recur2(4) -> recur2(2); printf(“4\n”); recur2(3); = recur2(2)의 작업인 2 1 출력한 뒤 4 출력하고 ㅇ위의 recur2(3)의 작업인 1 3 2 1 출력
연습문제_Q5 > 아래 recur3 함수를 다시 비재귀적으로 구현하세요.
void recur3(int n)
{
if(n>0) {
recur3(n-1);
recur3(n-2);
printf("%d\n", n);
}
}
#include <stdio.h>
#include "IntStack.h"
/*
내 구현. 약간은 미비함.
스택을 두개 이용하여 하나는 n-1용 하나는 n-2용 이라고 볼 수 있는데,
print 시에 재귀 함수 내 그 순간순간에 한다기 보다, 값을 스택에 저장해놨다가 한꺼번에 하는 방법이라 조금 미비한것 같음.
답은 같음. goto문이 프로그램 코딩에 좋지 않다는걸 알고있는데 예제에서 쓰길래 goto문으로 구현해야하는줄알고 했는데,
정답은 포문으로 구현했더라 ..
*/
void recur3(int n)
{
IntStack stk1, stk2;
Initialize(&stk1, 100);
Initialize(&stk2, 100);
if(n > 0) {
recur3(n - 1);
recur3(n - 2);
printf("%d\n", n);
}
Top :
if(n > 0) {
Push(&stk1, n);
n-=1;
goto Top;
}
if(!IsEmpty(&stk2)) {
Pop(&stk1, &n);
Push(&stk2, n);
n-=2;
goto Top;
} else {
for(int i=(Size(&stk2)-1); i>=0; i--) {
printf("%d ", stk2.stk[i]);
}
}
Terminate(&stk1);
Terminate(&stk2);
}
int main(void)
{
int x;
printf("정수를 입력하세요. : ");
scanf("%d", &x);
recur3(x);
return 0;
}
/*
제공된 정답 : 스택에 값을 넣을 때, n-1 차원인지 n-2 차원인지 구분을 위한 구분스택 sw추가, 값을 넣을 때마다 구분스택에도 값을 넣어주며
값을 뺄 때에도 함께 빼주며 이 값이 n-1로부터인지 n-2로부터인지 인식하고 n-2일경우 출력. 방식을 반복문으로 구현했음.
내 구현에 비해 그때 그때 출력한다는 점에서 더 우세함.
void recur3(int n)
{
int sw = 0;
IntStack nstk, sstk;
Initialize(&nstk, 100);
Initialize(&sstk, 100);
while (1) {
if (n > 0) {
Push(&nstk, n);
Push(&sstk, sw);
if (sw == 0)
n = n - 1;
else if (sw == 1) {
n = n - 2;
sw = 0;
}
continue;
}
do {
Pop(&nstk, &n);
Pop(&sstk, &sw);
sw++;
if (sw == 2) {
printf("%d\n", n);
if (IsEmpty(&nstk))
return;
}
} while (sw == 2); //두번째 재귀가 끝나고는 스택을 한번 더 열어서 뽑음(함수종료후 이전재귀실행인듯. 난 이런거 안해줘도 되도록 구현했네.)
}
Terminate(&nstk);
Terminate(&sstk);
}
*/
연습문제_Q6 > 실습 5-6을 숫자가 아닌 기둥 이름을 출력하도록 프로그램을 수정하세요. 예를 들어 'A 기둥', 'B 기둥', 'C 기둥'과 같이 출력하면 됩니다.
#include <stdio.h>
void move(int no, int x, int y)
{
if(no > 1)
move(no-1, x, 6-x-y); //그룹을 시작 기둥에서 중간 기둥으로
printf("원반[%d]를(을) %c 기둥에서 %c 기둥으로 옮김\n", no, x+64, y+64); //바닥 원반을 목표 기둥으로
if(no > 1)
move(no-1, 6-x-y, y); // 그룹을 중간 기둥에서 목표 기둥으로
}
int main(void)
{
int n;
printf("하노이의 탑\n원반 개수: ");
scanf("%d", &n);
move(n, 1, 3);
return 0;
}
// 제공된 정답
///* 하노이 탑(기둥 이름을 출력했습니다) */
//#include <stdio.h>
//
///*--- 원반[1] ~ 원반[no]을 x 기둥에서 y 기둥으로 이동 ---*/
//void move(int no, int x, int y)
//{
// char *name[] = { "Ａ기둥", "Ｂ기둥", "Ｃ기둥" };
//
// if (no > 1)
// move(no - 1, x, 6 - x - y); /* 그룹을 시작 기둥에서 중간 기둥으로 */
//
// printf("원반[%d]를 %s에서 %s로 이동\n", no, name[x - 1], name[y - 1]); /* 바닥을 목적 기둥으로 */
//
// if (no > 1)
// move(no - 1, 6 - x - y, y); /* 그룹을 중간 기둥에서 목표 기둥으로 */
//}
연습문제_Q7 > 실습 5-6의 move 함수를 비재귀적으로 수정하세요.
#include <stdio.h>
#include "IntStack.h"
void mave(int no, int x, int y) {
IntStack stk1, stk2, stk3;
Initialize(&stk1, 100);
Initialize(&stk2, 100);
Initialize(&stk3, 100);
Top:
if(no > 1) {
Push(&stk1, no);
Push(&stk2, x);
Push(&stk3, y);
no-=1;
y=6-x-y;
goto Top; // 그룹을 시작기둥에서 중간기둥으로
} else if(no==1) { // 핵심적으로 추가한 부분. print는 no가 1보다 작은 0이여도 하기 때문에.
printf("원반[%d]를(을) %d 기둥에서 %d 기둥으로 옮김\n", no, x, y); // 바닥원반을 목표기둥으로
}
if(!IsEmpty(&stk1)) {
Pop(&stk1, &no);
Pop(&stk2, &x);
Pop(&stk3, &y);
printf("원반[%d]를(을) %d 기둥에서 %d 기둥으로 옮김\n", no, x, y); // 바닥원반을 목표기둥으로
no-=1;
x=6-x-y;
goto Top; // 그룹을 중간기둥에서 목표기둥으로
}
}
int main(void)
{
int n;
printf("하노이의 탑\n원반 개수: ");
scanf("%d", &n);
mave(n, 1, 3);
return 0;
}
// 제공된 정답은 도저히 뭔소린지 모르겠음.
연습문제_Q8 > 실습 5-9의 print 함수를 수정하여 전각 기호를 사용해 퀸의 배치 상황을 출력하세요.
#include <stdio.h>
int flag_a[8]; // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_b[15]; // 대각선 /에 퀸을 배치했는지 체크하는 배열
int flag_c[15]; // 대각선 \에 퀸을 배치했는지 체크하는 배열
int pos[8]; // 각 열에서 퀸의 위치
//퀸의 위치 출력
void print() {
for(int i = 0; i< 8; i++) {
for(int j =0; j<8; j++) {
(pos[i]==j)?printf("◼︎ "):printf("◻︎ ");
}
putchar('\n');
}
putchar('\n');
putchar('\n');
}
//i열에서 알맞은 위치에 퀸을 배치
void set(int i)
{
// j 행 i 열
int j;
for(j = 0; j < 8; j++) {
if(!flag_a[j]&&!flag_b[i+j]&&!flag_c[i-j+7]) {
pos[i] = j;
if(i == 7) // 모든 열에 배치를 마침
print();
else {
flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = 1;
set(i+1);
flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = 0;
}
}
}
}
int main() {
int i;
set(0);
return 0;
}
연습문제_Q9 > 8퀸 문제를 비재귀적으로 구현한 프로그램을 작성하세요.
#include <stdio.h>
#include "IntStack.h"
int flag_a[8]; // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_b[15]; // 대각선 /에 퀸을 배치했는지 체크하는 배열
int flag_c[15]; // 대각선 \에 퀸을 배치했는지 체크하는 배열
int pos[8]; // 각 열에서 퀸의 위치
int count=0;
//퀸의 위치 출력
void print() {
count++;
int i;
for(i=0; i<8; i++)
printf("%2d", pos[i]);
putchar('\n');
}
//i열에서 알맞은 위치에 퀸을 배치
void set(int i)
{
IntStack row, col;
Initialize(&row, 100);
Initialize(&col, 100);
// j 행 i 열
int j=0;
B:
for(; j < 8; j++) {
if(!flag_a[j]&&!flag_b[i+j]&&!flag_c[i-j+7]) {
pos[i] = j;
if(i == 7) // 모든 열에 배치를 마침
{
print();
}
else {
flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = 1;
Push(&row, j);
Push(&col, i);
j=0; //재귀함수 호출준비이므로 뽑은 뒤에 함수의 처음으로 이동할 때 j값을 초기화하여 새로운 함수인것처럼 해줘야함.
i++; //하나 증가한 뒤 함수의 처음으로 이동
goto B;
}
}
}
if(!IsEmpty(&row)) { //둘중 아무거나 안 비어있으면
Pop(&row, &j);
Pop(&col, &i);
flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = 0;
j++; // 재귀함수를 마치고 기존의 j행으로 이동할 때, 재귀함수가 끝난 상황이므로 이제 j++작업을 해주며 다음 행을 뽑을 준비를 해야하는데 그냥 이동시 for문의 증감식을 거치지 않으므로 수동으로 넣어줌.
goto B;
}
Terminate(&row);
Terminate(&col);
}
int main() {
set(0);
printf("%d\n", count);
return 0;
}
재귀문을 비재귀로 구현해주는데 있어서, 스택이 유용하게 쓰이는 것 같다. 스택 없이 구현해보려했는데, 재귀 전 값의 임시 저장을 필요로 하는 재귀함수(다른 재귀함수로 이동하기 전에 현재 재귀함수의 데이터 저장 느낌, 다른 액티비티로 이동하기 전에 현재 액티비티의 값을 저장해놓고 이동한뒤 돌아왔을때 그 값으로 복구하는 느낌)는 스택같은 자료구조를 필히 사용해야 할 것 같다.
다시말해, 꼬리재귀의 역할이 아닌 재귀함수들은 스택을 필요로 한다.
공부 내용 정리
▶︎ 재귀
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 합니다.
재귀의 개념을 사용해 1부터 무한하게 이어지는 자연수를 아래처럼 정의할 수 있다.
1. 1은 자연수다.
2. 자연수 n의 바로 다음 수도 자연수다.
이처럼 재귀적 정의에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의할 수 있다.
∙ 재귀의 기본 사용 예, 순차곱셈(factorial)
음이 아닌 정수 n의 순차곱셈 n!은 아래처럼 재귀적으로 정의할 수 있다.
1. 0! = 1
2. n > 0 이면 n! = n×(n-1)!int factorial(int n)
{
if(n > 0)
return n*factorial(n-1); //재귀 호출
else
return 1;
}
∙ 직접재귀와 간접재귀
위처럼 함수 A안에서 함수 A를 다시 호출하는 것을 직접재귀라고 하고, 함수 A안에서 함수B를 호출하고 그 함수B안에서 함수 A를 호출하는것을 간접재귀라고 한다.
∙ 재귀의 사용 예, 유클리드 호제법
두 정수의 최대공약수(GCD)를 재귀적으로 구하는 방법을 알아보자.
두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어 떨어지는 가장 작은 값이 최대공약수다. 나누어떨어지지 않으면 작은값에 대해 얻은 나머지로 다시 나누며, 나누어떨어질때까지 같은과정을 반복한다. 그리고 나누어떨어질 때 나누는 값, 작은값이 최대공약수라는 것이다. 이 알고리즘을 유클리드 호제법이라고 한다.
이는 두 정수를 직사각형의 두 변의 길이라고 생각하고, 최대공약수는 직사각형을 정사각형으로만 완전히 채워서 만들 수 있는 가장 큰 정사각형의 한 변의 길이라고 볼 수도 있다. 두 정수 중 작은 정수를 한 변으로 하는 정사각형으로 직사각형을 채우며, 채워지지 않고 남는 직사각형이 생길 경우 다시 그 안에서 이런 작업을 반복하여 모두 정사각형으로 채워질 수 있을때, 그 정사각형의 길이가 최대공약수인것.
- 유클리드 호제법에 의한 최대공약수 구하기
int gcd(int x, int y) //처음 입력한 x, y는 0보다 큰 정수여야되겠음. 또한 x는 큰값이고 y는 작은값이여야하는데, 아닐경우 아래서 알아서 순서바꿔지긴 함.
{
if(y==0)
return x;
else
return gcd(y, x%y);
}
∙ 재귀 호출을 여러 회 실행하는 함수를 '순수하게 재귀적'이라고 한다
ex)
void recur(int n)
{
recur(n-1);
putchar('\n');
recur(n-2);
}
∙ 재귀 알고리즘의 분석
- 하향식 분석
가장 위쪽에 위치한 함수 호출부터 시작해 계단식으로 자세히 내려가며 조사해 가는 분석 기법. 실행되는 순서로 직접 들어갔다 나오며 조사.
꼭대기부터 분석하는 탓에 같은함수경우의 호출이 여러번 나올 수 있다.
Top -> Bottom 방식
- 상향식 분석
아래쪽부터 쌓아 올리며 분석하는 방법.
해당 알고리즘의 가능한 실행 경우중 가장낮은수의 경우부터 수행하는 작업을 분석하고 숫자를 높여나가며 정리함.
Bottom -> Top 방식
개인적으로 상향식분석이 효율이 좋은듯
∙ 재귀함수의 또다른 예, 하노이의 탑 알고리즘
총 원반이 두개 이상일 경우 재귀가 시작되고, 이때 항상 맨 아래 원반을 제외한 나머지 원반을 하나의 그룹으로 본다.
그럼 원반이 몇개일지라도 항상 간단하게 아래 3단계로 정의된다.
1. 그룹을 시작 기둥에서 중간 기둥으로
2. 바닥 원반을 시작 기둥에서 목표 기둥으로
3. 그룹을 중간 기둥에서 목표 기둥으로
그렇게 각 그룹마다 재귀함수를 통해 구성한다.
그리고 재귀함수 안에선, 그룹의 개수가 1개가 되면 더이상 재귀하지 않는다. (그 안에서도 총 원반이 2개 이상이면 재귀해야하지만, 1개라면 그냥 1개 옮기고 함수 종료. 재귀 탈출조건)
void move(int no, int x, int y)
{
if(no > 1)
move(no - 1, x, 6 - x - y); // 그룹을 시작 기둥에서 중간 기둥으로
printf("원반[%d]를(을) %d 기둥에서 %d 기둥으로 옮김\n", no, x, y); // 바닥 원반을 목표 기둥으로
if(no > 1)
move(no - 1, 6 - x - y, y); // 그룹을 중간 기둥에서 목표 기둥으로
}
원반이 두개 이상일 때, 그룹으로 묶어서 그룹마다 재귀해주고 그룹안의 갯수가 1개일 땐 재귀할 필요없이 그냥 옮기고 끝나는 것.
다시한번 !
전체 원반이 두개 이상이면 맨 아래원반을 제외하고 나머지를 하나의 그룹으로 묶어 재귀를 호출하고 재귀안에서 이 개념의 과정을 똑같이 반복(맨아래 하나를 제외하고 나머지그룹화 후 재귀) 언제까지? 그룹화한 원반의 갯수가 1일때까지.
∙ 재귀함수의 또다른 예, 8퀸 문제(8-Queen problem)
서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.
+ 퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능합니다.
이 문제의 정답은 92가지의 조합이다.
∙ 용어 정리
- 가지뻗기
모든 조합을 나열하는 것을 말함.
- 분할 해결법
문제를 세분하고, 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법.
- 한정조작
필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법
- 분기 한정법
가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법
출처 -'Do it 자료구조와 함께 배우는 알고리즘 입문 C언어편' 도서
'[알고리즘 + 자료구조] > [Do it 자료구조와 함께 배우는 알고리즘]' 카테고리의 다른 글
| [알고리즘] Do it 자료구조와 알고리즘 7장 정리 (0) | 2020.12.06 |
|---|---|
| [알고리즘] Do it 자료구조와 알고리즘 6장 정리 2/2 (0) | 2020.11.27 |
| [알고리즘] Do it 자료구조와 알고리즘 4장 정리 (0) | 2020.10.15 |
| [알고리즘] Do it 자료구조와 알고리즘 3장 정리 (0) | 2020.10.11 |
| [알고리즘] Do it 자료구조와 알고리즘 2장 정리 (0) | 2020.10.09 |