DP 썸네일형 리스트형 여행 짐 싸기 문제링크: 여행 짐 싸기 유명한 문제인데 풀 때마다 새롭다. 이런 류의 문제들은 패턴이 있으니 기억하자. 배낭에 넣었을 때와 안넣을때의 값 중에 max를 취한다. 일단 최대 절박도를 구하는 함수를 구하고, 그 함수를 이용하여 선택한 item들을 재구성한다. - recursive무게가 capacity만큼 남았을 때, 해당 item부터 마지막 item들까지 넣었을 때 얻을 수 있는 최대절박도를 구하는 함수를 만든다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #define.. 더보기 LIS 문제링크: Longest Increasing Sequence 증가하는 부분 수열의 갯수를 구하는 문제이다. 동적계획법으로 풀 수 있으며, 아래보다 더 최적화된 O(NlogN) 방법이 가능하지만, 그 방법은 해당 수열을 저장하지 않는 방법이므로 일단 동적계획법을 이용해서 구현해 보았다. 현재 숫자보다 큰 숫자를 만나면 1을 더해주고, 해당숫자를 재귀적으로 호출해서 해결한다. 12345678910111213141516171819202122232425262728293031323334353637#include using namespace std;#define max(a,b) ((a)>(b) ? (a):(b))int C, N;const int MAXNUM=100001;const int MAXN = 501;int .. 더보기 조세푸스 문제 문제링크: 조세푸스 문제 원형으로 원소를 삭제하는 문제이다. 벡터나 c++라이브러리에서 지원하는 벡터나 리스트를 이용하면 간단히 되지만 다른 라이브러리를 사용하지 않으려고 링크드리스트를 만들어 사용해 보았다. - 원형 리스트를 이용한 구현123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include using namespace std;int C, N, K; typedef struct list { int elem; list *prev; list *next;} List; List *list; L.. 더보기 이전 1 다음