분류 전체보기69 배낭 알고리즘 n개의 물건과 배낭이 있고, 물겅에는 가치와 무게 값이 존재한다. 배낭에는 최대 용량이 존재하고 이 용량 안에서 담을 수 있는 물건의 최대 가치를 찾는다. 다이나믹 프로그래밍 , 즉 큰 문제를 작은 문제로 쪼개 푸는 것으로 해결 가능하다.dp는 이차원 배열로 작성하고 dp [ 현재 탐색하는 물건 ] [ 가방의 남은 공간 ] = 최대 가치 가방 최대 5키로0 번 물건/3kg1번 물건2 번 물건3 번 물건4 번 물건0키로 1키로 3키로 4키로 5키로 이런 형태의 표를 생각 할 수 있다 ..d[1][6] 은 1번 물건을 담으려 하는데 남은 공간이 6키로라는 의미다.1번 물건이 3키로에 3달러라 했을 때, 배낭의 최대 가치는 d[i][3] 중 최대 값 +3 달러 일 것이다... 2024. 11. 9. 백준 2656 전깃줄 문제를 있는 그대로 받아들여서 교차점이 제일 많은 전깃줄부터 제거하여 문제를 풀려 했지만 교차점이 같은 전깃줄에서 어느 것을 먼제 제거할지 결정하기가 어려웠다..결국 서치하여 알아낸 것은문제 풀이 방법이 증가하는 가장 긴 부분 수열을 구하는 문제라는 것! 왼쪽 전봇대와 오른쪽 전봇대를 볼 때, 왼쪽에서 출발하는 전깃줄이 도착하는 오른쪽 전봇대의 인덱스를 나열하여, 그중에서 제일 긴 증가하는 부분수열을 구하면 되는 문제였다.. 가장 긴 증가하는 부분 수열을 구하는 방법은?dp 배열을 이용한다.dp[a]=b의 의미는 a번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이는 b이다. 라는 의미임 정렬되지 않은 순서로 입력이 주어질 수 있으므로 저장한 값을 먼저 정렬해주고, dp 배열에 값을 할당한다. #i.. 2024. 11. 5. 백준 1920 수 찾기 #include#include#includeusing namespace std;vector a;void find(int s, int e, long long i) { int mid = (s + e) / 2; if (e i) { find(s, mid-1, i); } if (a[mid] > n; for (int i=0; i > k; a.push_back(k); } cin >> m; sort(a.begin(), a.end()); for (int j = 0; j > k; find(0, a.size()-1, k); } return 0;}배열에 원소를 삽입하고 find 함수를 작성하여 그 안에서 이분탐색을 진행하였다. end>start인 경우에는 정답을 찾지 못한 것이므로 0을 출력, a[mid]가 찾던 값인.. 2024. 9. 30. 백준 2295 세 수의 합 #include#include#includeusing namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vectorarr(n,0); for (int i = 0; i > arr[i]; } sort(arr.begin(), arr.end()); int max; int x, y, z; for (int m = n - 1; m >= 0; m--) { max = arr[m]; for (int j = m; j >= 0; j--) { y = arr[j]; for (int i = j; i >= 0; i--) { x = arr[i]; z = max - x - y; if (z 숫자를 n 개 입력받아 ar.. 2024. 9. 30. 이전 1 2 3 4 5 6 ··· 18 다음
