KPU CE

문제 https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 문제 해결 문제에서 주어진 점화식을 다이나믹으로 그대로 구현하였다. 코드 #include using namespace std; int main(void){ int N; long long dp[36],temp = 0; dp[0] = 1; dp[1]..

문제 https://www.acmicpc.net/group/board/view/9362/19864 로그인 www.acmicpc.net 문제해결 다이나믹 프로그래밍으로 풀었다. fibo(n) = fibo(n-1) +fibo(n-2) 이라는 식을 규칙을 보고 유추하여서 배열로 구현하였다. 코드 #include #pragma warning(disable : 4996) int main(void) { int n; long long int ary[92]; ary[0] = 0; ary[1] = 1; scanf("%d",&n); for (int i = 2; i

문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 일단 크게 두가지 경우로 나뉜다. 1. 시간이 초과되서 상담을 그날 상담을 못하는 경우 2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우 일단 1번의 경우이다. 상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다. 2번의 경우 1.상담을 할 수 있..

문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 일단 크게 두가지 경우로 나뉜다. 1. 시간이 초과되서 상담을 그날 상담을 못하는 경우 2. 시간이 초과되지 않아서 그날에 상담을 할 수 있는 경우 일단 1번의 경우이다. 상담을 한다면 N보다 초과되어서 이날의 상담은 하지 못하므로 이날의 최대 dp의 값은 i+1의 값이 된다. -> 이날 상담을 안하고 다음 날 한다. 2번의 경우 1.상담을 할 수 있..

문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 해결 1. 그 자리에서 3을 점프뛰면 앞, 앞앞, 앞앞앞까지 탐색하는데 현재 dp의 값+1과 탐색한 자리에 dp값과 비교해서 작은 값을 선택한다. 2. 만약 그 자리가 끝이거나 넘어서면 결과값의 dp이므로 현재 자리의 dp값과 결과값dp를 비교해서 작은값이 결과값dp가 된다. 코드 12345678910111213141516171819202122232425262728293031..

이번 시간에는 다이내믹 프로그래밍을 알아보도록 하겠습니다. 다이나믹 프로그래밍은 재귀적으로 문제를 해결할 때 불필요하게 같은 연산을 하는 것을 없애고자 만들어진 알고리즘 기법입니다. 대표적인 예로 피보나치 수열을 예로 들어서 설명하겠습니다. 피보나치수열 피보나치수열은 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. 처음 인덱스부터 자기자신 전까지 탐색를 한다..