Algorithm_BOJ(백준)/동적프로그래밍(DP) (65) 썸네일형 리스트형 [백준 15989 c++ V] 1, 2, 3 더하기 4 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; /* [백준 15989 c++ V] 1, 2, 3 더하기 4 문제:n을 1,2,3,의 합으로 순서다른 수는 제외하고 나타내는 방법의 수 구하기 접근1: 완탐 재귀-> 재귀시 현재 더한 수보다 큰 수만 더하기 재귀해서 순서다른것 중복 제외 -> 시간초과 예상 시간복잡도: O(n^n) 10000^10000 접근2: dp -> 2차.. [백준 1890 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; /* [백준 1890 c++ V] 점프 문제: 2차원 그래프에서 해당 인덱스의 숫자만큰 오른쪽,아래 이동해서 맨 오른쪽 아래까지 경로의 수를 구하라 접근: 2차원 그래프 오른쪽/아래 방향으로 뒤로 돌아갈수 없음 -> 2차원 dp로 그 위치까지의 경로의 갯수 저장하며 반복문 완탐 점화식: dp[i][j]: i행j.. [백준 11726 c++ VOO] 2×n 타일링 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 #include using namespace std; // [백준 11726 c++ VOO] 2×n 타일링 // 문제: 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수 구하기 // 접근: n=1부터 차례로 방법의 수들 구해보기 -> 규칙(전화식 찾기) // 접근2 : dp라 생각하고 탑다운 방식으로 n번째에 더해지는 경우들을 생각 -> //n번째에는 n-1번째에서 .. [백준 2747 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 2747 c++ O] 피보나치 수 // 문제: // 접근: 피보나치 -> dp // 시간복잡도: O(n) = 45 // 풀이: #define MAX 92 int n; int dp[MAX]; int main() { ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류 cin.tie(nullptr); cout.tie(nullpt.. [백준 2748 c++ O] 피보나치 수 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 2748 c++ O] 피보나치 수 2 // 문제: // 접근: 피보나치 -> dp // 풀이: // 범위가 크기 때문에 longlong 으로 해야 함 #define MAX 92 int n; long long dp[MAX]; int main(){ ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류 cin.tie(nullptr); .. [백준 1463 c++ VOO] 1로 만들기 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 // memset 헤더 #include #include using namespace std; // [백준 1463 c++ VOO] 1로 만들기 // 문제: -1./3,/2 3가지 계산을 통해 1로 만들 때 최소 연산 횟수를 구하라 // 접근: 완전 -> 시간초과 예상, 그리디 -> 최소 횟수 아닌 경우 있음 틀림 // 접근2: 3가지 조건 세분화, 중복 -> dp -> n부터 탑다운 .. [백준 1495 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 1495 c++ V] 기타리스트 // 문제: // 접근: 완전탐색 -> i번째 마다 +,- 하는 2가지 경우 -> 답은 맞으나 O(2^n) = 2^100 시간초과 // 접근2: dp -> // dp점화식 , // dp[i][j] = i번째.. [백준 12856 c++ XX] 평범한 배낭 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 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include // memset 헤더 using namespace std; // [백준 12856 c++ XX] 평범한 배낭 // 문제: 냅색문제 . 가방에 넣을 수 있는 무게대비 최대 가치를 구하는 문제 // 접근: 재귀로 모든 경우의 수 탐색 -> O(2^100) 시간초과 안함 // 접근2: dp // dp 점화식 // dp[i][j]= i번.. 이전 1 2 3 4 5 ··· 9 다음