동적 계획법
동적 계획법 - 13. 두니발 박사의 탈옥
문제 : 두니발 박사의 탈옥 (난이도 : 中) 분석 이 문제는 학부 때 확률과 통계를 수강했던 사람이면 마르코프 연쇄(Markov Chain)를 생각할 수 있을 것이다. 앞서 푼 문제를 참고하면 확률을 처리하는데 큰 문제는 없을 것이다. 2021/01/03 - [알고리즘 문제 해결 전략] - 동적 계획법 - 10. 우물을 기어오르는 달팽이 동적 계획법 - 10. 우물을 기어오르는 달팽이 문제 : 달팽이 (난이도 : 下) 분석 처음 풀면 매우 당황스러운 문제이다. 경우의 수를 구하는 것과 달리 확률은 어떻게 처리할지 고민이 된다. 그러나 코드를 한번 보고 나면 어떻게 처리할지 감 return-value.tistory.com search(days, num) = 탈옥 d일 후 두니발 박사가 num 마을에 있을..
동적 계획법 - 12. 폴리오미노 & 메모이제이션
문제 : 폴리오미노 (난이도 : 中) 분석 일단 poly(n) = n개의 정사각형으로 만들 수 있는 세로 단조 폴리오미노의 수를 반환한다고 하자. 그러나 매개변수 n 하나로 폴리오미노의 위치를 정하기가 애매하고 어렵다. 따라서 1st row에 있는 정사각형 수 별로 나머지 rows의 폴리오미노 반환을 받아야 한다. 1st row의 정사각형 개수를 firsts라고 할 때, poly(n, first) 함수를 정의하자. poly 함수는 n개의 정사각형을 포함하되, 1st row에 first개의 정사각형이 들어가는 폴리오미노의 수를 반환한다. 1st row에 first개의 정사각형이 있고, 2nd row에 second개의 정사각형이 있다고 하자. 이때 이들을 붙일 수 있는 방법의 수는 first + second..
동적 계획법 - 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..