반응형 [백준]214 [BaekJoon/백준] 1149번 / 순열조합은 동적계획법인가? | 복습 1회 완료 이 문제는 혼자 못 풀었다. 다른 분의 코드를 참고한 뒤 풀었다. 처음에 내가 구현한 코드는 아래와 같다. 재귀함수를 사용했다. #include int arr[1000][3]; int memo[1001]; int N; int min = 1000000; void print_count() { int result = 0; for(int i = 0; i result) min = result; } void rgb(int count) { if(count > N) { print_count(); return; } for(int i = 1; i < 4; i++) { if(!(memo[count - 1]==i)) { memo[.. 2020. 12. 26. [BaekJoon/백준] 9461번 | 복습 1회 완료 파도반 수열에 대한 문제. 피보나치랑 비슷한 느낌이다. 이를 동적계획법으로 구현하면 된다. P(N)에 대해서 나열해봤고, Tn에 대해서 나열해봤다. 여기서 P(N)은 문제에서의 파도반수열이고 Tn은 삼각형 종류와 각 관계에 대한 수열이다. 그림에서보면 T3부터 더해지는 수의 앞자리가 P(N)에서 순서대로 가져와지며, 뒷자리는 자신의 바로 이전 삼각형을 참조한다는 것을 알 수 있다. 그리고 마침 T3인 P(6)부터 'P(N - 1) = P(N)의 이전 삼각형' 이 되므로 (1 1 1 2 2 에서는 n-1이 항상 n의 이전삼각형이 아니기 때문에) 이를 토대로 아래 식을 만들어 낼 수 있다. P(N) = P(N - 5) + P(N - 1) // 단, N>5이며 P(1)=1, P(2)=1, P(3)=1, P(4.. 2020. 12. 24. [BaekJoon/백준] 1904번 | 복습 1회 완료 타일 문제. 처음엔 이걸 순열과 조합으로 풀려고 시도했다. 팩토리얼을 자주 쓰게 되니 팩토리얼 값이 중복이 생기므로 메모이제이션을 활용하면 되겠다고 생각했다. 극복하지 못한 내 소스코드 #include long long fac_num[1000000]; long long factorial(int num) { if(num < 2) return fac_num[1]; else { if((fac_num[num])) return fac_num[num]; else return (fac_num[num] = num * factorial(num - 1)); } } int main() { int n, max, i = 1, count = 0; scanf("%d", &n); fac_num[1]=1; max = n/2; // 최.. 2020. 12. 16. [BaekJoon/백준] 2748번 피보나치 수열을 동적계획법으로 푸는 문제다. 동적계획법 - 동적 계획법은 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다 - 동적 계획법은, 쪼개지는 부분 문제가 중복될 때 메모이제이션을 사용하여 속도를 향상시키는 방법이다. 즉 하나의 문제가 부분 문제로 쪼개져서 푸는 문제에서, 같은 부분 문제들이 있다면 이들을 한 번만 실행하게끔만 구현해주는 것. (중복되는 문제에 대한 답을 여러 번 구할 필요가 없도록, 한 번 실행할 때 결과값을 캐시해놨다가 다음에 실행될 때는 캐시해놓은 값을 꺼내 쓰는것) - 부분 문제로 쪼개서 원래의 답을 구한다는 점, 최적 부분 구조에서 사용된다는 점에서.. 2020. 12. 14. 이전 1 ··· 37 38 39 40 41 42 43 ··· 54 다음 반응형
