1234567891011121314151617181920212223242526272829303132#include using namespace std; #define swap(a,b,tmp) tmp=a; a=b; b=tmp; int n,num[1001],tmp; void perm(int* num, int start, int end) { if (start == end) { for (int i = 0; i

조합 정의 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다. 성질중복조합에서 다음이 성립한다.nCr = n-1Cr-1 + n-1Cr이성질을 이용하여 알고리즘을 구현할 수 있다. [출처 : wiki] 소스 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include using namespace std; time_t startTime = 0, endTime = 0; // 재귀는 메모이제이션 활용해야 빠름int memo[1001][1001]; int combi(int a, int b) { if (a == b || b==0) { return 1; } ..

Counting Sort카운팅 정렬은 반복되는 숫자가 있으면서 숫자의 범위가 너무 크지않을 때 유용하다. 순서1. 숫자의 범위만큼 배열을 선언해주고 0으로 초기화한다.2. Data의 숫자를 하나씩 꺼내면서 카운트를 세준다.3. 처음에 선언한 배열에서 카운트가 0이 아닌 숫자들을 카운트 만큼 출력해주면 된다. 소스 코드123456789101112131415161718192021222324252627282930/* 카운팅 정렬 중복된 수를 정렬할때 유용 숫자의 범위가 한정적일때 유용 */ #include using namespace std; int main() { int n, num[10001]; // num안의 숫자는 최대 허용 숫자 범위 for (int i = 0; i cin 속도 극대화 cin >> n..

병합 정렬하나의 집합을 원소가 한개가 될때까지 쪼개고, 정렬하면서 병합하는 알고리즘 세가지 단계로 나뉜다.1. 분할2. 병합3. 정렬 시간 복잡도 O(N * logN)공간 복잡도 O(N) 소스 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include using namespace std; int n;int space[1000001]; // 입력 받을 공간int space_copy[1000001]; // 병합과정에서 임시로 저장할 공간 void merge(int data[], int start, int mid, int end) {..

정의유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며,기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부..