초보개발자

[알고리즘] 동적계획법 동적 계획법은 큰 의미에서 분할 정복과 같은 접근방식을 의미한다.메모이제이션(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..