알고스팟(70)
-
[동적 계획법] OCR 광학 문자 인식
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 #include #include #include #include #include #include #include using namespace std; st..
2021.01.13 -
[동적 계획법] PACKING 여행짐 싸기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 #include #include #include #include #include class pac { public: std::string name; int imminence; int w; pac(); pac(std::s..
2021.01.13 -
[동적 계획법] NUMB3RS 두니발 박사의 탈옥
1. 완전 탐색 이 문제는 day만큼 날이 지난다음 q의 마을에 p에서 탈옥한 박사가 있을 확률을 구하는 문제이다. 날마다 박사는 인접한곳으로 이동한다. 그러므로 완전 탐색으로 풀때에는 p에서 시작해서 확률을 곱해가며 모든 경우의 수를 세면서 마지막 날일 때 ret[town] += 해당 경우의 확률 이처럼 더해가면된다 그 후 ret[0] ret[2] 를 호출하게되면 바로 바로 답이 나오게 된다. 2. 점화식 이 문제에서 동적 계획법을 적용하려면 완전 탐색 과는 다르게 뒤에서 부터 생각해야한다. FIND(remainDay, startpoint) = Σ(per(startpoint) * FIND(remainday - 1, next)) remainDay의 날짜가 남았을 떄 startpoint부터 시작하여 교도소..
2021.01.11 -
[동적 계획법] ASYMTILING 비대칭 타일링
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include const int MOD = 1000000007; int wide = 0; int cache[100][100][3]; int asy(int vertical, int horizontal, int before) { int &ret = cache[vertical][horizontal][before], ishalf = 0, width = vertical+ indexx; if(ret != -1) return ret; if (wide % 2 == 0 && ((width == wide/2 + 1 && befor..
2021.01.10 -
[동적 계획법] Quantization
1. 완전 탐색 알고리즘 이 문제는 입력으로 주어진 배열을 먼저 정렬해야한다. 정렬을 하고나면 이 문제는 간단히 풀 수 있다. 어떤 구간에서 평균값이 오차의 최소값이므로 우리는 부분문제를 평균값과 오차의 제곱 합을 따로 구할 수 있는 함수를 구현만하면 된다. end quant(begin) = min(quant(hi)+ quantization(begin, hi)) begin = 0 hi = 1 quantization(begin, hi)는 begin부터 hi까지 배열의 평균값 오차의 제곱 합을 반환하는 함수이다. 2. 메모이제이션 적용 Cache[begin][usednum] = usednumb만큼 양자화를 수행한 상태에서 begin으로 시작하는 배열의 양자화 오차 제곱의 합의 최소값을 가짐 usednumb만..
2021.01.09 -
[동적 계획법] PI 원주율 외우기
1. 완전 탐색 알고리즘 이 문제는 주어진 문자열을 3-5글자씩 끊어서 특정 규칙에의해 정해진 난이도를 부여하여 전체 문자열의 최저 난이도를 계산하는 문제이다. 이 문제를 풀 함수는 한번 호출되었을 떄 문자열을 3-5길이의 문자열과 나머지 문자열로 분할한다. 난이도 판별함수를 실행하여 문제를 해결하고 (최대 5번의 for문) 나머지 문자열은 재귀호출하여 다음 부분문제로 넘어간다. 이 함수는 문자열의 길이가 n일 떄 최소 n/3 의 깊이와 최대 n/5 깊이를 가지고 3^n/3 > leaf > 3^n/5 인 잎의 개수를 가진다. 따라서 완전 탐색은 지수적 수행 시간을 가지며 이는 시간초과를 의미한다. 2. 메모이제이션 적용 부분문제는 동일하다 i 이전과 i 이후 i의 이전 문자열은 i 이후 문자열을 해결하는..
2021.01.09