KPU CE

이번 시간에는 다이내믹 프로그래밍을 알아보도록 하겠습니다. 다이나믹 프로그래밍은 재귀적으로 문제를 해결할 때 불필요하게 같은 연산을 하는 것을 없애고자 만들어진 알고리즘 기법입니다. 대표적인 예로 피보나치 수열을 예로 들어서 설명하겠습니다. 피보나치수열 피보나치수열은 0,1로 시작하고 그다음 피 보나 치수는 앞에 두 수를 더한 값이 됩니다. Ex) 0,1,1,2,3,5,8,13,21,34,55,89.... 피보나치수열을 재귀적으로 구현했을 경우 코드는 다음과 같습니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 #include using namespace std; int fibo(int n){ if(n == 1){return 1;} else if(n == 0){return 0;} return ..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제해결 1. 다이나믹 문제이지만 재귀를 이용하여 풀었다. 2. 각 DAY마다 재귀를 이용하여 상담이 가능한 날짜를 탐색했다. 코드 1234567891011121314151617181920212223#include using namespace std;int N,Max = 0;int ary[16][2];void DFS(int node,int count){ if(count >= Max){Max = count;} for(int i = node;iN){continue;} DFS(ary[i][0]+i,count+ary[i][1]); } ..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 나도 다른 사람의 풀이를 보고 알았다. 다이나믹 프로그래밍은 너무 어려운듯하다. 문제해결 1. 10,20,10,30,20,50 이 수열A로 있으면 맨 처음 인덱스인 10의 대한 dp[0] = 1(길이) dp[1] = 2 dp[2] = 1 이런식으로 한다. 2. 처음 인덱스부터 자기자신 전까지 탐색를 한다..