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만..

1. 완전 탐색 알고리즘 이 문제는 주어진 문자열을 3-5글자씩 끊어서 특정 규칙에의해 정해진 난이도를 부여하여 전체 문자열의 최저 난이도를 계산하는 문제이다. 이 문제를 풀 함수는 한번 호출되었을 떄 문자열을 3-5길이의 문자열과 나머지 문자열로 분할한다. 난이도 판별함수를 실행하여 문제를 해결하고 (최대 5번의 for문) 나머지 문자열은 재귀호출하여 다음 부분문제로 넘어간다. 이 함수는 문자열의 길이가 n일 떄 최소 n/3 의 깊이와 최대 n/5 깊이를 가지고 3^n/3 > leaf > 3^n/5 인 잎의 개수를 가진다. 따라서 완전 탐색은 지수적 수행 시간을 가지며 이는 시간초과를 의미한다. 2. 메모이제이션 적용 부분문제는 동일하다 i 이전과 i 이후 i의 이전 문자열은 i 이후 문자열을 해결하는..

동적 계획법을 적용한 문제 풀이 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..

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}..

동적 계획법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔다. 중복되는 부분 문제 없애 최적화하여 속도향상을 꾀하는 알고리즘 설계 기법이 바로 동적 계획법이다. 동적계획법은 분할 정복과 접근방식이 같다. 주어진문제 -> 더 작은문제들 -> 조각 계산 -> 조각의 답들로부터 원래 문제 답 계산 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에 여러번 계산하는 대신 한번만 계산하고 계산 결과를 재활용함으로써 속도 향상을 꾀함 각 문제의 답을 메모리에 저장해 둘 필요가 있음 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시라고 부름 두번 이상 계산되는 부분문제를 부분 문제(overlapping subproblems)라고 부름 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적으로 ..

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 #include #include #include #include #inclu..