전체 글(220)
-
[동적 계획법] 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 -
[동적 계획법] 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