Algorithm_BOJ(백준)/동적프로그래밍(DP) (65) 썸네일형 리스트형 [백준 10942 c++ V] 팰린드롬? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 10942 c++ V] 팰린드롬? // 문제: 수열을 입력받고 원하는 구간의 수가 팰린드롬인지 출력 // 접근: 완전탐색 -> 각 구간 입력 받을 때 마다 팰린드롬인지 검사 -> .. [백준 11060 c++ O] 점프 점프 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 11060 c++ O] 점프 점프 // 문제: 일차원 배열의 최소 점프횟수 출력 // 접근: 완전탐색(재귀/dfs) -> -> 될 것 같음 , 시도는 안 해봄 // 접근2: 최댓값 -> dp -> 최소 점프횟수 저장하며 // dp점화식 , // dp[i].. [백준 11048 c++ O] 이동하기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 11048 c++ O] 이동하기 // 문제: 이차원 그래프의 n,m 위치까지 최대합을 구해라 // 접근: 이차원 그래프 최대합 -> bfs -> 될 것 같음 , 시도는 안 해봄 // 접근2: 이차원 그래프 위,왼 방향이 없어 뒤로 돌아가는 것 .. [백준 2133 c++ V] 타일 채우기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 2133 c++ V] 타일 채우기 // 문제: 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수 // 접근1: 경우의 수 -> 완전탐색,dp -> 탑다운 dp로 생각 // 점화식 // dp[n] : n번째 까지 만들 수 있는 경우의 수 // dp[i] = 3 * dp[i - 2] + 2*dp[i-4] + 2.. [백준 13398 c++ V] 연속합 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 13398 c++ V] 연속합 2 // 문제: 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합(수열에서 수를 하나 제거해도되고 않해도 됨) // 점근1: 연속된 수,최대합 -> 완전탐색,그리디,dp -> 탑다운 dp로 생각해.. [백준 11054 c++ OV] 가장 긴 바이토닉 부분 수열 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 11054 c++ OV] 가장 긴 바이토닉 부분 수열 // 문제: 한 원소를 기점으로 양쪽에서 가장 긴 증가하는 부분수열(오름차순의 부분수열)의 길이를 구하는 문제 // 점근1: dp를 이용해 각 자리마다 나오는 증가하는 부분수열의 최대값 저장 .. [백준 11722 c++ O] 가장 긴 감소하는 부분 수열 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 11722 c++ O] 가장 긴 감소하는 부분 수열 // 문제: 가장 긴 감소하는 부분 수열의 길이를 구하라 // 접근1: 최댓값(완전탐색,그리디,dp) -> 탑다운 dp로 생각 -> 가장 긴 증가하는 부분수열의 길이에서 부호만 바꿔줌 응용 // dp[n] : n번째 까지의 감소하는 최대 부분수열 길이 .. [백준 11055 c++ O] 가장 큰 증가 부분 수열 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // [백준 11055 c++ O] 가장 큰 증가 부분 수열 // 문제: 증가 부분 수열 중에서 합이 가장 큰 것을 구하라 // 접근1: 최댓값(완전탐색,그리디,dp) -> 탑다운 dp로 생각 // dp[n] : n번째 까지의 증가하는 최대 부분수열의 합 // 가장 긴 증가하는 부분수열에서.. 이전 1 2 3 4 5 6 ··· 9 다음