nov.Zip

* 다음 포스팅은 Hash 자료구조의 개념에 대한 내용을 포함하고 있습니다.

실질적인 구현 및 C++ STL map의 사용 방법에 대한 정보를 원하시는 분은 다음 포스팅을 참고해 주세요.

* 개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있으며,

지속적으로 수정 및 보완 해 나갈 예정입니다. 언제나 지적은 환영합니다!

Related

→ C++ STL map 사용 방법 정리

→ Hash 자료구조 구현 with C/C++ (미완성)

_Contents

#1 About Hash DataStructure

- Hashing & Hash Function

#2 Collision

- Chaining : 체이닝

- Open Addressing : 개방 주소법

#3 Hash 장단점

#1 About Hash DataStructure

Hash는 Key - Value 쌍으로 데이터를 저장하는 자료구조 입니다.

이 때 데이터를 그냥 저장시키는 것이 아닌 해시 함수 (Hash Function) 라는 것을 사용해 Key 값을 Hash 값으로 바꾸어 준 뒤, 이 바꾼 Hash 값을 주소로 삼아 데이터를 Hash 값과 함께 저장합니다.

여기서 왜 굳이 번거롭게 Hash Function 까지 사용해 가며 키 값을 변환하여 저장해야 하는지 의문이 생길 수 있습니다.

학번과 학생의 이름을 저장한 뒤, 학번을 이용해 학생을 검색하는 프로그램을 제작하는 의뢰를 받았다고 가정해 봅시다.

학번은 총 10자리로 구성되어 있으며 학번과 학생의 데이터베이스는 다음과 같습니다.

그러면 이제 어떤 자료구조를 이용해 데이터베이스에 담긴 정보를 저장해야 할까요?

배열을 사용해 저장해 보도록 합시다. 가장 쉽게 떠오를 수 있는 방법인데, 배열에 학번이 될 수 있는 모든 경우의 메모리를 저장한 뒤 학생의 정보를 저장하는 것 입니다.

하지만 학번의 모든 가짓수를 배열로 저장하려면 학번이 총 10자리 이기에 10¹⁰ 가지 즉, 10000000000 10GB의 메모리가 필요하게 됩니다. 배열을 사용하는 것은 사실상 불가능합니다.

- Hashing & Hash Function

이번에는 Hash 자료구조를 이용해 봅시다. 앞에서 설명했듯이 Hash Function을 이용할 것 입니다. Hash Function 이란 임의 길이의 데이터를 고정된 길이의 Hash로 변경해주는 역할을 수행하는 함수입니다.

다음 예제에서는 Hash Function 이 10자리의 학번 중 가장 뒤에 끝 4자리만 떼와서 새로운 테이블에 저장합니다.

이러한 과정을 Hashing 이라고 하며, Hash Function 을 사용해 새롭게 제작된 테이블은 Hash Table 이라고 부릅니다.

#2 Collision

언뜻보면 완벽할 것 같은 Hash도 만능은 아닙니다. 

예를들어 23년에 12번째로 minji 라는 학생이 새로 대학에 입학했다고 가정해 봅시다. 앞에서 수행했던 것과 같이 학번 정보를 Hash Function에 넣었더니, 해시 값으로 "0012"가 출력되어 Hash Table에 저장되었습니다.

하지만 0012는 이미 존재하는 key값입니다. 

이처럼 Collision(충돌)이란 서로 다른 키가 같은 해시 값을 가지게 될 경우 발생하는 문제점입니다.

이러한 충돌을 회피하기 위한 방안으로 크게 Chaining 기법과 Open Addressing 기법으로 나뉩니다.

- Chaining : 체이닝

Chaining은 Hash Table의 각 인덱스에 연결 리스트 혹은 벡터와 같은 자료 구조를 하나씩 두어 충돌을 회피하는 기법입니다.

실제로 C++ STL 의 map 컨테이너는 체이닝 기법을 토대로 구현되어 있습니다.

만약 위 상황과 같이 해시 값 충돌이 발생해도 그냥 연결 리스트로 연결해 주기만 하면 됩니다.

그러나 극단적으로 모든 키의 해시 값이 같은 상황이 발생했을 때 O(N)의 탐색 시간이 소요됩니다.

- Open Addressing : 개방 주소법

Open Addressing 은 인덱스에 바로 key - value 쌍을 작성하는 기법입니다.

만약 해시 값 충돌이 발생하면 비어있는 다음 블록을 찾아 저장합니다. 

이 때 비어있는 블록을 찾아가는 방법 또한 여러가지가 있는데, 이건 추후에 다른 포스팅에서 정리 하도록 하겠습니다.

#3 Hash 장단점

장점 : (Hash Function이 잘 구현되어 있다는 가정 하에) Insertion(추가), Deletcion(삭제), Search(검색) 연산의 시간복잡도가 O(1)으로 매우 효율적입니다.

Key를 이용해 빠르게 value에 조작할 수 있습니다.

단점 : 데이터가 저장되기 이전에 미리 저장 공간을 확보해 놓아야 하기에 메모리 효율이 떨어집니다.

Hash Function 의존도가 높습니다. 효율이 떨어지는 Hash Function을 채택할 경우 Hash Table의 시간 복잡도가 최대 O(원소의 개수) 까지 늘어날 가능성이 있습니다.

이상으로 Hash 자료구조의 원리와 구조에 대해 간략하게 정리해 보았습니다.

도움이 되셨다면 공감 부탁드립니다!

* 개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있습니다.

* 다음 포스팅은 Linked List (연결 리스트) 자료구조의 개념에 대한 내용을 포함하고 있으며 실질적인 구현 및 STL list의 사용 방법에 대한 정보를 원하시는 분은 다음 포스팅을 참고해 주세요.

연관 포스팅

→ Linked List 구현 with C/C++ (미완성)

→ C++ STL List 사용 방법

_Contents

#1 연결 리스트란?

#2 연결 리스트의 종류

#2.1 단일 연결 리스트 (Singly Linked List)

#2.2 이중 연결 리스트 (Doubly Linked LIst)

#2.3 원형 연결 리스트 (Circular Linked List)

#3 연결 리스트의 시간 복잡도

#3.1 N번째 원소 탐색

#3.2 원소 삽입

#3.3 원소 삭제

#4 배열 vs 연결 리스트

#1 연결 리스트란?

연결 리스트 (Linked List) 란 원소들 사이의 선후 관계가 일대일로 대응되는 선형 자료구조 입니다. 즉, 원소를 저장할 때 다음 원소의 위치 정보를 포함 시키는 방식으로 구현되어 있습니다.

원소 5 10 15 20 을 배열 자료구조를 이용해 저장해 보도록 하겠습니다. 

int arr[5] = {5, 10, 15, 20};

그러면 다음과 같이 인덱스 0번부터 3번까지 원소가 메모리에 연속되게 저장됩니다.

이번에는 연결 리스트 자료구조를 활용해 원소들을 저장해 보겠습니다. C++ STL 의 list 컨테이너를 사용했습니다.

(앞서 미리 얘기했듯이, 이번 포스팅에서는 리스트 자료구조의 사용방법에 대한 내용을 포함하고 있지 않습니다.)

list<int> myList {5, 10, 15, 20};

배열과 달리 메모리에 연속적으로 저장되지 않으며, 각 원소가 다음 원소에 대한 위치 정보를 포함하고 있습니다.

#2 연결 리스트의 종류

연결 리스트는 크게 3가지 종류로 구분할 수 있습니다.

#2.1 단일 연결 리스트 (Singly Linked List)

가장 기본적인 형태의 연결 리스트입니다. 각 원소가 다음 원소의 주소의 정보를 포함하고 있는 연결 리스트 입니다.

#2.2 이중 연결 리스트 (Doubly Linked List)

각 원소가 이전 원소의 주소 정보와 다음 원소의 주소 정보를 모두 들고 있는 형태의 연결 리스트 입니다. 

단일 연결 리스트와 달리 각 원소 마다 메모리를 하나 씩 더 사용해야 한다는 단점이 있습니다. C++ STL List 컨테이너는 이중 연결 리스트로 구현되어 있습니다. 

#2.3 원형 연결 리스트 (Circular Linked List)

마지막 원소와 첫 번째 원소가 연결되어 있는 형태의 연결 리스트입니다.

#3 연결 리스트의 시간 복잡도

#3.1 N번째 원소 탐색

연결 리스트에서 N번째 원소를 탐색하기 위해선, O(N)의 시간이 소요됩니다. O(1)에 바로 원소에 접근할 수 있는 배열과 달리 상당히 비효율 적 이라고 할 수 있습니다.

원리는 어찌보면 당연한데 {5, 10, 15, 20} 의 원소가 저장된 연결 리스트에서 원소 15를 탐색하기 위해선 첫 번째 원소인 5부터 순차적으로 탐색해 나가야 되기 때문입니다.

#3.2 원소 삽입

연결 리스트에서 원소를 추가하는 연산은 O(1)의 시간의 소요됩니다. 예를 들어 원소 10과 15 사이에 13 이라는 원소를 새로 추가해 보도록 하겠습니다.

10이 가리키는 주소를 15의 주소에서 13의 주소로 변경하고 13이 가리키는 주소를 15로 변경하기만 하면 됩니다.

#3.3 원소 삭제

원소 삭제 연산 또한 O(1)의 시간이 소요됩니다. 원소 13을 삭제하는 상황을 예시로 들어보면 원소 10이 가리키는 주소를 13에서 15로 변경해 주기만 하면 됩니다. 물론 연결 리스트를 실제로 구현할 시 원소 13은 가비지 값이 되기에 따로 처리해 주어야 합니다.

#4 배열 vs 연결 리스트

마지막으로 배열과 연결 리스트를 비교해 보고 마치도록 하겠습니다.

* Overhead (추가 필요 공간) - 앞서 설명했듯이 연결 리스트는 각 원소가 다음 혹은 이전의 주소값을 포함하고 있습니다.

따라서 32bit 컴퓨터의 경우엔 4Nbyte 64bit 컴퓨터의 경우엔 8Nbyte의 메모리 공간이 추가로 필요합니다.

정리하자면 배열은 원소에 접근하는 데는 효율적이지만 원소 삽입 & 삭제에 있어서는 비효율적입니다.

반대로 연결 리스트는 원소에 접근하는 데는 비효율적 이지만 원소 삽입 & 삭제는 O(1)으로 효율적입니다.

따라서 원소의 삽입과 삭제가 빈번하게 일어나는 경우에는 연결 리스트 사용을 고려해 보는 것이 좋습니다.

* 개인적인 공부 내용을 기록하는 용도로 작성한 글 이기에 잘못된 내용을 포함하고 있을 수 있습니다.

_contents

#1 소수 구하기

#2 에라토스테네스의 채

_ref

https://www.youtube.com/watch?v=5ypkoEgFdH8

#1 소수 구하기

소수(PrimeNumber)란 1과 자신만을 약수로 가지고 있는 자연수를 의미한다. 프로그래밍으로 소수를 구하는 다양한 방식의 알고리즘이 존재하는데, 어떤 알고리즘을 선택하느냐에 따라 시간복잡도가 달라진다.

첫 번째로 소개할 소수 판별 알고리즘 코드는 다음과 같다.

// isPrimeNumber 시간복잡도 : O(N) 
// 2 ~ x - 1 의 수 중에서 하나라도 약수가 존재하면 소수가 아니다.
bool isPrimeNumber(int x){
	for(int i = 2; i < x; i++)
		if(x % i == 0) return false;
	return true;
}

1과 자신을 제외한 수 (즉, 2 ~ x - 1) 를 반복문을 돌려 자기 자신과 나누어 나머지가 존재하는 지 판별하는 브루트포스 방식 알고리즘이다.

구현이 간단하다는 장점이 있지만 시간복잡도가 O(N)으로 효율이 떨어지는 알고리즘이다.

#include <iostream>
using namespace std;

bool isPrimeNumber(int x){
	for(int i = 2; i < x; i++)
		if(x % i == 0) return false;
	return true;
}

int main(){
	cout << isPrimeNumber(7) << '\n'; // true
	cout << isPrimeNumber(10) << '\n'; // false;
	return 0;
}

[결과]
1
0

다음으로 소개할 소수 판별 알고리즘은 시간복잡도가 O(N^(1/2))로 앞서 소개한 알고리즘보다 다소 효율적인 알고리즘이다. 소수 판별 시 약수들이 대칭을 이루고 있다는 성질을 이용한 알고리즘이다.

8을 예로 들어보면 8의 약수는 1, 2, 4, 8이다. 여기서 1과 8(자신)을 제외하면 남은 약수는 2와 4이다.

이 때 2와 4는 2 * 4 = 8로 대칭 관계이기 때문에 굳이 4를 판별하지 않고 2까지만 탐색하여도 8이 소수가 아님을 확인할 수 있다.

따라서 n - 1 까지 모두 탐색하는 것이 아닌 n의 제곱근 까지만 for문으로 탐색을 진행하여 약수가 존재하는 지 확인하면 된다.

* <math.h>의 sqrt 함수를 이용해 제곱근을 계산하였다.

#include <iostream>
#include <math.h> // sqrt
using namespace std;

// isPrimeNumber2 시간복잡도 : O(N^((1/2)))
// 소수를 판별할 때 약수들이 대칭을 이루고 있다는 점을 이용한 알고리즘
bool isPrimeNumber2(int x){
	int end = (int) sqrt(x);
	for(int i = 2; i <= end; i++)
		if(x % i == 0) return false;
	return true;
}

int main(){
	cout << isPrimeNumber2(7) << '\n'; // true
	cout << isPrimeNumber2(10) << '\n'; // false;
	return 0;
}

#2 에라토스테네스의 채

에라토스테네스의 채는 대량의 소수를 한꺼번에 판별할 때 사용되는 알고리즘이다.

가장 먼저 소수를 판별할 범위를 배열에 저장한 뒤, 범위 내에서 소수가 아닌 자연수를 제거해 나가는 방식이다.

1 ~ 25 범위의 자연수를 에라토스테네스의 채를 이용해 소수를 판별해 보도록 하자.

1> 2차원 배열을 생성하여 소수를 판별할 범위(1 ~25)의 수를 초기화한다.

2> 1은 탐색 범위에서 제외하고 2의 배수를 배열에서 제거한다. 이 때 2는 제거하는 자연수에 포함시키지 않는다.

3> 다음으로 3의 배수를 모두 제거한다. 마찬가지로 3은 포함시키지 않으며 제거하는 자연수가 겹치면 continue한다.

4> 4는 배열에서 삭제되었으니 건너뛰고, 5의 배수를 삭제한다.

5> 다음 과정을 25(마지막 수)까지 반복하면 소수만이 배열에 남게된다.

int sieve[26];
void eratos(int number){
	for(int i = 2; i <= number; ++i){
		sieve[i] = i;
	}
	for(int i = 2; i <= number; ++i){
		if(sieve[i] == 0) continue; // 이미 지워진 숫자는 continue
		// i의 배수에 해당하는 숫자들을 삭제
		for(int j = i + i; j <= number; j += i){
			sieve[j] = 0;
		}
	}
	for(int i = 2; i <= number; ++i){
		if(sieve[i] != 0) cout << sieve[i] << " ";
	}
}
int main(){
	// eratos
	eratos(25);
	return 0;
}

[결과] 2 3 5 7 11 13 17 19 23

에라토스테네스의 채는 시간복잡도가 O(NloglogN)으로 거의 선형시간에 작동할 정도로 효율적인 알고리즘 이지만, 메모리를 많이 잡아먹는다는 단점이 있다.

PS에서 대량의 소수를 구해야 하는 상황에서 메모리 제한이 충분하다면 에라토스테네스의 채를 이용하도록 하자.

* 다음 포스팅의 모든 내용은  BaaaaaaaaarkingDog 님의 [실전 알고리즘] 0x0B강 - 재귀 강의를 공부한 뒤 개인적인 공부 용도로 간략하게 요약하여 정리한 글 입니다. 자세한 내용은 아래 바킹독님의 블로그에서 확인해 주세요.

BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹 (encrypted.gg)

#1 백트래킹

#1.1 BOJ15649 N과M(1)

#1.2 BOJ9663 N-Queen [미완성]

#1 백트래킹

백트래킹 알고리즘이란 해를 찾는 도중 해가 될 가능성이 없다면 이전 상태로 되돌아가 다시 해를 찾아가는 기법이다.

깊이 우선 탐색 알고리즘인 DFS와 많이 유사한데 DFS는 유망하지 않은 경로를 사전에 차단하는 등의 행동을 수행하지 못하지만 백트래킹 알고리즘은 유망하지 않은 경로를 조기차단하여 효율성을 높일 수 있다.

이처럼 유망하지 않은 경로를 조기차단 하는 것을 "가지치기(pruning)한다" 라고 표현한다.

#1.1 BOJ15649 N과 M(1)

1 부터 n(4)까지 자연수 중에서 중복 없이 M(2)개를 고른 수열을 백트래킹을 이용해 구해 보도록 하겠다.

처음에는 빈 배열에서 시작한다.

다음으로 첫 번째 원소를 1로 설정한다.

숫자 1이 사용 되었으니 중복 없이 수열을 만들기 위해서는 2번째 숫자로 2, 3, 4가 들어가야 한다. 

배열의 끝에 도달하였으니 이전 상태로 역추적(Backtracking)하여 다시 탐색을 시작한다.

같은 방식으로 첫 번째 원소가 1인 배열의 모든 조합을 탐색한다.

첫 번째 원소가 1인 배열의 모든 조합을 탐색했다면 다시 초기 상태로 역추적한다.

나머지 케이스들도 같은 방식으로 탐색을 수행하면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10]; 
bool isVisited[10]; // 숫자 i를 사용했는지 확인하는 배열

void recur(int k){
	if(k == m){
		for(int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}
	for(int i = 1; i <= n; i++){
		// 숫자 i를 사용하지 않았다면
		if(!isVisited[i]){
			arr[k] = i;	// 배열의 k번째 원소를 i로 설정한다.
			isVisited[i] = true; // 숫자 i를 사용했다고 표시한다.
			recur(k+1); // 배열의 k + 1 번째 원소를 탐색하러 들어간다.
			isVisited[i] = false; // 탐색을 모두 끝마쳤다면 숫자 i 사용 여부를 해제한다.
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	recur(0);
	return 0;
}

#1.2 BOJ 9663 N-Queen

BOJ 9663 N-Queen 문제는 n * n 으로 이루어진 체스판에서 퀸 n개를 서로 공격할 수 없게 설정하는 무제이다.

퀸의 공격방향은 다음과 같이 8방향으로 퍼져 나간다.

따라서 퀸의 공격방향에 또 다른 퀸이 존재한다면 불가능한 배치가 되고, 공격 방향을 모두 피해 남은 칸에 퀸이 존재한다면 가능한 배치가 된다.

* 다음 포스팅의 모든 내용은  BaaaaaaaaarkingDog 님의 [실전 알고리즘] 0x0B강 - 재귀 강의를 공부한 뒤 개인적인 공부 용도로 간략하게 요약하여 정리한 글 입니다. 자세한 내용은 아래 바킹독님의 블로그에서 확인해 주세요.

BaaaaaaaarkingDog | [실전 알고리즘] 0x0B강 - 재귀 (encrypted.gg)

#1 귀납적 사고

#2 재귀 함수의 특성

_base condition

_함수를 명확하게 정의하자

_재귀함수와 반복문

_재귀함수와 피보나치 수열

..요약

#1 귀납적 사고

재귀 알고리즘이란, 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다.

재귀로 문제를 풀이하기 위해 가장 중요한 점은 우리가 평소에 생각해 오던 절차 지향적 사고를 버리고 귀납적 사고를 통해 문제에 접근해야 한다는 것이다.

절차 지향적 사고와 귀납적 사고의 차이를 도미노를 이용하여 이해해 보도록 하자. 예를들어 도미노 n개가 나열되어 있다고 가정해 보자.

1번 도미노를 쓰러뜨리면 2번 도미노가 쓰러지고 2번 도미노가 쓰러지면 3번 도미노가 쓰러진다. 이런식 으로 연이어 모든 n개의 도미노가 쓰러지게 될 것이다. 이것이 바로 절차 지향적 사고이다. 

그렇다면 이번에는 귀납적 사고로 도미노의 쓰러지는 과정을 설명해 보도록 하자. 1번 도미노가 쓰러진다. 1번 도미노가 쓰러지는것은 매우 자명하고, k번 도미노가 쓰러지면 k+1번째 도미노 또한 쓰러진다. 따라서 결국은 모든 도미노가 쓰러지게 될 것이다.

평소에 우리는 당연하듯이 절차 지향적 사고를 이용해 코딩을 해 왔다. 함수A를 호출하면 연이어 함수B가 호출될 것이고,, 함수B가 호출 되면 변수C를 출력한다.. 와 같이 말이다. 하지만 재귀 알고리즘을 이용해 알고리즘 문제 풀이를 하는 동안은 앞에서 강조했듯이, 절차 지향적 사고를 버려야만 한다.

#2 재귀 함수의 특성

_base condition

재귀 함수는 특정 입력에 대해서 자기 자신을 호출하지 않고 종료해야 한다. 또한 모든 입력은 base condition으로 수렴 해야만 한다. 이를 지키지 않으면 재귀함수는 무한루프에 빠져 에러를 발생시키고 말 것이다. 

void recursive(int n){
	cout << n << endl;
	recursive(n-1);
}

위의 함수는 n부터 1까지의 값을 출력하는 재귀 함수이다. 하지만 recursive 함수를 실행시키면 무한루프에 빠져 프로그램이 뻗고 말 것이다. 그 이유는 base condition을 따로 지정해 주지 않았기 때문이다.

void recursiveFixed(int n){
	if(n==0) return; // base condition
	cout << n << endl;
	recursive(n-1);
}

recursiveFixed 함수에 base condition을 추가 해주었다. 특정 입력(0)에 대해서 자기 자신을 호출하지 않고 종료하며, 모든 입력은 base condition으로 수렴하기에 무한루프에 빠지지 않고 정상적으로 n부터 1까지의 수를 출력한다.

_함수를 명확하게 정의하자

재귀함수를 만들때는 함수를 명확하게 정의해야 한다. 함수를 명확하게 정의한다는 것은 1.함수의 인자로 어떤 것을 받을지, 2. 어디까지 계산한 후 자기 자신에게 넘겨줄 지를 명확히 하는 것을 의미한다.

_재귀함수와 반복문

모든 재귀함수는 재귀구조 없이 반복문 만으로 동일 동작을 수행하는 함수를 구현할 수 있다. 재귀를 적절하게 잘 사용하면 코드가 간결해 진다는 장점이 있지만, 메모리와 시간적 측면에서는 어느정도 손해를 보게 된다.

따라서 반복문으로도 간단하게 해결 가능한 문제라면 반복문을 사용해 구현하고, 반복문 만으로는 너무 코드가 복잡해 질 것 같다면 재귀 구조를 사용하는 것이 좋다.

_재귀함수와 피보나치 수열

피보나치 수열은 초항(F1, F2)가 1이고 나머지는 그 직전 항 2개의 합으로 연결되는 수열이다. ex) 1, 1, 2, 3, 5, 8 ...

다음 fibo 함수는 재귀 구조를 이용해 피보나치 수열을 구현한 코드이다. 언뜻보면 base condition도 잘 지켜졌고 문제가 없는 함수라고 생각할 수 도 있다. 하지만 n의 값이 커질수록 연산의 처리량이 지수함수 형태로 매우 가파르게 늘어난다.

int fibo(int n){
	if(n == 1) return 1; // base condition
	return fibo(n-1) + fibo(n-2);
}

fibo(5)를 호출하는 과정을 예시로 들어 문제의 원인을 파악해 보도록 하자.

fibo(5)를 호출하면 fibo(4)와 fibo(3)이 호출된다. fibo(4)를 호출하면 fibo(3)과 fibo(2)가 호출된다. fibo(3)을 호출하면 fibo(2)와 fibo(1)이 호출된다 fibo(2)를 호출하면 fibo(1)과 fibo(1)이 호출된다.

위 과정을 자세히 살펴보면 이미 한 번 호출된 함수가 또 다시 호출되는 케이스가 빈번하게 발생하고 있다. 자기 자신의 호출을 계속하다 보니 시간 복잡도가 예상과 달리 급격하게 늘어나 버린다.

따라서 이렇게 한 함수가 자기 자신을 여러번 호출하는 케이스는 재귀 호출 보다는 작은 문제의 답으로 큰 문제의 답을 풀어내는 다이나믹 프로그래밍(Dynamic Programming) 알고리즘을 사용해 문제를 풀이하는 것이 좋다. DP를 이용하면 재귀의 문제점인 중복 호출을 어느정도 해결할 수 있다.

..요약

1. 재귀 알고리즘을 이용해 문제에 접근할 때는 절차 지향적인 사고를 버리고 귀납적인 사고로 접근해야 한다.

2. _base condition : 특정한 입력에 대해서 자기 자신을 호출하지 않고 종료 해야만 하며, 모든 입력은 base condition으로 수렴해야 한다.

3. 재귀함수를 정의할때는 함수의 인자로 어떤 값을 받을 지, 어디까지 계산한 후 자신에게 넘겨줄 지 명확히 설계해야 한다.

4. 모든 재귀함수는 재귀구조 없이 반복문으로 똑같이 구현할 수 있다. 

5. 함수가 자기 자신을 여러번 중복해서 호출하는 케이스는 재귀보다 DP를 이용하는 것이 바람직하다.