동적계획법 (2) 썸네일형 리스트형 [C / C++] 백준 1003번 - 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ✅ 문제 설명 테스트 케이스 T를 입력한 후 T개의 숫자 N을 입력하면, N의 피보나치 수열에서 0과 1이 몇 번 출력되는지 묻는 문제이다. ✅ 알고리즘 설명 1. 일반 피보나치 함수 처음에는 C를 사용하여 평범한 피보나치 함수를 사용했다. #define _CRT_SECURE_NO_WARNINGS #include #include int zero[40]; int one[40]; int fibonacci(int n, int i) { if (n == 0) { zero[i]++; return 0; }.. [알고리즘] DP 동적계획법 ✅ 동적계획법(DP) 1. 동적계획법이란? - 하나의 큰 문제를 여러 개의 작은 문제로 분할하여 푸는 방법 - 이미 계산된 작은 문제의 결과 값을 별도의 메모리 영역에 저장해두고 활용함. - 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킬 수 있음. 답을 재활용하는 것! "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘 2. 동적계획법 사용 조건 1) 큰 문제를 작은 문제로 나눌 수 있음. 2) 작은 문제에서 구한 값이 그것을 포함하는 큰 문제에서도 동일한 값으로 사용됨 (피보나치 수열) ✅ 분할정복법 VS 동적계획법 공통점 큰 문제를 쪼개서 가장 작은 단위로 분할한다. 차이점 - 분할정복법 : 부분 문제는 서로 중복되지.. 이전 1 다음
