Algorithm_BOJ(백준)/동적프로그래밍(DP) (65) 썸네일형 리스트형 [백준 11053 c++ VOO] 가장 긴 증가하는 부분 수열 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 11053 c++ VOO] 가장 긴 증가하는 부분 수열 // 문제: LIS 가장 긴 증가하는 부분수열(오름차순의 부분수열)의 길이를 구하는 문제 // 접근1: 브루트포스로 큰 수 나올 때마다 카운트해서 최대값 찾으려 생각-> 시간초과 예상으로 안함 // 점근2: dp를 이용해 각 자리마다 나오는 증.. [백준 2193 c++ VOO] 이친수 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 2193 c++ VOO] 이친수 // 문제: n 자리 이친수의 개수 구하기 // 접근1: dp결과값으로 규칙 찾기 -> 못찾음 // 접근2: 2차원 dp : 0으로 끝나는 경우, 1로 끝난는 경우 // 풀이: // 점화식 dp 작성 // dp 점화식: // 0으로 끝나는 경우 dp[i][0] = dp[i.. [백준 10844 c++ VVO] 쉬운 계단 수 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#define _CRT_SEC.. [백준 15990 c++ VO] 1, 2, 3 더하기 5 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 15990 c++ VO] 1, 2, 3 더하기 5 // 문제: 정수를 1,2,3의 합으로 나타내는 방법의 수를 출력, 같은 숫자 연속된 수의 합은 안됨 // 접근: 1,2,3 경우를 나눔 -> dp -> 탑다운 방식: .. [백준 16194 c++ OO] 카드 구매하기 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 16194 c++ OO] 카드 구매하기 2 // 문제: n 개의 카드를 구매할 때 비용의 최솟값 구하기 // 접근1: 완전텀색 -> 시간초과 예상 // 접근2: 그리디: 제일 작은 값만 더하기 또는 가성비 제일 좋은카드만 더하기 ->카드갯수의 합이 n개가 .. [백준 11052 c++ VVO] 카드 구매하기 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 11052 c++ VVO] 카드 구매하기 // 문제: n 개의 카드를 구매할 때 비용의 최댓값 구하기 // 접근1: 완전텀색 -> 시간초과 예상 // 접근2: 그리디: 제일 큰 값만 더하기 또는 가성비 제일 좋은카드만 더하기 ->카드갯수의 합이 n개가 되는지 모.. [백준 9095 c++ OO] 1, 2, 3 더하기 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 9095 c++ OO] 1, 2, 3 더하기 // 문제: 정수를 1,2,3의 합으로 나타내는 방법의 수를 출력 // 접근: 1,2,3 경우를 나눔 -> dp -> 탑다운 방식: 정수 i 가되는 경우 // 1.i-1 에서 1 더한 것 // 2. i-2에서 2 더한 것 // 3. i-3 에서 3 .. [백준 11727 c++ VO] 2×n 타일링 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; // [백준 11727 c++ VO] 2×n 타일링 2 // 문제: 2×n 크기의 직사각형을 1×2, 2×1,2x2 타일로 채우는 방법의 수 구하기 // 접근: 보텀업: n=1부터 차례로 방법의 수들 구해보기 -> 규칙(전화식 찾기) -> 찾을 수 있지만 어려움 // 접근2 : 탑다운: dp라 생각하고 탑다운 방식으.. 이전 1 2 3 4 5 6 7 8 9 다음