05. 재귀 알고리즘

Notice

Recent Posts

Recent Comments

Link

« 2025/01 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

촉촉한초코칩

05. 재귀 알고리즘 본문

Algorithm

05. 재귀 알고리즘

햄친구베이컨 2023. 4. 21. 00:39

5-1 재귀의 기본

재귀

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 : 재귀적(recursive)
ex) 자연수 : 재귀적 정의(recursive definition)에 의해 무한으로 존재하는 자연수
재귀를 효과적으로 사용하면 프로그램도 간결하게 만들 수 있다.
즉, 자기 자신과 똑같은 함수를 호출하는 것과 같다.

음이 아닌 정수의 순차곱셈 구하기 (factorial)

음이 아닌 정수 n의 순차곱셈 (n!) 정의

0! = 1
n > 0이면 n! = n * (n - 1)!

#include <stdio.h>

//정수 n의 순차곱셈 값 반환
int factorial(int n) {
   if(n>0)
      return n * factorial(n-1);
   else
      return 1;
}

int main(void) {
   int x;
   printf("정수를 입력하세요 : ");
   scanf("%d", &x);
   printf("%d의 순차곱셈 값은 %d입니다. \n", x, factorial(x));
   
   return 0;
}

재귀호출 과정 (3의 순차곱셈 값 구하기)

factorial(3) 실행 > 3 * factorial(2) 반환
위의 곱셈을 수행하려면 factorial(2)의 값을 구해야 한다. 2를 다시 매개변수로 전달하고 factorial 함수 호출한다.
매개변수 2를 전달받는다.
다시 곱셈 2 * factorial(1)을 수행하기 위해 factorial 함수를 호출한다.
매개변수 1을 전달받는다.
다시 곱셈 1 * factorial(0)을 수행하기 위해 factorial 함수를 호출한다.
호출된 factorial 함수는 매개변수 n에 전달받은 값이 0이므로 1을 반환한다.
반환된 값 1을 전달받은 factorial 함수는 1 * factorial(0)(1*1)을 반환한다.
반환된 값 1을 전달받은 factorial 함수는 2 * factorial(1)(2*1)을 반환한다.
반환된 값 2를 전달받은 factorial 함수는 3 * factoria(2)(3*2)를 반환한다.

직접 재귀와 간접 재귀

직접 재귀 (direct) : 자신과 같은 함수를 호출하는 것
간접 재귀 (indirect) : 함수 a가 함수 b를 호출하고 다시 함수 b가 함수 a를 호출하는 구조

유클리드 호제법 > 두 정수의 최대공약수를 재귀적으로 구하는 방법

ex) 직사각형을 정사각형으로 완전히 채운다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하시오. (22, 8)

22*8 크기의 직사각형에서 짧은 변을 한 변으로 하는 정사각형으로 분할한다.
그러면 8*8 크기의 정사각형 타일 2장이 생기고 8*6 크기의 직사각형 1개가 남는다.
남은 8*6 크기의 직사각형으로 다시 같은 과정을 수행한다.
6*6 크기의 정사각형 1개, 6*2 크기의 직사각형 1개가 남는다.
남은 6*2 크기의 직사각형으로 다시 같은 과정을 수행한다.
2*2 크기의 정사각형 3개가 나온다. > 최대공약수는 2가 된다.

두 정수가 주어질 경우, 큰 값을 작은 값으로 나누었을 떄 나누어떨어지는 가장 작은 값이 최대공약수이다.
나누어지지 않으면 작은 값 (얻은 나머지)에 대해 나누어떨어질 때까지 같은 과정을 재귀적으로 반복한다.

수학적으로 표현하기 (= 유클리드 호제법 Euclidean method of mutual division)

두 정수 x, y의 최대공약수 : gcd(x, y)
x = az와 y = bz를 만족하는 정수 a, b와 최대 정수 z가 존재할 때, z는 gcd(x, y)가 된다.
즉, 최대공약수는 y가 0이면 x가 되고, y가 0이 아니면 gcd(y, x % y)로 구한다.

#include <stdio.h>

//정수 x, y의 최대공약수 반환 
int gcd(int x, int y) {
   if(y == 0)
      return x;
   else
      return gcd(y, x % y);
}

int main(void) {
    int x, y;
    puts("두 정수의 최대공약수를 구합니다.");
    printf("정수를 입력하세요 : ");
    scanf("%d", &x);
    printf("정수를 입력하세요 : ");
    scanf("%d", &y);
    printf("최대공약수는 %d입니다. \n", gcd(x, y));
    
    return 0;
}

5-2 재귀 알고리즘 분석

재귀 알고리즘 분석

#include <stdio.h>

//재귀 함수 
void recur(int n) {
   if(n > 0) {
      recure(n-1);
      printf("%d\n", n);
      recur(n-2);
   }
}

int main(void) {
   int x;
   printf("정수를 입력하세요 : ");
   scanf("%d", &x);
   recur(x);
   
   return 0;
}

* recur 함수 : 재귀 호출을 2회 실행한다.

* 순수하게 재귀적 (genuinely) : 재귀 호출을 여러 회 실행하는 함수

1) 하향식 분석 (top-down analysis)

가장 위쪽에 위치한 값부터 함수 호출을 시작해 계단식으로 자세히 조사해가는 분석 기법

* 매개변수 n으로 4 전달할 때 과정

recur(3) 실행
4 출력
recur(2) 실행

2) 상향식 분석 (bottom-up analysis)

아래쪽부터 쌓아 올리며 분석하는 방법

* 매개변수 n으로 4 전달할 때 과정

recur(0) 실행
1 출력
recur(-1) 실행

재귀 알고리즘의 비재귀적 표현 (= 재귀 호출을 사용하지 않고 구현하는 방법)

꼬리 재귀의 제거

함수의 꼬리에서 재귀 호출하는 함수 recur(n-2) = 인자로 n-2를 전달하여 recur 함수를 호출한다.

n의 값을 n-2로 업데이트하고 함수의 시작 지점으로 돌아간다.

recur 함수는 n의 값을 -2만큼 줄인 다음 goto 문을 사용해 함수 시작 지점으로 돌아간다.

//함수 recur(함수의 끝에서 시작하는 꼬리 재귀 제거)
void recur(int n) {
   Top:
      if(n > 0) {
         recur(n-1);
         printf("%d\n", n);
         n = n - 2;
         goto Top:
      }
}

재귀의 제거 (앞에서 호출한 재귀 함수 제거하기)

변수 n의 값을 출력하기 전에 recur(n-1)을 먼저 수행해야 한다.
스택을 사용하여 변수 n의 값을 잠시 저장한다.

//재귀 호출을 제거한 recur 함수 
void recur(int n) {
   IntStack stk;
   Initialize(&stk, 100);
   
   Top:
      if(n > 0) {
        Push(&stk, n);
        n = n - 1;
        goto Top;
    }
    
    if(!IsEmpty(&stk)) {  //스택이 비어있지 않으면 
       Pop(&stk, &n); //값을 저장했던 n 빼기
       printf("%d\n", n);
       n = n - 2;
       goto Top;
    }
    
    Terminate(&stk);
}

5-3 하노이의 탑

* 분할 해결법 (divide and conquer)

문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법
문제를 세분할 때는 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출될 수 있도록 설계해야 한다.

하노이의 탑 (Towers of Hanoi)

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에 옮기는 문제
모든 원반을 마지막 원반으로 최소의 횟수로 옮기며 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수는 없다.

시작 기둥 : 처음 원반이 놓인 기둥
목표 기둥 : 목적지 기둥
중간 기둥 : 남은 중간 기둥
그룹 : 원반 1과 원반 2가 겹친 것

* 가장 큰 원반을 최소 단계로 옮기려면 먼저 그룹을 중간 기둥으로 옮겨야 한다.

원반이 N개를 옮기는 과정

그룹을 시작 > 중간 기둥으로
남은 원반을 시작 > 목표 기둥으로
그룹을 중간 > 목표 기둥으로

#include <stdio.h>

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);  //그룹을 죽안 > 목표 기둥으로 
}

int main(void) {
   int n; //원반 개수 
   printf("하노이의 탑\n원반 개수 : ");
   scanf("%d", &n);
   move(n, 1, 3);
   
   return 0;
}

바닥 원반을 제외한 그룹을 시작 기둥에서 중간 기둥으로 옮긴다.
바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력한다.
바닥 원반을 제외한 그룹을 중간 기둥에서 목표 기둥으로 옮긴다.

5-4 8퀸 문제

8퀸 문제 (8-Queen problem)

서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓는다.
퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능하다.

퀸 놓기 > 8개의 퀸을 놓는 조합이 모두 몇 가지인지 알아보기

1) 체스판은 64칸이므로 처음 퀸을 1개 놓을 때는 64칸 중 아무 곳이나 선택할 수 있다.
경우의 수 : 64 *63 * 62 * 61 * 60 * 59 * 58 * 57 = 178,462,987,637,760

2) 각 열에 퀸을 1개만 배치하기
경우의 수 : 8*8*8*8*8*8*8*8 = 16,777,216

3) 각 행에 퀸을 1개만 배치하기
경우의 수 : 8*8*8*8*8*8*8*8 = 16,777,216

가지 뻗기 (branching)

배열 pos : 퀸의 배치를 나타낸다.
i열에 놓인 퀸의 위치가 j행 : pos[i]의 값은 j
set 함수 : pos[i]에 0부터 7까지의 값을 순서대로 대입하여 i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀 함수이다.
호출된 set 함수는 0열에 1개의 퀸을 배치하는 8가지 조합을 for문에 의해 나열한다.
j값을 0부터 7까지 1씩 증가하며 재귀호출한다.

#include <stdio.h>

int pos[8]; //각 열에서 퀸의 위치 

//각 열의 퀸 위치 출력
void print(void) {
   int i; 
   for(i=0; i<8; i++) 
      printf("%2d", pos[i]);
   putchar('\n');
}

//i열에 퀸 배치
void set(int i) { //열
   int j; //행 
   for(j=0; j<8; j++) {
      pos[i] = j;
      if(i == 7)  //모든 열에 배치를 마침 
         print();
      else
         set(i+1);
    }
}

int main(void) {
   set(0);
   
   return 0;
}

분기 한정법 (각 행에 퀸을 1개만 배치하기)

//각 행, 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열한다. 
#incude <stdio.h>

int flag[8]; //각 행에 퀸을 배치했는지 체크하는 배열 
int pos[8];  //각 열에서 퀸의 위치 

//각 열에서 퀸 위치 출력
void print(void) {
    int i;
    for(i=0; i<8; i++) 
       printf("%2d", pos[i]);
    putchar('\n');
    
}

//i열에서 알맞은 위치에 퀸 배치
void set(int i) {
   int j;
   for(j=0; j<8; j++) {
      if(!flag[i]) { //j행에 퀸을 배치하지 않았다면 
         pos[i] = j;
         if(i == 7)   //모든 열에 배치 마침
            print();
         else {
            flag[i] = 1;
            set(i+1);
            flag[j] = 0;
         }
       }
   }
}

int main(void) {
  int i;
   for(i=0; i<8; i++)
      flag[i] = 0;
   set(0);
 
   return 0;
}

* flag : 같은 행에 중복하여 퀸이 배치되는 것을 방지하기 위한 표시
j행에 퀸을 배치 > flag[j] = 1, 배치되지 않았다면 flag[j] = 0

0행에 퀸을 배치하기 위해 호출한 set 함수는 먼저 0행에 퀸을 배치한다.
flag[0] = 1
그리고 set 함수를 재귀적으로 호출한다.
다음 1열에 퀸을 배치한다.
for문을 0행부터 7행까지 퀸을 배치한다.
0행에 퀸을 배치하는 방법
flag[0] = 1이므로 이 행에는 이미 퀸을 배치했다.
그러므로 set 함수를 재귀호출하지 않는다.
1행에 퀸을 배치하는 방법
flag[1] = 0이므로 아직 퀸을 배치하지 않았다.
set 함수를 재귀호출하여 다음 열인 2번째에 퀸을 배치한다.
재귀 호출한 set(i+1) 함수가 끝나면 퀸을 j행에서 제거했기 때문에 flag[j]에 0을 대입한다.
set함수에서는 퀸을 배치하지 않은 행(flag[j]의 값이 0인 행)에만 퀸을 배치한다.

한정 (bounding) 조작 : 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법
분기 한정법 (branching and bounding method) : 가지 뻗기와 한정 조작을 조합하여 문제를 풀어가는 방법

8퀸 문제를 푸는 프로그램

퀸이 행/열 방향으로 겹쳐지지 않는 조합을 나열한다.
퀸은 대각선 방향으로도 이동할 수 있기 때문에 대각선에서 보더라도 퀸을 1개만 배치하는 한정 조작을 추가해야 한다.

#include <stdio.h>

int flag_a[8];  //각 행에 퀸 배치했는지 확인하는 배열 
int flag_b[15]; //대각선 /에 퀸 배치했는지 체크하는 배열 
int flag_c[15]; //대각선 \에 퀸 배치했는지 체크하는 배열 
int pos[8];     //각 열에서 퀸의 위치 

//각 열에서 퀸 위치 출력
void print(void) {
    int i;
    for(i=0; i<8; i++) 
      printf("%2d", pos[i]);
    putchar('\n');
}

//i열에서 알맞은 위치에 퀸 배치
void set(int 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(void) {
    int i;
    for(i=0; i<8; i++)
        flag_a[i] = 0;
    for(i=0; i<15; i++)
        flag_b[i] = flag_c[i] = 0;
    set(0);
    
    return 0;
}

* flag_b[i+j], flag_c[i-j+7] : i행 j열에서 각각의 대각선 방향에 대해 퀸을 배치했을 때 체크하는 배열 인덱스
각 칸에 퀸의 배치를 체크할 때 같은 행에 퀸을 배치했는지 판단하고 점선 위에 퀸을 배치했는지 검사한다.
가로방향(같은 행), 왼쪽 대각선 방향, 오른쪽 대각선 방향 중 어느 방향이든 1개의 라인이라도 퀸이 배치되었다면 그 칸에는 퀸을 놓을 필요가 없다.
이 경우 실행을 건너뛴다.
3개의 배열을 사용하는 한정 조작을 수행하면 8퀸 문제의 조건을 만족하는 퀸 배치를 효율적으로 수행할 수 있다.

저작자표시 비영리 변경금지

'Algorithm' 카테고리의 다른 글

06. 정렬 (0)	2023.05.05
[백준] 27866(문자와 문자열) c언어 (0)	2023.04.22
[백준] 10813(공 바꾸기) c언어 (0)	2023.04.15
[백준] 10773(제로) c언어 (0)	2023.03.31
04. 스택과 큐 (0)	2023.03.31

'Algorithm' Related Articles

촉촉한초코칩

05. 재귀 알고리즘 본문

05. 재귀 알고리즘

'Algorithm' 카테고리의 다른 글

티스토리툴바