전체 글
동적 계획법 - 11. 비대칭 타일링
문제 : 비대칭 타일링 (난이도 : 下) 분석 위 문제는 이 문제의 연장선이다. 2021/01/01 - [알고리즘 문제 해결 전략] - 동적 계획법 - 8. 타일링 방법의 수 세기 동적 계획법 - 8. 타일링 방법의 수 세기 문제 : 타일링 (난이도 : 下) 분석 타일링하는 방법은 다음과 같이 2가지가 나온다. 경우의 수를 셀 때 항상 확인해야 하는 조건이 있다. 위 문제로 예를 들면 다음과 같다. 1. 이 두 가지 분류는 return-value.tistory.com 이 문제는 두 가지 방법으로 풀 수 있는데 어느 것을 선택하느냐에 따라 난도가 살짝 달라진다. 첫 번째 방법은 전체 경우의 수에서 대칭인 경우를 빼는 것이다. 두 번째 방법은 비대칭인 경우의 수를 직접 구하는 것이다. 난도는 첫 번째 방법이..
동적 계획법 - 10. 우물을 기어오르는 달팽이
문제 : 달팽이 (난이도 : 下) 분석 처음 풀면 매우 당황스러운 문제이다. 경우의 수를 구하는 것과 달리 확률은 어떻게 처리할지 고민이 된다. 그러나 코드를 한번 보고 나면 어떻게 처리할지 감이 잡힐 것이다. ※ 주의할 점이 하나 있는데 double형 배열을 memset으로 초기화하면 에러가 발생한다. 평소 하던 대로 하면 콘솔 창에 결괏값이 -nan이 나온다. 찾아보니 부동소수점 표기때문에 에러가 나는 것 같다. 필자는 간단하게 memset 대신 이중 for문으로 배열을 초기화했다. 구현 #define MAX_N 1000 int n, m; double cache[MAX_N][2 * MAX_N + 1]; //days동안 climbed[m] 올라왔을 때 //m일 전까지 n[m] 올라갈 확률 double ..
동적 계획법 - 9. 삼각형 위의 최대 경로 개수 세기
문제 : 삼각형 위의 최대 경로 개수 세기 (난이도 : 中) 분석 이 문제는 앞서 푼 삼각형 위의 최대 경로 문제의 연장 문제이다. 2020/12/24 - [알고리즘 문제 해결 전략] - 동적 계획법 - 3. 삼각형 위의 최대 경로 동적 계획법 - 3. 삼각형 위의 최대 경로 문제 : 삼각형 위의 최대 경로 (난이도 下) 분석 문제를 보며 처음 든 생각은 '최대합을 반환하면 되지 않을까?'였다. 하지만 생각해보면 최대합을 memoization으로 처리하기엔 배열의 크기가 너무 return-value.tistory.com 최대 경로의 합을 반환하는 함수 path()가 있다고 하고, count(y, x) = (y, x)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수를 반환한다고 하자. 그럼 다음과 같은 ..
동적 계획법 - 8. 타일링 방법의 수 세기
문제 : 타일링 (난이도 : 下) 분석 타일링하는 방법은 다음과 같이 2가지가 나온다. 경우의 수를 셀 때 항상 확인해야 하는 조건이 있다. 위 문제로 예를 들면 다음과 같다. 1. 이 두 가지 분류는 타일링하는 방법을 모두 포함해야 한다. 2. 두 가지 분류에 모두 포함되는 타일링 방법은 없다. 이 문제는 단계마다 세로 타일 하나로 덮을 것인지, 가로 타일 두 개로 덮을 것인지만 결정하면 된다. 남은 공간이 각각 2x(n-1), 2x(n-2)가 되므로 재귀 호출로 쉽게 답을 구할 수 있다. 2xn 크기의 사각형을 타일로 덮는 경우의 수를 반환하는 함수를 tiling(n)이라 할 때, 다음과 같은 점화식이 성립한다. tiling(n) = tiling(n-1) + tiling(n-2) 구현 int MOD ..
동적 계획법 - 7. Quantization
문제 : Qunatization (난이도 : 中) 분석 양자화를 하는 데 있어 다음과 같은 규칙이 있다. 같은 수로 양자화되는 숫자들은 인접한 숫자들이다. 따라서 일단 입력된 수열을 크기순으로 정렬을 할 필요가 있다. from번째 이후의 숫자들을 parts개의 묶음으로 묶을 때, 최소 오류 제곱 합을 반환하는 함수를 quatize(from, parts)라 하자. a번째 수부터 b번째 수까지 하나의 수로 표현했을 때의 최소 오류를 반환하는 함수를 minError(from, from+size-1)라 하자. 그럼 다음과 같은 점화식이 성립된다. quantize(from, parts) = min[ minError(from, from+size-1) + quatize(from+size, parts-1) ] (단, ..
동적 계획법 - 6. 원주율 외우기
문제 : 원주율 외우기 (난이도 : 下) 분석 조각의 길이가 3, 4, 5 중 하나이므로 다음과 같이 생각해보자. 1. 길이가 3인 조각 난도 + 3글자 뺀 나머지 수열에 대한 최적해 2. 길이가 4인 조각 난도 + 4글자 뺀 나머지 수열에 대한 최적해 3. 길이가 5인 조각 난도 + 5글자 뺀 나머지 수열에 대한 최적해 시작 위치가 주어졌을 때 최소 난도를 반환하는 함수를 memorize(begin), 주어진 구간([a, b])의 난도를 반환하는 함수를 classify(a, b)라 하자. 구현 const int INF = 987654321; string input; //input[a, b] 구간의 난도를 반환한다. //난도를 판단하는 if문 눈에 익혀두자. int classify(int a, int b..
동적 계획법 - 5. 합친 LIS
문제 : 합친 LIS (난이도 : 下) 분석 A[index_A], B[index_B]에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수를 JLIS(index_A, index_B)라고 하자. 두 순서는 작은 쪽이 앞으로 온다고 가정하고 다음과 같은 점화식을 세울 수 있다. JLIS(index_A, index_B) = max{ max JLIS(next_A, index_B) + 1, max JLIS(index_A, next_b) + 1 } 소스 코드를 보면 무슨 말인지 이해가 될 것이다. 구현 최소치 구현 부분도 눈여겨 봐보자. //32비트의 정수가 입력치이므로, 최소치는 64비트여야 한다. const long long NEGINF = numeric_limits::min(); int n, m, A[..
동적 계획법 - 4. 최대 증가 부분 수열
문제 : 최대 증가 부분 수열 (난이도 下) 코드 int n; int cache[101], S[100]; int makeLIS(int start) { int& ret = cache[start + 1]; if (ret != -1) return ret; ret = 1; //최소길이 1 for (int next = start+1; next > C; while (C--) { memset(cache, -1, sizeof(cache)); cin >> n; for (int i = ..