팩토리얼 (factorial, 계승)
∙ 팩토리얼
- 20보다 같거나 작은 자연수 N이 입력으로 주어질 경우, 1 * 2 * 3* ... *. (N-1)*N 을 계산하는 팩토리얼 함수를 작성하시오
#include <iostream>
using namespace std;
// factorial(20)이 값이 크기 때문에 int형으로 불가능
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
}
피보나치 수
∙ 피보나치 수 (Fibonacci numbers)
- 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
ex) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...
- 편의상 0번째 항을 0으로 설정하기도 함
#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;
// 40번째 항 출력
cout << fibo(40) << endl;
// 50번째 항 출력 -> 출력이 늦게 나옴
// 중복되는 부분 문제로 인해 계산 효율이 떨어짐
// 캐시를 사용하여 문제를 해결할 수 있음
cout << fibo(50) << endl;
}
문자열 뒤집기
∙ 문자열 뒤집기
- 문자열의 각 문자 순서를 역순으로 변경
#include <iostream>
#include <string>
using namespace std;
string reverse(const string& str)
{
if (str.length() == 0)
return "";
else
return reverse(str.substr(1)) + str[0];
}
int main()
{
cout << reverse("Hello") << endl;
}
최대 공약수와 최소 공배수
∙ 최대 공약수
- gcd(a,b) : 두 개의 자연수 a와 b가 있을 때, a와 b 모두의 약수 중에서 가장 큰 정수
- 유클리드 알고리즘을 이용하여 재귀적으로 구할 수 있음
ex) gcd(24, 18) => gcd(18, 6) => gcd(6, 0) => 6
ex) gcd(18, 24) => gcd(24, 18) => gcd(18, 6) => gcd(6, 0) => 6
∙ 최소 공배수
- lcm(a, b) : 두 정수 a와 b가 있을 때, a와 b로 모두 나누어 떨어지는 가장 작은 정수
- 두 정수의 곱은 두 정수의 최대 공약수와 최소 공배수의 곱과 같다는 성질을 이용하여 구할 수 있음
#include <iostream>
// C++ 17버전부터 사용가능
#include <numeric>
// 최대 공약수
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// 최소 공배수
int lcm(int a, int b)
{
return a * b / gcd(a,b);
}
int main()
{
// 정의된 함수 사용
int gcd1 = gcd(10, 15);
int lcm1 = lcm(10, 15);
// STL numeric 사용
int gcd2 = std::gcd(10, 15);
int lcm2 = std::lcm(10, 15);
std::cout << gcd1 << ", " << gcd2 << std::endl;
std::cout << lcm1 << ", " << lcm2 << std::endl;
}
순열
∙ 순열 (permutation)
- n개의 원소로 구성된 집합이 있을 경우, 모든 원소를 서로 다른 순서로 나열하는 순열 방법을 모두 출력하시오
- 순열 재귀 함수 구현 방법
1. 첫 번째 원소를 모든 원소와 각각 맞바꾸기(swap)
2. 첫 번째 원소를 제외한 나머지 원소들의 집합으로 순열 구하기
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
void print_vector(const vector<T>& vec)
{
for (const auto& e : vec)
cout << e << " ";
cout << endl;
}
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]); // 순서 원복
}
}
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()));
}
하노이의 탑
∙ 하노이의 탑
- 퍼즐의 일종
- 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 처음에는 하나의 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있음
- 다음 조건을 만족시키면서 원판들이 다른 기둥으로 옮겨서 다시 쌓아야 함
1. 한 번에 하나의 원판만 옮길 수 있다.
2. 기둥의 맨 위에 있는 원판을 다른 기둥의 맨 위로 옮길 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안된다.
- 하노이의 탑 이동 순서 구하기
> 하노이 탑의 세 기둥을 차례대로 1번, 2번, 3번이라고 할 경우 처음 1번 기둥에 n개의 원판이 있음
> n은 15이하의 자연수이며, 입력으로 주어짐
> 1번 기둥의 모든 원판을 3번 기둥으로 최소 횟수로 옮기는 방법을 출력하시오
#include <vector>
#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);
hanoi(3, 1, 3, 2);
}
