동적 계획법(19)
-
[동적 계획법] 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 -
[동적 계획법] 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 -
[동적 계획법] Longest Increasing Sequence, JLIS 합친 LIS
-jlis 문제를 푸는 과정에서의 나의 잘못된 접근방법 1. LISLongest Increasing Sequence jlis 문제를 풀기전에 알고리즘 문제해결전략 책에 나와있는 LIS의 더 빠른 알고리즘을 구현하였다. (동적계획법을 사용한 O(n^2)알고리즘과 다르게 O(nlgn)만에 수행된다.) 이 알고리즘은 배열의 각 원소들을 앞에서 부터 탐색해나가며 다음과 같은 배열에 원소들을 집어넣는다. C[i] = 지금 까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막값 C[i]에 원소들을 집어 넣을 때 push()함수가 쓰이는데 이 함수는 삽입정렬과 비슷하며 다음과 같이 작동한다. C[i] 배열에 x라는 원소를 삽입하고자할 때 이 함수는 i에서 시작하여 1까지 탐색하여 lo < x && x
2021.01.08 -
[동적 계획법] WILDCARD 와일드 카드
동적 계획법을 적용한 문제 풀이 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 106 107 108 109 110 111 112 113 114 115 116 117 #include #include #i..
2021.01.07 -
[동적 계획법, 그래프] JUMPGAME 외발 뛰기
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 #include #include #define UNTRAVELED -1 #define NO 0 #define YES 1 int cache[100][100]; int board[100][100]; int dy[2]{1,0}; int dx[2]{0,1}; bool inRange(int y, int x, int n) { return ((y n; memset(cache, -1, sizeof cache); for(int j{0}..
2021.01.06