목록동적계획법 (6)

F.R.I.D.A.Y.

BAEKJOON 1912:연속합(DP)

주어진 배열에서 연속하는 각 요소의 합이 최대인 값 구하기. 코드 #include using namespace std; #define max(x,y) ((x) > (y) ? (x) : (y)) int main() { int n; int* arr; cin >> n; arr = new int[n]; for (int i = 0; i > arr[i]; int result = arr[0]; { for (int i = 1; i 0 && arr[i - 1] + arr[i] > 0) { arr[i] += arr[i - 1]; } result = max(arr[i], result); } } cout 0 위 조건을 추가해 점화식을 적용하면 다음..
DEV/Algorithm 2021. 12. 21. 11:13
BAEKJOON 1932:정수 삼각형(DP)

최대 합이 되는 경로 검색 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 2차원 배열로 구성을 했다변 더 좋았겠지만, 2차원 배열을 굳이 사용하지 않더라도 수식만으로 2차원 배열을 사용하는 것처럼 구성이 가능하다는 것을 보이기 위해 1차원 배열을 사용해봤다. #include using namespace std; int main() { int n; cin >> n; int* arr = new int[n * n]; cin >> arr[0]; for (int i = 1; i > arr[i * n]; arr[i * n] += arr[(i - 1) * ..
DEV/Algorithm 2021. 12. 21. 02:38
BAEKJOON 11053:가장 긴 증가하는 부분 수열 O(nLogn) for C++(DP)

LIS를 해결하는 시간 복잡도 O(nLogn)의 알고리즘 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include using namespace std; int main() { int n; cin >> n; int* input, * dp; input = new int[n]; dp = new int[n + 1]{}; for (int i = 0; i > input[i]; int maxLength = 1..
DEV/Algorithm 2021. 12. 21. 02:15
BAEKJOON 11053:가장 긴 증가하는 부분 수열 O(n²) for C

가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include int main(void){ int size, max = 1; int data[1000], dp[1000]; scanf("%d", &size); for(int i = 0; i d..
DEV/Algorithm 2021. 9. 8. 22:08
BAEKJOON 2579: 계단 오르기 for C

계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 설명 DP 공부를 하면서 느낀건데, 규칙성이 있다면 점화식을 구하는게 급선무?라 생각한다. 일단, 문제에서 규칙을 정해주었기 때문에 규칙을 보면 다음과 같다. 여기에서 중요한 것이 (3)인데, 마지막에 대한 설명이 존재하기 때문이다. 따라서 마지막 규칙을 기반으로 하면 다음과 같다. dp[i] = dp[i - 3] + data[i - 1] + data[i]; dp[i] = dp[i - 2] + data[i]; 배열 dp는 여태 계산상에서 가장 높은 수를 찾은 데..
DEV/Algorithm 2021. 9. 7. 22:04
동적 계획법(다이나믹 프로그래밍, DP)

문제를 해결하는 데 있어서는 많은 방법이 있습니다. 프로그래밍이란 결국 문제를 해결하는 과정을 순차적으로 나열한 것이라고 봐도 무방하겠지요. 오늘 포스트에서는 동적 계획법, 다르게 말하면 다이나믹 프로그래밍(Dynamic Programming, DP)에 대해 알아봅니다. Q. 피보나치 수 구하기 갑자기 웬 피보나치 수를 구하느냐구요? 동적 계획법을 설명하는 가장 간단하면서도 이 기술을 처음 접하는 사람들이 이해하기 쉬운 문제이기 때문입니다. 위 문제를 구하라고 한다면 대체적으로 아래와 같은 두 가지 방법 중 한 가지를 이용할 겁니다. // # F[1] = F[2] = 1; int fibonacci1(int n){ // 재귀 함수를 이용한 방법 if(n > 2){ return fibonacci1(n-1) ..
DEV/Algorithm 2019. 11. 24. 23:09
Prev 1 Next