Algorithm/Dynamic Programming (7) 썸네일형 리스트형 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.. WILDCARD #include #include #include #include using namespace std; const int MAX_BUFFER_SIZE = 1024; const int MAX_TEXT_LENGTH = 100; char input[MAX_BUFFER_SIZE]; string src, dest; int cache[MAX_TEXT_LENGTH][MAX_TEXT_LENGTH] = {-1, }; vector results; bool IsMatched(int srcIdx, int destIdx); int main() { int caseNum = 0; cin >> caseNum; cin.ignore(); for (int cIter = 0; cIter < caseNum; cIter++) { // initi.. BINOMIAL COEFFICIENT #include #include using namespace std; const int MAX_NUM = 1024; int cache[MAX_NUM][MAX_NUM]; void initCache(); int binomial(int n, int r); int main() { int caseNum = 0; int n = 0, r = 0; cin >> caseNum; for (int cIter = 0; cIter > n >> r; cout 이전 1 다음