머슬가이

개요 :이항 계수(Binomial Coefficient)란, 주어진 자연수 $n$과 $k$에 대해 “$n$개 중에서 $k$개를 고르는 방법의 수”를 나타내는 값이다. 이는 보통 조합(Combination)으로 불리며, 수학적으로 다음과 같이 정의된다. $C(n, k) = \frac{n!}{k!(n-k)!}$$C(n, k)$는 $n$개 중에서 $k$개를 선택하는 경우의 수.$n!$은 $n$의 팩토리얼로, $n \times (n-1) \times \cdots \times 1$을 의미.원리 :이항 계수를 풀기 위해서는 점화식을 이용하여 재귀 호출을 해야한다. 점화식을 이용한 재귀 방식:$$ C(n, k) = \begin{cases} 1 & \text{if } k = 0 \text{ or } k = n \\..

개요 :유클리드 호제법이란 두 수의 최대공약수(GCD)를 구하는 하나의 알고리즘이다.고대 그리스 수학자 유클리드가 제시한 알고리즘으로, 두 수의 나누어떨어지는 관계를 반복적으로 활용하여 가장 큰 공약수를 빠르게 구할 수 있다.원리 :두 수 a와 b에 대해, a가 b로 나누어떨어지지 않으면, 그 나머지를 구하고, 그 나머지와 b로 최대공약수를 구하는 방식입니다. 이 과정을 반복해서 나머지가 0이 될 때까지 진행하면, 그때의 b가 a와 b의 최대 공약수입니다.사용 조건 :두 수 a와 b가 주어져야 한다.a와 b가 정수여야 한다.두 수 중 적어도 하나는 0이 아니어야 한다. (48과 0의 최대 공약수는 48, 18과 0의 최대 공약수는 18)#include using namespace std;int gcd(i..

개요 :계수 정렬(Counting Sort)은 비교 기반 정렬 알고리즘이 아닌 카운팅을 기반으로 하는 정렬 알고리즘입니다. 주로 정수 값이나 범위가 제한된 값들을 정렬할 때 매우 효율적입니다. 값의 범위가 크지 않거나 제한적인 경우에 매우 빠르게 동작하며, 시간 복잡도가 O(n + k)로, n은 입력 배열의 크기, k는 배열 값의 범위입니다.원리 :계수 정렬의 핵심 아이디어는 각 값의 등장 횟수를 세고, 그 정보를 바탕으로 정렬된 배열을 만들어내는 것입니다. 각 값이 배열에서 몇 번 나타나는지를 기록하는 카운팅 배열을 이용하여 최종적으로 정렬을 수행합니다.사용 조건 :값의 범위가 제한적인 경우배열의 크기 N에 비해 값의 범위 K가 상대적으로 작은 경우수의 범위가 작고, 동일한 수가 많이 반복될 때출력 순..