초보개발자

분류: 그래프, 트리 난이도: 하입력: 테스트 케이스 C( C; for (int i = 1; i > N >> M; point = vector(N, make_pair(0, 0)); disjoinSet lanSet(N); for (int j = 0; j > point[j].first;//x좌표 for (int j = 0; j > point[j].second;//y좌표 for (int j = 0; j > u >> v; lanSet.merge(u, v); } cout

분류: 그래프난이도: 하입력: 테스트 케이스 C( C; for (int i = 1; i > N; preorder = vector(N, 0);//초기화 inorder = vector(N, 0); for (int j = 0; j > preorder[j]; for (int j = 0; j > inorder[j]; int index = 0; printPostorder(N, index, 0, N - 1); cout right){ --root_index; return; } if (root_index >= n) return; int index = left; for (; index

분류: 분할정복 난이도: 하입력: 테스트 케이스 C(child[i] = ptr->child[i + 2]; ptr->child[i + 2] = temp; if (ptr->child[i]->ch == 'x') ChangeTree(ptr->child[i]); if (ptr->child[i + 2]->ch == 'x') ChangeTree(ptr->child[i + 2]); } } void ShowStr(node* ptr){ cout ch; for (int i = 0; i child[i]->ch == 'x') ShowStr(ptr->child[i]); else cout child[i]->ch; } } }; int main(){ int count; cin >> count; fo..

[알고리즘] 정수론유클리드 알고리즘(Euclidean algorithm)정의: 두 수의 최대공약수를 구하는 방법구현 방법: 파라미터로 a와 b를 받고, b=0이면 a를 반환한다. 아닐 경우, b와 a를 b로 나눈 나머지(a % b)를 인수로 재귀함수를 호출한다. a = b * R1 + 2, b = R1 * R2 + R3, ... , R(n-2) = R(n-1) * Rn + 0 일 때, Rn이 최대공약수이다.구현:int gcd(int a, int b){ if(b == 0) return a; else return gcd(b, a % b); }모듈라 연산정의: 모듈로(modulus) M에 도달하면 다시 0으로 돌가는 정수들을 가지고 하는 연산. 덧셈, 뺄셈, 곱셈(a + b)%M = ((a%M) + (b%M)..

분류: 정수론 난이도: 중입력: 테스트 케이스 C, 재료의 수 N(1> recipe[i]; for (int i = 0; i > put[i]; potion(number); for (int i = 0; i < number; i++) cout

분류: 동적계획법, 경우의 수 난이도: 중입력: 테스트 케이스 C, 정사각형의 수 N출력: 정사각형 N개로 만들 수 있는 세로 단조 폴리오미노의 경우의 수를 구하여라. (단, 10,000,000이 넘을 경우 나머지를 출력한다.)소스 #include #define MOD 10000000 using namespace std; int cache[101][101]; int poly(int, int); int calcPoly(int); int main(){ int C; cin >> C; //cache 초기화 for (int i = 0; i N; cout

[알고리즘] 동적계획법 동적 계획법은 큰 의미에서 분할 정복과 같은 접근방식을 의미한다.메모이제이션(memoization): 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법대표적인 사용 방법:항상 기저 사례를 제일 먼저 처리. 접근을 벗어나는 등의 오류가 발생.cache(이미 계산한 값을 저장해 두는 메모리의 장소)를 -1로 초기화. -1이 아닌 경우에는 계산이 된 경우가 아님을 의미.ret는 cache[idx]의 참조형(reference)으로, 해당 값이 수정되면 ret 값도 수정되어 계산되었음을 의미.초기화하는 방법은 memset() 혹은 vector를 사용하여 초기화할 수 있음.가장 유명한 예: 이항 계수(binomial co-efficient)참..

[PACKING] 여행짐싸기 분류: 동적계획법난이도: 중입력: 테스트 케이스 C, 물건의 수 N, 캐리어의 용량 W, N개의 물건의 이름, 부피, 절박도 출력: 가져갈 수 있는 물건들의 최대 절박도의 합과 가져갈 물건들의 갯수. 단, 조합이 여럿일 경우 아무거나 출력해도 됨.소스 #include #include #include #include using namespace std; int n, capacity; int volume[100], need[100]; int cache[1001][100]; string name[100]; int pack(int capacity, int item){ if (item == n) return 0; int& ret = cache[capacity][item]; if (re..