다이나믹프로그래밍(DP)
-
백준 11055 번: 가장 큰 증가 부분 수열다이나믹프로그래밍(DP) 2018. 8. 2. 10:16
https://www.acmicpc.net/problem/11055 1. 문제수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 2. 알고리즘키워드 - 다이나믹 프로그래밍 가장 큰 증가 부분 수열중 가장 큰 값은 113 이다. 3. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#i..
-
백준 1912번: 연속합다이나믹프로그래밍(DP) 2018. 7. 3. 10:07
https://www.acmicpc.net/problem/1912 1. 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 2. 알고리즘키워드 - 다이나믹프로그래밍, 브루트 포스 * 접근초기 문제를 풀때 부르트포스로 해결 했었는데. 7달 뒤 보니 채점 기준이 달라져서 시간 초과 되었다. 입력 받는 수열 에서이전 값과의 합이 더크 다면 현재 dp 에 dp[i - 1] + dp[i] 저장 이전 값과의 합이 작다면 현..
-
백준 10986번: 나머지 합다이나믹프로그래밍(DP) 2018. 7. 1. 19:20
https://www.acmicpc.net/problem/10986 1. 문제수 N개 A1, A2, ..., AN이 주어진다. 이 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 2. 알고리즘키워드 - DP, 부분합참고 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-10986 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #..
-
백준 1904번: 01타일다이나믹프로그래밍(DP) 2018. 6. 24. 16:44
https://www.acmicpc.net/problem/1904 1. 문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 지원이는 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 N개 수열로 이루어진 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) ..
-
백준 11726번: 2xn 타일링다이나믹프로그래밍(DP) 2018. 6. 23. 17:19
https://www.acmicpc.net/problem/11726 1. 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 2. 알고리즘키워드 - 다이나믹 프로그래밍 피보나치 응용 문제로 보이기도 한다.2 x 1 타일 - 1 개2 x 2 타일 - 2 개2 x 3 타일 - 3 개2 x 4 타일 - 5 개N 개의 타일을 만들위해 DP[N] = DP[N-2] + DP[N-1] 점화식을 세울 수 있다. 3. 코드1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #in..
-
백준 11441번 : 합 구하기다이나믹프로그래밍(DP) 2018. 6. 18. 14:50
https://www.acmicpc.net/problem/11441 1. 문제 N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 2. 알고리즘 키워드 - 부분 합최초의 입력 받은 배열은 위 처럼 10, 20, 30, 40, 50 으로 이루어 져있는 배열이다. 배열의 부분합을 만들기 위해 0 번째 배열을 추가하고 배열[i-1] + 배열[i] 부분 합을 구한다. 문제 에서 1번과 4번 배열의 합을 구하라고 나와 있다. 1번 부터 N 까지는 모두 계산이 되어 있음으로 위와 같이 답을 도출 할 수 있다. 두번 째 예제에서는 2번 부터 4 까지의 합을 계산 해야 한다.2번 의 부분합은 30 임으로 ..