C언어로 복습하는 자료구조 (1) 순환

 

위기감이 느껴진다

개강이 가까워지니까...

 

 

 

순환(recursion)

함수 내에서 자기 자신을 다시 호출하는 알고리즘

거두절미하고 예시로 알아보자...

 

1) 팩토리얼

순환으로 팩토리얼 구현

int fact(int n) {
	if (n <= 1) return 1;
	else return n * fact(n - 1);
}

 

함수 내에서 자기 자신을 호출하고 또 호출하고.... 해서 더는 호출하지 않는 순간이 오면 다시 원래 함수로 리턴 리턴... 해가며 최종 결과를 계산하게 되는 식

순환 호출을 무한히 하면 안 되니까 (알고리즘의 유한성) 순환 알고리즘에는 반드시 순환을 멈추는 부분이 있어야 한다

 

팩토리얼 계산은 순환이 아닌 반복으로도 구현할 수 있는데

int fact(int n) {
	int res = 1;
	for (int i = 1; i <= n; i++)
		res *= i;
	return res;
}

 

이 역시 너무 유명한 예시니까 머...

단순한 코드라 순환 구현과 반복 구현에서 큰 차이가 안 보이지만... 일반적으로는 순환을 사용하는 구현이 더 쉽다. 나도 코드 짤 때 생각하기가 귀찮아서 대부분 순환호출로 다 때우는데...

알고리즘마다 순환이 더 효율적인 게 있고 반복이 더 효율적인 게 있기에 잘 따져보고 쓰는 것이 좋다

물론 팩토리얼의 경우 둘다 O(n)으로 같긴 하지만...

ㄴ 순환: 1번의 순환호출당 1번의 곱셈 수행

ㄴ 반복: for 반복문 n번 실행

순환호출은 호출이 일어날 때마다 호출하는 함수의 상태를 기억해둬야 한다. 이전으로 돌아가야 하니까... 시스템소프트웨어 배울 때 나왔던 내용으로 기억하는데, 리커시브 호출에선 원상태로 돌아가려면 이전 메모리/레지스터 주소를 기억해둬야 한다고... 뭐 그랬던 것 같다

그러니까 순환은 여분의 기억장소가 필요하다는 뜻

즉 이 경우에는 그런 게 필요없는 반복 구현이 좀더 효율적이다

 

 

2) 거듭제곱

x의 n승을 구하려면?

먼저 순환

갑자기 머리를 써야된다 벌써 하기가 싫다 큰일남

의사코드를 써보자

x의 n승은 (x의 2승)의 n/2승이니까 n에 따라 분기를 나눌수있겠다

 

power(x, n):

if n==0 then return 1

else if (n이 짝수) then return power(x제곱, n/2)

else if (n이 홀수) then return x*(power(x제곱, (n-1)/2))

double power(double x, int n) {
	if (n == 0) return 1;
	else if (n % 2 == 0) return power(x * x, n / 2);
	else return x * power(x * x, (n - 1) / 2);
}

 

벌써 어려우면 이분야를 접는것이 맞는것같으나 갈 데가 없네 정말 슬프다

미리미리 잘하는 것을 찾아두도록 하자

난 틀렷음

 

여튼 그렇다

보면 알 수 있듯 순환으로 구현한 거듭제곱 알고리즘은 매 실행마다 문제의 크기가 1/2로 줄어든다

2의 n승을 구하기 위해 이 함수를 실행할 경우 문제는 매 실행마다 2의 n승 -> 2의 n-1승 -> 2의 n-2승 -> ... 2의 0승으로 크기가 줄어드는 것

즉 복잡도는 O(log2(n))이다

 

반복으로 구현한다면

double power2(double x, int n) {
	double res = 1.0;
	for (int i = 0; i < n; i++)
		res *= x;
	return res;
}

 

아까 일반적으로는 순환을 쓰는 게 머리 덜 써도 되어서 편하다고 했는데 이 경우에는 반대다... 반복이 훨씬 쉽다

그치만 머리를 쓰지 않는 대가를 치뤄야 하는 법

얘는 단순 n번 반복문이기에 O(n)의 복잡도를 가진다

즉 이 경우에는 순환을 쓰는 것이 훨씬 효율적인 것이다

 

 

3) 피보나치 수열의 항

0, 1, 1, 2, 3, 5, 8, 13, 21...

첫번째 두번째 항은 0, 1로 시작하고 이후 항은 앞의 두 수를 더한 값과 같은 수열

먼저 순환으로 구현해보자...

int fib(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fib(n - 2) + fib(n - 1);
}

 

와! 머리를 조금도 쓰지 않고 만들 수 있는 코드

당연히 비효율적이다

중복된 계산이 너무 많은 이 코드는 복잡도가 무려 O(2의 n승) 이다

지수 복잡도를 가진 코드는 그냥.. 잘못만들어진게 맞다 숫자가 좀만 커져도 계산을 못한다

 

그럼 반복으로는

int fib(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	int pp = 0, p = 1;
	int res = 0;
	for (int i = 2; i <= n; i++) {
		res = pp + p;
		pp = p;
		p = res;
	}
	return res;
}

 

바로 전 항과 전전 항을 반복마다 바꿔주는 식으로 구현이 가능하다

복잡도는 for 반복문만 봐주면 되니까 O(n)으로 훨씬 간단해진다

 

 

4) 하노이탑 문제

막대가 세 개 있고, 한 막대에 모두 꽂혀 있는 원판들을 다른 막대로 모두 옮기는 문제

원판은 크기가 큰 것이 무조건 아래로 가야 한다

 

하노이탑은 순환 알고리즘에 적합한 문제로 매우 유명하다..

어떤 식으로 구현하냐면

막대가 A, B, C 세 개가 있고 원판이 n개 존재하며, A 막대에 있는 원판을 C 막대로 전부 옮긴다고 치자

그럼 먼저 n-1개의 원판을 B로 전부 옮겨주고, A에 남은 n번째 원판을 C로 옮긴다

이후 B에 있는 n-1개의 원판에서 n-2개를 A로 전부 옮겨주고, B에 남은 n-1번째 원판을 C로 옮긴다

이걸 반복하면 되겠다...

 

의사코드로 써보면

hanoi(n, from, tmp, to) //n=원판개수, from=처음 원판이 꽂혀있는 막대, to=목표지점이 되는 막대

if (n==1) then from에 있는 원판을 to로 옮김

else

1) from에 있는 원판 중 마지막 것을 제외한 나머지를 tmp로 옮김

2) from에 있는 원판 하나를 to로 옮김

3) tmp에 있는 원판들을 to로 옮김

 

구현하자

void hanoi(int n, char from, char tmp, char to) {
	if (n == 1) printf("원판 1, %c -> %c\n", from, to);
	else {
		hanoi(n - 1, from, to, tmp);
		printf("원판 %d, %c -> %c\n", n, from, to);
		hanoi(n - 1, tmp, from, to);
	}
}

 

그런 것이다

이해만 하면 순환 구현은 정말 쉽다...

이러니 자꾸 머리 안 쓰고 헤헤 무지성순환빔 해버리지

 

 

연습문제도 몇개만 풀어보자..

 

14. 1 + 1/2 + 1/3 + ... + 1/n을 계산하는 순환적인 프로그램

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

숫자가 점점 작아지니까 순환호출에서 n-1을 매개변수로...

 

16. 다음 순환 프로그램을 반복구조의 비순환적 프로그램으로 바꾸기

int sum(int n){

if(n==1) return 1;

else return (n+sum(n-1)); }

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

 

17. 이항계수 (binomial coefficient) 구현

nCk 그거 얘기다..

nCk는 다음과 같이 정의된다

n-1Ck-1 + n-1Ck (if 0<k<n)

1 (if k=0 or k=n)

 

우선 순환구현

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

정의대로만 만들면 되니 쉬울 수밖에...

 

다음 반복구현

nCk를 계산하는 공식은 n! / k!(n-k)! 이다

앞서 만들었던 팩토리얼 함수를 이용해서

int fact(int n) {
	int res = 1;
	for (int i = 1; i <= n; i++)
		res *= i;
	return res;
}

int binomial(int n, int k) {
	int res = fact(n) / (fact(k) * fact(n - k));
	return res;
}

 

그렇게 만들어줄 수 있다

 

알고리즘은 왜이렇게 머리가 아플까

적성이 아닌것같애 역시...