1장 재귀 알고리즘
1. 재귀 알고리즘
가. 재귀 (recursion, 순환) 알고리즘이란?
- 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
- 많은 종류의 문제가 재귀적으로(recursively) 해결 가능
- 예) 피보나치 수열, 이진 탐색, 병합 정렬, 퀵 정렬 등
나. 재귀 함수 (recursion function)
- 자기 자신을 다시 호출하는 함수. 순환 함수.
- 자기 자신을 완전히 그대로 호출하지 않고, 함수의 인자를 특정한 방식으로 변경하여 호출
- 무한 루프에 빠질 위험이 있기 때문에 자기 자신을 완전히 그대로 호출하지 않는다.
다. 재귀 함수의 구성
- 기저 조건(base case): 재귀를 종료하기 위한 조건이 있어야 함. 종료 조건.
- 재귀 호출 (recursive case): 자기 자신을 다시 호출하는 부분. 재귀를 반복하다보면 반드시 기저 조건으로
수렴해야 함.
2. 재귀 알고리즘 - 재귀 함수 작성하기
가. 자연수의 합 구하기
- 양의 정수 N이 입력으로 주어질 경우, 1부터 N까지의 합을 반환하는 함수 sum(N)을 작성하시오.
int sum(int n) {
if (n == 1) {
return 1;
}
else {
return n + sum (n - 1);
}
}
3. 재귀 알고리즘 - 재귀 함수의 특징
- 모든 재귀 함수는 반복문을 사용하는 함수로 변환 가능
- 재귀 함수: O(n) + 함수 호출 오버헤드
int sum(int n) {
if (n == 1) {
return 1;
}
else {
return n + sum (n - 1);
}
}
- 반복문 사용 함수: O(n)
int sum1(int n) {
int s = 0;
for (int i = 0; i <= n; i++) {
s += i;
}
return s;
}
- 재귀 함수의 장단점
- 장점: 코드를 간결하게 작성 가능
- 단점: 디버깅이 어려움. 스택 오버플로우(stack overflow) 주의, 반복문 사용 코드보다 낮은 효율
- 재귀 함수와 반복문 사용 함수의 연산 시간 비교
- 1부터 n까지의 자연수의 합을 재귀 방법과 반복문 사용 방법으로 각각 계산하고, 그 실행 시간을 비교
- n값은 1부터 20000까지 변화시키면서 입력으로 전달
2장 재귀 알고리즘 주요 예제 (1)
1. 재귀 알고리즘 주요 예제 (1)
- 팩토리얼
- 피보나치 수
- 문자열 뒤집기
- 최대 공약수와 최소 공배수
2. 팩토리얼
가. 팩토리얼(factorial, 계승)
- 20보다 같거나 작은 자연수 N이 입력으로 주어질 경우, 1*2*3*...*(N-1)*N 을 계산하는 팩토리얼 (factorial)함수를 작성하시오.
long long factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n-1);
}
int main()
{
cout << factorial(5) << endl; //120
cout << factorial(10) << endl; //3628800
cout << factorial(20) << endl; // 2432902008176640000
}
3. 피보나치 수
가. 피보나치 수 (Fibonacci numbers)
- 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
- (e.g.) 1, 1, 2, 3, 5, 8, 13, 21, 24, 55 ...
- 편의상 0번째 항을 0으로 설정하기도 함
-
더보기f(0) = 0
f(1) = 1
f(n) = f(n-2) + f(n-1) (n>1)
#include <iostream>
using namespace std;
long long fibo(int n)
{
if (n <= 1)
return n;
else
return fibo(n-1) + fibo(n-2);
}
int main ()
{
for (int i = 1; i <= 10; i++)
cout << fibo(i) << ", ";
cout << endl;
}
나. 재귀에 의한 피보나치 수 계산의 문제점
- 중복되는 부분 문제 (overlapping subproblem)로 인해 계산 효율이 떨어짐
- 캐시(cache)를 사용하여 문제를 해결할 수 있음
4. 문자열 뒤집기
가. 문자열 뒤집기
- 문자열의 각 문자 순서를 역순으로 변경
1. 두 번째 문자부터 시작하는 부분 문자열을 뒤집어 반환
2. 1에서 반환된 문자열 뒤에 첫 번째 문자를 추가
string reverse(const string& str)
{
if (str.length() == 0)
return "";
else
return reverse(str.substr(1)) + str[0];
}
int main()
{
cout << reverse("Hello") << endl;
}
5. 최대 공약수와 최소 공배수
가. 최대 공약수 (greatest common divisor)
- gcd(a, b): 두 개의 자연수 a와 b가 있을 때, a와 b 모두의 약수 중에서 가장 큰 정수
- 유클리드 알고리즘 (Euclidean algorithm, 유클리드 호제법)을 이용하여 재귀적으로 구할 수 있음
-
더보기gcd(a, b) = a (if b = 0), gcd (b, a%b) (otherwise)
- 유클리드 알고리즘 예:
- gcd(24, 18) = gcd(18, 6) = gcd(6, 0) = 6
- gcd(18, 24) = gcd(24, 18) = gcd(18, 6) = gcd(6, 0) = 6
나. 최소 공배수 (lowest common multiple)
- lcm(a, b): 두 정수 a와 b가 있을 떄, a와 b로 모두 나누어 떨어지는 가장 작은 정수
- 두 정수의 곱은 두 정수의 최대 공약수와 최소 공배수의 곱과 같다는 성질을 이용하여 구할 수 있음
다. C++ 최대 공약수 & 최소 공배수 계산 함수
template <class M, class N>
constexpr std::common_type_t<M,N> gcd(M m, N n);
template <class M, class N>
constexpr std::common_type_t<M,N> lcm(M m, N n);
- C++ 17부터 지원
- <numeric>에 정의되어 있음
- 예제 코드)
#include <numeric>
int main()
{
int a = std::gcd(10, 15); //5
int b = std::lcm(10, 15); // 30
}
3장 재귀 알고리즘 주요 예제 (2)
1. 재귀 알고리즘 주요 예제 (2)
- 순열
- 하노이의 탑
2. 순열
가. 순열 (permutation)
- n개의 원소로 구성된 집합이 있을 경우, 모든 원소를 서로 다른 순서로 나열하는 순열 방법을 모두 출력하시오.
나. 순열의 재귀 관계
- {a, b, c, d}의 모든 순열
- a로 시작하고 { b, c, d}의 모든 순열
- b로 시작하고 {a, c, d}의 모든 순열
- c로 시작하고 {a, b, d}의 모든 순열
- d로 시작하고 {a, b,c}의 모든 순열
- b로 시작하고 {c, a}의 모든 순열
- c로 시작하고 {b, a}의 모든 순열
- a로 시작하고 {c, b}의 모든 순열
다. 순열 재귀 함수 구현 방법
- 첫 번쨰 원소를 모든 원소와 각각 맞바꾸기(swap)
- 첫 번쨰 원소를 제외한 나머지 원소들의 집합으로 순열 구하기
라. 순열 재귀 함수 구현 코드
void permutation(vector<int>& vec, int k)
{
if (k == vec.size() - 1) {
print_vector(vec);
return;
}
for (int i = k; i < vec.size(); i++){
swap(vec[k], vec[i]);
permutation(vec, k + 1);
swap(vec[k], vec[i]); // 순서 원복
}
}
라. C++ 순열 구하기 함수
template <class BidirIT>
bool next_permutation (BidirIt first, BidirIt last);
- 주어진 시퀀스를 사전순으로 다음에 나오는 순열로 변환
- 정렬된 시퀀스로 호출하기 시작해야 함
- <algorithm>에 정의되어 있음
- 예제 코드)
std::vector<int> vec {1, 4, 3, 2};
std::sort(vec.begin(), vec.end());
do {
for (int a : vec)
cout << a;
cout << endl;
} while (std::next_permutation(vec.begin, vec.end()));
마. 순열 테스트 코드
int main()
{
// 재귀 알고리즘 사용 예제
vector<int> vec {1, 2, 3, 4};
permutation(vec, 0);
// std::next_permutation() 사용 예제
sort(vec.begin(), vec.end());
do {
print_vector(vec);
} while (next_permutation(vec.begin(), vec.end()));
}
3. 하노이의 탑
가. 하노이의 탑(tower of Hanoi)
- 퍼즐의 일종
- 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 처음에는 하나의 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있음
- 다음 조건을 만족시키면서 원판들을 다른 기둥으로 옮겨서 다시 쌓아야 함
-
더보기1. 한번에 하나의 원판만 옮길 수 있다.
2. 기둥의 맨 위에 있는 원판을 다른 기둥의 맨 위로 옮길 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.
나. 하노이의 탑 이동 순서 구하기
- 하노이 탑의 세 기둥을 차례대로 1번, 2번, 3번이라고 할 경우, 처음에 1번 기둥에 n개의 원판이 있음.
- n은 15 이하의 자연수이며, 입력으로 주어짐
- 1번 기둥의 모든 원판을 3번 기둥으로 최소 횟수로 옮기는 방법을 출력하시오.
다. 입출력 예
| n | answer |
| 2 | 1->2, 1->3, 2->3 |
| 3 | 1->3,1->2, 3->2, 1->3, 2->1, 2->3, 1->3 |
라. 원판이 2개인 경우
마. 원판이 3개인 경우
바. 재귀 관계 분석
void hanoi(int n, int from, int to, int by)
{
if (n == 1) {
cout << from << " -> " << to << endl;
} else {
hanoi(n - 1, from, by, to);
cout << from << " -> " << to << endl;
hanoi(n-1 , by, to, from);
}
}
사. 하노이의 탑 테스트 코드
#include <iostream>
using namespace std;
void hanoi(int n, int from, int to, int by)
{
if (n == 1) {
cout << from << " -> " << to << endl;
} else {
hanoi(n - 1, from, by, to);
cout << from << " -> " << to << endl;
hanoi(n-1 , by, to, from);
}
}
int main()
{
hanoi(2, 1, 3, 2);
}
'3학년 > 자료구조와 알고리즘 스터디' 카테고리의 다른 글
| [자료구조와 알고리즘] 5장 큐 (0) | 2023.05.15 |
|---|---|
| [자료구조와 알고리즘] 4장 스택 (1) | 2023.05.09 |
| [자료구조와 알고리즘] 3장 연결 리스트 (0) | 2023.04.11 |
| [자료구조와 알고리즘] 2장 배열: C에서 C++로 (0) | 2023.04.02 |
| [자료구조와 알고리즘] 1주차 개요, 시간 복잡도 (1) | 2023.03.26 |
