조합 정의 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 말한다. 성질중복조합에서 다음이 성립한다.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) {..

풀이모든 경우의 수를 돌리면 시간초과가 나게된다.. 이 문제도 DP를 통해서 구현할 수 있다. (현재값 + DP이전값) 과 (현재값) 중 큰값을 DP배열에 저장해주면서 Max값이랑 비교한다. 1dp[i] = Max(num[i], dp[i - 1] + num[i]);cs--> 이렇게 하면 부분집합의 합을 DP에 계속 쌓을 수 있다. 문제를 해석할 때 놓치는 부분이 있을 수 있다. 입력범위는 -1000 ~ 1000 까지라 int형 내에서 입력을 받을 수 있다. 하지만 입력의 갯수가 n(1≤n≤100,000) 이므로 1000이 연속해서 100000개가 들어와서 DP배열에 쌓게 되면 int형을 벗어날 수 있다. 소스코드12345678910111213141516171819202122232425#include us..

풀이계단 오르기문제랑 비슷한 문제이다. 연속으로 세잔을 마시지 못하는 조건이 들어간것도 똑같다. 모든 경우의 수를 구해서 답을 구할 수 있지만 시간초과가 나므로 DP로 해결할 수 있다. 마실 수 있는 경우의 수를 3가지로 분류할 수 있다.1. 현재 잔을 마셧을 경우2. 이전잔과 현재잔 전전전잔을 마셧을 경우3. 전전잔과 현재잔을 마셧을 경우 이 경우의 수의 최대값을 계속 DP배열에 저장해나가면 해결할 수 있다.1231. dp[i-1]2. wine[i] + wine[i - 1] + dp[i - 3]3. wine[i] + dp[i - 2];cs 소스 코드123456789101112131415161718192021222324252627#include using namespace std; int n, wine[..

정의유클리드 호제법(- 互除法, 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부..