Nagie's DevStory

C++ 17부터 제공하는 std::gcd()와 std::lcm을 사용해도 되지만 모든 작업환경이 C++ 17을 만족하지는 않기에 유클리드 호제법을 사용해 직접 구현해 봤다. 재귀함수 int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); } 반복문 int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } 최소 공배수(LCM) 구하기 int lcm(int a, int b) { return a * b / gcd(a, b); }

피보나치 수열은 이전 두 항을 더해서 다음 항을 만들어 내는 규칙에 따라 생성되는 수열이다. 재귀함수와 반복문을 사용해 각각 구현했다. 재귀함수 unsigned long long fibonacci(int n) { return (n

팩토리얼은 양의 정수 n에 대해 n!로 표시되며, 1부터 n까지의 모든 양의 정수를 곱한 값을 나타낸다. 재귀함수와 반복문을 사용해 각각 구현했다. 재귀함수 unsigned long long factorial(int n) { return (n == 0) ? 1 : n * factorial(n - 1); } 반복문 unsigned long long factorial(int n) { unsigned long long sum = 1; for (int i = 1; i

O(n!)은 팩토리얼(Factorial) 시간 복잡도를 나타낸다. 이는 입력 크기 n에 대해 n의 팩토리얼에 비례하는 실행 시간을 가지는 알고리즘을 의미하며, 팩토리얼 시간 복잡도는 굉장히 높은 성능 비용을 가지기 때문에, 큰 입력에 대해서는 사용이 거의 불가능에 가깝다. O(n!)의 알고리즘은 일반적으로 재귀적인 방법을 사용하여 문제를 작은 부분으로 나누고, 모든 가능성을 따져야 하는 경우에 나타나며 대표적인 예시로는 외판원 문제(Travelling Salesman Problem)가 있다. 아래는 재귀함수를 사용해 팩토리얼을 계산하는 코드이며, O(n!) 시간 복잡도를 가진다. int factorial(int n) { if (n == 0 || n == 1) { return 1; } else { retu..

O(n log n)은 로그 선형(Log-Linear) 시간 복잡도를 가지는 알고리즘을 나타낸다. 이는 입력 크기 n에 대해 n과 log n의 곱에 비례하는 실행 시간을 갖는 알고리즘을 의미하며, 주로 효율적인 정렬 알고리즘에서 나타난다. 아래는 가장 널리 사용되는 O(n log n) 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이다. // 두 변수의 값을 교환하는 함수 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // 배열을 특정한 피벗을 기준으로 두 부분으로 나누고, 피벗의 정확한 위치를 반환 int partition(int arr[], int low, int high) { int pivot = arr[..