전체 글 (596) 썸네일형 리스트형 KLIS 1. LIS 의 Length 구하기 2. LIS 의 Count 구하기 3. K 번쨰 LIS 구하기 Dynamic Programming Technics 로 들어오니 넘 어렵다... #include #include #include using namespace std; const int MAX_N = 500; const int MAX_K = 2000000000 + 100; int N = 0, K = 0; vector nums, kLis; int cacheLen[MAX_N + 1]; int cacheCnt[MAX_N + 1]; int lisLength(int start); int lisCount(int start); void reconstruct(int start, int skip); int main() { i.. LUNCHBOX #include #include #include using namespace std; vector m, e; vector lunchSet; int minLunchTime(); int main() { int caseNum = 0; cin >> caseNum; int n, mInput = 0, eInput = 0; for (int cIter = 0; cIter > n; for (int i = 0; i > mInput; m.push_back(mInput); } for (int i = 0; i < n; i++) { cin .. PACKING 배낭 문제(Knapsack Problem) 중 0/1 Knapsack Problem 이다.Knapsack Problem 은 여러 가지 형태가 있다. (추후에 다른 버전도 도전... 쿨럭) #include #include #include #include using namespace std; const int MAX_STUFF_NUM = 100; const int MAX_CARRIER_CAPACITY = 1001; const int MAX_STUFF_NAME_LENGHT = 20; const int MAX_STUFF_VOLUME = 1001; const int MAX_STUFF_DESIRE = 1001; int C = 0, N = 0, W = 0; typedef struct stuff { string nam.. NUMB3RS 두니발 박사의 탈옥 문제를 두 가지 방식으로 풀었다.첫번째는 책에 나온 DP 를 활용한 방법,두번째는 내가 직접 푼 방법. 책에 나온게 훨씬 더 깔끔하다.책에서는 두니발이 이동했을 법한 경로를 추적하여 모든 경로를 DP를 활용하여 구한다. 이 중 유효한 경로들의 확률값 계산을 재귀호출의 리턴값을 이용하여 해결했다. 나의 경우엔 그냥 무식하게 풀었다. A 마을에서 B 마을로 이동할 확률을 계산한 2차원 배열을 만들고, 하루가 지날 때마다 각 마을에 이동했을 확률을 계산하였다. 덕분에 3중 for문 (ㄷㄷ) 을 시전하였다. Time Complexity 는 n^2 * d 로 동일하지만 코드의 가독성을 볼 땐 종만 아저씨의 코드가 훨씬 깔끔하고 우아하다. ps) DP를 구현하다가 기저 사례를 cache 값 참조.. POLY #include using namespace std; const int MAX_N = 101; const int MOD = 10000000; int cache[MAX_N][MAX_N]; int n; int getTotPoly(int n); int poly(int n, int top); int main() { int caseNum = 0; cin >> caseNum; for (int cIter = 0; cIter > n; // Initialize for (int i = 1; i ASYMTILING #include using namespace std; const int MAX_N = 101; const int MOD = 1000000007; int n; int cache[MAX_N]; int tiling(int n); int main() { int caseNum = 0; cin >> caseNum; for (int cIter = 0; cIter > n; // Initialize for (int i = 0; i QUANTIZATION #include #include #include #include using namespace std; const int MAX_ERROR = 999999; const int MAX_N = 100; const int MAX_S = 10; int cache[MAX_N][MAX_S]; int sum[MAX_N]; int sumSquare[MAX_N]; vector quants; int n = 0, s = 0; int quantize(int from, int parts); int minError(int start, int end); int main() { int caseNum = 0; cin >> caseNum; for (int cIter = 0; cIter > .. PI #include #include using namespace std; const int MAX_BUFFER_SIZE = 10001; const int MAX_INPUT_SIZE = 10001; const int MAX_DIFFICULTY = 99999; char input[MAX_BUFFER_SIZE]; int cache[MAX_INPUT_SIZE + 1]; int getMinDiff(int start); int calcMinDiff(int start, int end); int main() { int caseNum = 0; cin >> caseNum; cin.ignore(); for (int cIter = 0; cIter < caseNum; cIter++) { cin.getline(input, MAX_B.. 이전 1 ··· 69 70 71 72 73 74 75 다음