Chapter 08 - 다이나믹 프로그래밍(Dynamic programming) 1. 다이나믹 프로그래밍(동적 계획법) : 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법 1) 피보나치 수열 - 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예 n번째 피보나치 수 = (n-1)번째 피보나치수 + (n-2)번째 피보나치수 단, 1번째 피보나치수 = 1, 2번째 피보나치 수 = 2 ① 재귀 함수를 사용한 소스코드 int fibo(int x){ if(x==1 || x==2){ return 1; } return fibo(x-1)+fibo(x-2); } int main(){ cout n; for (int i = 0; i > x; arr.push_..
이코테
Chapter 03 - 그리디(Greedy) 1. 그리디 알고리즘(=탐욕법) : 현재 상황에서 지금 당장 좋은 것 만 고르는 방법 👉 매 순간 좋아 보이는 것만 선택 👉 현재의 선택이 나중에 미칠 영향에 대해 고려X 예제 3-1 ) 거스름돈(C++) Q . 손님에게 거슬러야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원이 있다) > 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함 #include using namespace std; int n;//손님에게 받은 돈 int coin[4] = { 500, 100, 50, 10 }; int ans; //거스름돈의 개수 int main() { cin >> n; for (int i = 0; i < 4; i++) ..
