다이나믹프로그래밍 검색 결과

해당 글 24건

[백준] 알고리즘 C++ 1520번 - 내리막 길문제

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 소스코드 /****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl, C#, VB, Swift, Pa..
Algorithm/dynamic programming 2022. 1. 24. 18:58

[백준] 알고리즘 C++ 1003번 - 피보나치 함수문제

문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 소스코드 #include #include using namespace std; int dp[41]; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int T; cin >> T; dp[0] = 1, dp[1] = 1, dp[2] = 1; for (int i = 3; i > x; if (x == 0) cout
Algorithm/dynamic programming 2021. 11. 14. 19:54

[백준] 알고리즘 11048번 - 이동하기문제

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 소스코드 #include #include #include using namespace std; int n, m; int arr[1001][1001],dp[1001][1001];; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); cin >> n >> m; for (int i = 1; i arr[i][j]; } } fo..
Algorithm/dynamic programming 2021. 9. 8. 18:54

[백준] 알고리즘 3-4일차 다이나믹 프로그래밍

1. 1699번 : 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net DP[N] = 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 저장 N이 되기위해 제곱수들의 합으로 표현할 때 가장 마지막에 오는 숫자가 중요하다. 가장 마지막에 오는 숫자를 j라고 한다면 1부터 N까지 j*j를 계속해서 반복해서 경우의 수를 살펴볼 것이다. 그렇다면 dp[i] = dp[i-j*j]+1 이라는 식을 도출해낼 수 있다. 마지막의 제곱수에서 N을 뺀다면 현재의 제곱수 이전의 값..
Algorithm/정리 2021. 8. 11. 12:04

[백준] 알고리즘 3-3일차 다이나믹 프로그래밍

1. 11053번 : 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP[N] = 가장 긴 증가하는 부분 수열의 길이를 저장한다. 하지만 여기서 아이디어가 필요로한데 단순히 모든 경우를 다 해본다면 2^1000승으로 시간초과가 나게된다. 배열 ARR[i]를 마지막으로 하는 부분수열을 저장해줘야 문제를 해결할 수 있다. LIS 라고하며 정답은 DP[1]~DP[N] 사이의 최댓값이 정답이 된다. #inclu..
Algorithm/정리 2021. 8. 9. 12:36

[백준] 알고리즘 3-1일차 다이나믹 프로그래밍

1. 11726번 : 2 x n 타일링 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2xn 타일링 문제는 큰 문제에서 작은문제로 어떻게 만들것인가가 중요한데, 오른쪽 끝에 타일을 붙여서 모양을 만든다고 생각하면 가로가 1인경우와 2인경우로 나눌 수 있다. 즉 오른쪽에 가로가 1인 타일을 붙이면 총 가로가 N일때, 남은 부분은 N-1의 크기가된다. 마찬가지로 2로 N-2가 된다. 점화식을 주석에 있는 것처럼 세워준후 문제를 해결한다. #include #include using namespace std; int dp[1001]..
Algorithm/정리 2021. 8. 7. 18:10

[백준] 알고리즘 11060번 - 점프 점프 문제

문제 www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 소스코드 #include using namespace std; int arr[1001]; int dp[1001]; int n; void res(int x) { for (int i = x + arr[x]; i >= x + 1; i--) { if (i dp[x] + 1) { dp[i] = dp[x] + 1; res(i); } } } } int main() { ios_base::sync_with_st..
Algorithm/dynamic programming 2021. 4. 28. 14:28

[백준] 알고리즘 2491번 - 수열 문제

문제 www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 소스코드 #include using namespace std; int arr[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, ansup = 1, ansdown = 1, lenup = 1,lendown=1; cin >> n; for (int i = 1; i > arr[i]; } for (int..
Algorithm/dynamic programming 2021. 4. 6. 16:00

[백준] 알고리즘 1890번 - 점프 문제

문제 : www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 소스코드 #include using namespace std; int n; int arr[101][101]; long long dp[101][101]; long long dfs(int x, int y) { if (x == n-1 && y == n-1) return 1; else if (dp[x][y] == -1) { dp[x][y] = 0; // 오른쪽가는친구 int right_x = x+ ..
Algorithm/dynamic programming 2021. 4. 5. 16:58

[백준] 알고리즘 12865번 - 평범한 배낭 문제

문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 소스코드 #include using namespace std; int dp[101][100001]; int arr[101][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; for (int i = 1;..
Algorithm/dynamic programming 2021. 3. 31. 20:00