[자료구조] 순환 알고리즘과 반복 알고리즘 비교

1. 순환 알고리즘

같은 프로그램에 대해서 순환알고리즘을 사용하는 경우와 반복알고리즘을 사용하는 경우가 있습니다.

어떤 프로그램이냐에 따라 두 알고리즘의 효율성이 다르게 작용합니다.

두 알고리즘의 차이를 비교해가며 코드를 먼저 풀이해보시고 설명을 확인해보시기 바랍니다.

 

 

 

1-1. 다음을 계산하는 순환 함수를 작성하라

> 1 + 2 + 3 + … + n

int factorial (int n) { 
  if ( n == 1 )
    return 1;
  else if ( n >= 2 )
    return ( n + factorial (n - 1) );
}

함수 설명

(1) factorial 함수에 n을 매개변수로 보냅니다

(2) n이 1이면 1을 return합니다

(3) n이 1이 아니고 2와 같거나 크면 n을 return함과 동시에 factorial 함수에서 n - 1의 값을 다시 순환 호출합니다

 

예시

(ex) n이 3이라면

>> return 3 + factorial (2)

>> return 3 + 2 + factorial (1)

>> return 3 + 2 + 1

 

 

 

1-2. 다음을 계산하는 순환 함수를 작성하라

> 1 + 1/2 +1/3 + … + 1/n

double factorial2 (double n) { 
  if ( n == 1 ) 
    return 1;
  else
    return ( 1 / n + factorial2( n - 1 ));
}

함수 설명

(1) factorial2 함수에 double형 n을 매개변수로 보냅니다

(2) n이 1이면 1을 return합니다

(3) n이 1이 아니면 1 / n을 return함과 동시에 factorial2 함수에 n - 1의 값을 다시 순환 호출합니다

 

예시

(ex) n이 5라면

>> return 1 / 5 + factorial2 (4)

>> return 1 / 5 + 1 / 4 + factorial2 (3)

>> return 1 / 5 + 1 / 4 + 1 / 3 + factorial2 (2)

>> return 1 / 5 + 1 / 4 + 1 / 3 + 1 / 2 + factorial (1)

>> return 1 / 5 + 1 / 4 + 1 / 3 + 1 / 2 + 1

>> return 2.283333

 

 

 

1-3. N까지의 정수들 중 3의 배수의 합을 구하여 반환하는 순환함수를 작성하라.

int factorial3 (int n) {
  if( n == 0) 
    return 0;
  else if ( n % 3 == 0 )
    return n + factorial3(n - 1);
  else
    return factorial3(n - 1);
}

함수 설명

(1) factorial3 함수에 int형 n을 매개변수로 보냅니다

(2) n이 0이면 0을 return합니다

(3) n이 0이 아니고 n을 3으로 나누었을 때 나머지가 0이면(3의 배수이면) 현재의 n값을 return함과 동시에 factorial3 함수에 n - 1의 값을 다시 순환 호출합니다

(4) n이 0이 아니고 3의 배수도 아니라면 n - 1의 값을 다시 순환 호출합니다

 

예시

(ex) n이 6이라면

>> return 6 + factorial3 (5)

>> return 6 + factorial3 (4)

>> return 6 + factorial3 (3)

>> return 6 + 3 + factorial (2)

>> return 6 + 3 + factorial (1)

>> return 6 + 3 + factorial (0)

>> return 6 + 3 + 0

 

 

 

1-4. Binomial coefficient를 계산하는 순환함수를 작성하라.

int nCr(int n, int r) {
  if (r == 0 || r == n) {
    return 1;
  } else {
    return nCr(n - 1, r - 1) + nCr(n - 1, r);
  }
}

함수 설명

(1) nCr 함수에 int형 n과 r을 보냅니다

(2) r값이 0이거나 n의 값과 같으면 1을 return합니다 (* 4개(n) 중 4개(r)를 조합하여 얻는 경우의 수는 1이므로)

(3) r값이 0이거나 n의 값과 같지 않으면 nCr함수에 n - 1, r - 1의 값을 넣고 다시 호출하고 n - 1, r의 값을 넣고 다시 호출합니다

 

예시

(ex) n이 6, r이 3이라면

>> return nCr(5, 2) + nCr(5, 3)

>> return (nCr(4, 1) + nCr(4, 2)) + (nCr(4, 2) + nCr(4, 3))

>> return (   4개   + nCr(3, 1) + nCr(3, 2)) + (nCr(3, 1) + nCr(3, 2) + nCr(3, 2) + nCr(3, 3)

>> return (         +   3개    + nCr(2, 1) + nCr(2, 2)) + (   3개   + nCr(2, 1) + nCr(2, 2) + nCr(2, 2) + nCr(2, 1) + 1개

>> return (         +          +   2개   +   1개   + (         +   2개   +    1개   +   1개   +   2개

>> return 20

 

 

 

1-5. Ackermann 수를 계산하는 순환함수를 작성하라.

int A(int m, int n)
{
    if (m == 0)
    {
        return n + 1;
    }
    if (m > 0 && n == 0)
    {
        return A((m - 1), 1);
    }
    if (m > 0 && n > 0)
    {
        return A((m - 1), A(m, (n - 1)));
    }
}

함수 설명

(1) 아커만 함수 A에 int형 m과 n을 보냅니다

(2) m이 0이면 n + 1을 return합니다

(3) m이 0이 아니고 0보다 크고 n이 0이면 A함수에 m - 1의 값과 1을 넣고 다시 순환 호출합니다

(4) m이 0이 아니고 0보다 크면서 n도 0보다 크면 A함수에 m - 1의 값과 A함수에 m과 n - 1의 값을 넣고 반환되는 값을 넣어 다시 순환 호출합니다

 

예시

(ex) m이 2, n이 1이라면

>> return a(1, a(2, 0))

           a(1, a(1, 1))

           a(1, a(0, a(1, 0)))

           a(1, a(0, a(0, 1)))

           a(1, a(0, 2))

           a(1, 3)

>> return a(0, a(1, 2))

           a(0, a(0, a(1, 1)))

           a(0, a(0, a(0, a(1, 0))))

           a(0, a(0, a(0, a(0, 1))))

           a(0, a(0, a(0, 2)))

           a(0, a(0, 3))

           a(0, 4)

           5

 

 

2. 반복 알고리즘

 

 

2-1. 다음을 계산하는 반복 함수를 작성하라

> 1 + 2 + 3 + … + n

int roop(int n) {
  int sum = 0;
  for(int i = 1; i <= n; ++i)
    sum += i;
  
  return sum;
}

함수 설명

(1) int형 n을 roop함수의 매개변수로 보냅니다

(2) int형 sum을 0으로 초기화합니다

(3) int형 i는 1로 초기화하고 n과 같거나 n보다 작을 때까지 반복하고 i를 전위형으로 1씩 증가시킵니다

(4) sum의 값에 현재의 i값을 추가하여 할당합니다

 

예시

(ex) n이 5라면

>> return 15

 

 

 

다음을 계산하는 반복 함수를 작성하라

> 1 + 1/2 +1/3 + … + 1/n

double roop2(int n) {
  double sum = 1;
  for(double i = 2; i <= n; ++i)
    sum += 1 / i;
  
  return sum;
}

함수 설명

(1) int형 n을 roop2함수의 매개변수로 보냅니다

(2) double형 sum을 1로 초기화합니다

(3) double형 i는 2로 초기화하고 n과 같거나 n보다 작을 때까지 반복하고 i를 전위형으로 1씩 증가시킵니다

(4) sum의 값에 1 / i값을 추가하여 할당합니다

 

예시

(ex) n이 5라면

>> return 2.283333

 

 

 

N까지의 정수들 중 3의 배수의 합을 구하여 반환하는 반복함수를 작성하라.

int roop3(int n) {
  int sum = 0;
  for(int i = 1; i <= n; ++i)
    if (i % 3 == 0)
      sum += i;
  
  return sum;
}

함수 설명

(1) int형 n을 roop3함수의 매개변수로 보냅니다

(2) int형 sum을 0으로 초기화합니다

(3) int형 i는 1로 초기화 하고 n과 같거나 n보다 작을 때까지 반복하고 i를 전위형으로 1씩 증가시킵니다

(4) i를 3으로 나눈 나머지가 0이면(3의 배수이면) sum의 값에 i를 추가하여 할당합니다

 

예시

(ex) n이 9라면

>> return 18

 

 

 

Binomial coefficient를 계산하는 반복함수를 작성하라.

int nCr_roop(int n){
    if(n == 0) return 1;
    int result = 1;
    
    for(int i = n; i >= 1 ; --i){
        result *= i;
    }
 
    return result;
}

함수 설명

(1) int형 n을 nCr_roop 함수의 매개변수로 보냅니다

(2) n이 0이라면 1을 return합니다

(3) int형 result를 1로 초기화합니다.

(4) int형 i를 n으로 초기화하고 1과 같거나 1보다 작을때까지 반복하고 i를 후위형으로 1씩 증가시킵니다

(5) result의 값에 i를 곱한 값을 추가하여 할당합니다

(6) main에서 선언된 result는 이항계수의 결과값으로써 이항계수 공식(n! / r!(n-r!)에 따라 nCr_roop(n) / (nCr_roop(r) * nCr_roop(n - r)) 로 설정합니다

 

예시

(ex) nCr_roop(6) / (nCr_roop(3) * nCr_roop(6 - 3)) 이라면

>> return 720 / 6 * 6

>> return 20

 

 

 

다음 함수를 반복 함수로 변환하라.

// 변환 전
int sub (int n) {
  if (n<0) return 0;
  return n  + sub (n-3);
}

// 변환 후
int sub2 (int n) {
  int sum = 0;
  int i = 0;
  while (i < n) {
    sum += n;
    n -= 3;
  }
  return sum;
}

함수 설명

(1) int형 n을 sub2 함수의 매개변수로 보냅니다

(2) int형 i와 sum을 0으로 초기화합니다

(3) i가 n보다 작을때까지 반복하고 sum에는 n의 값을 추가하여 할당하고 n은 3을 뺀 값을 할당합니다

 

예시

(ex) sub2(88) 이라면

>> return 1335