프로그래밍 언어에서 되풀이하는 방법으로는 반복(iteration)과 순환(recursion)이 있다.

반복은 for나 while 등의 반복 구조를 사용해 반복하는 것을 말하며, 대부분의 경우 순환에 비해 간명하고 효율적이다.

그러나 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 순환은 반복에 비해 알고리즘을 훨씬 명확하거나 간결하게 나타나낼 수 있는 장점을 가지기도 한다.


순환 중에서 끝에서 이루어지는 순환을 꼬리 순환(tail recursion)이라 하고, 앞에서 이루어지는 순환을 머리 순환(head recursion)이라 한다. 

꼬리 순환은 반복 알고리즘으로 쉽게 바꾸어 쓸 수 있으나, 머리 순환이나 함수 내부 여러 군데에서 자기 자신을 호출하는 경우(multi recursion) 쉽게 반복 알고리즘으로 바꿀 수 없다.

일반적으로 동일한 알고리즘을 꼬리 순환과 머리 순환 중 어떤 것으로든 바꿀 수 있다면, 꼬리 순환을 선택하여야 한다.


이번에는 거듭제곱 값 계산을 통해 순환 알고리즘이 반복 알고리즘보다 빠른 경우를 살펴 보겠다.

간단하게 생각 할 수 있는 반복 알고리즘을 사용해 코드를 작성해보았다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
 
double power_iteration(double x, int n) { // x는 밑, n은 지수이다.
    int i;
    double r = 1.0;
    for (i = 0; i < n; i++)
       r = r * x;
    return (r);
}
 
int main(void) {
    double base = 2.0;
    int exponent = 10;
    double result;
    
    result = power_iteration(base, exponent);
    printf("계산 결과: %.2f\n", result);
    
    return 0;
}
cs


다음으로는 순환 알고리즘을 통해 코드를 작성하겠다.

순환에서 중요한 것은 순환을 할 때마다 문제의 크기가 작아진다는 것이다.

거듭제곱에서는 어떻게 크기를 줄일 수 있을까?


먼저 x^n 이라는 거듭제곱이 있을 때 n이 짝수라고 생각해보자.

이 때 지수를 줄일 수 있는 방법은 x^n 을 (x^2)^(n/2)로 표현하는 것이다.


n이 홀수일 때는 n이 짝수가 될 수 있도록 해주면 된다.

x^n 은 곧 x * x^(n-1)이고 n이 홀수이므로 n-1은 짝수이다.

x^(n-1)은 거듭제곱 꼴이고 지수가 짝수이므로, 위에서 사용한 방법을 사용하면 (x^2)^((n-1)/2))라고 할 수 있다.

즉 n이 홀수인 경우 x^n은 x * (x^2)^((n-1)/2))이다.


이러한 개념을 이용해 코드를 작성하면 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
 
double power_recursion(double x, int n) { // x는 밑, n은 지수이다.
    if (n == 0) return 1;
    else if ((n % 2) == 0) // n이 짝수인 경우
        return power_recursion(x*x, n/2);
    else return x * power_recursion(x*x, (n-1)/2); // n이 홀수인 경우
}
 
int main(void) {
    double base = 2.0;
    int exponent = 10;
    double result;
    
    result = power_recursion(base, exponent);
    printf("계산 결과: %.2f\n", result);
    
    return 0;
}
cs


글을 시작할 때 대부분의 경우에는 반복이 순환보다 효율적이다고 하였다.

하지만 이 경우는 순환이 더 효율적이다.

어째서일까?


이는 아까 언급한 바와 같이 순환 호출이 이루어 질 때마다 문제의 크기가 작아지기 때문이다.

예를 들어 n을 100이라고 가정하자.

이 때 n의 크기는 호출 할 때 마다 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1 로 작아진다.

즉 순환 알고리즘의 시간 복잡도는 O(logn)이다.


반면 반복 알고리즘일 때는 n이 100이라면 100번의 연산이 이루어진다.

따라서 반복 알고리즘의 시간 복잡도는 O(n)이다.


이번 예제를 통해 일반적인 경우와 달리 순환 알고리즘이 반복 알고리즘보다 효율적인 경우를 살펴보았다.



'C언어 > 자료구조' 카테고리의 다른 글

[C][순환][반복] 이항 계수 계산  (0) 2018.09.24
[C][순환] 하노이의 탑 계산  (0) 2018.09.23
[C][순환][반복] 피보나치 수열 계산  (0) 2018.09.20

문제


Hello World!를 출력하시오.


코드


1
2
3
4
5
6
#include <stdio.h>
 
int main(void) {
    printf("Hello World!\n");
    return 0;
}
cs


먼저 strlen은 문자열의 길이를 구하는 함수이다. 이 때 null 문자인 '\0'은 포함하지 않는다. strlen 함수는 string.h 헤더에 선언되어있다.


반면 sizeof는 연산자로 피연산자의 메모리 크기를 바이트 단위로 계산한다. 상수, 변수 뿐만 아니라 자료형 그 자체가 피연산자가 될 수 있다. 연산자이기 때문에 상수나 변수의 경우 반드시 괄호를 사용해 묶을 필요는 없다. (자료형의 크기를 구할 때는 괄호를 사용하여야 한다.) 하지만 sizeof는 높은 연산자 우선순위를 가지고 있기 때문에 피연산자가 단항이 아니라면 일반적으로 괄호로 묶어준다. 또한 size는 컴파일타임 연산자이기 때문에 sizeof와 피연산자는 컴파일 단계에서 결과 값을 가진다. (정수 a가 있을 때 sizeof ++a 나 sizeof a++은 a의 값을 변화시키지 않는다.)


예제를 통해 살펴보자.


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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main() 
{
 char *str1 = "MoscowMule";
 char str2[20] = "MoscowMule";
 char *str3 = (char *)malloc(sizeof(char) * 20);
 str3 = "MoscowMule";
 
 printf("sizeof(str1): %d\n", sizeof(str1));
 printf("sizeof(str2): %d\n", sizeof(str2));
 printf("sizeof(str3): %d\n", sizeof(str3));
 
 printf("strlen(str1): %d\n", strlen(str1));
 printf("strlen(str2): %d\n", strlen(str2));
 printf("strlen(str3): %d\n", strlen(str3));
 
 printf("printf(str1): %s\n", str1);
 printf("printf(str2): %s\n", str2);
 printf("printf(str3): %s\n", str3);
 
 return 0;
}
cs


위 코드를 실행 시키면 아래와 같은 출력이 나온다


sizeof(str1): 4
sizeof(str2): 20
sizeof(str3): 4
strlen(str1): 10
strlen(str2): 10
strlen(str3): 10
printf(str1): MoscowMule
printf(str2): MoscowMule
printf(str3): MoscowMule
cs


sizeof 부터 살펴보자.

  • str1은 포인터 변수이기 때문에 32비트 시스템에서는 4바이트(32비트), 64비트 시스템에서는 8바이트(64비트)의 크기를 갖는다. 포인터는 메모리 위치를 가리키는 주소를 담고 있는데, 시스템 마다 지원하는 주소의 비트수가 다르고 결국 포인터 크기도 달라지는 것이다. 여기에서는 32비트로 컴파일 하였기 때문에 4바이트라는 결과가 나왔다.
  • str2은 문자열인데 자료형 char은 각각 1바이트이므로 20바이트의 크기를 가진다. 만약 char str2[] = "MoscowMule"; 라고 하였으면 null 문자까지 포함해 11바이트가 되었을 것이다.
  • str3 역시 str1과 같은 포인터 변수이기 때문에 동일하게 크기는 4바이트이다.

다음은 strlen과 printf 이다.

결국 세 변수 (str1, str2, str3)은 모두 "MoscowMule"이라는 같은 문자열이다.

따라서 strlen을 사용하면 null 문자를 제외한 길이인 10이 나오게 되고, printf를 사용하면 그대로 출력이 된다.


틀린 내용이나, 수정해야할 부분이 있다면 댓글로 남겨주십시오.

바로 조치하겠습니다. 감사합니다.

+ Recent posts

티스토리툴바