전체 글66 백준 9084 흐흑너무 어려웠다경우의 수를 구하는 문제였는데, 뭔가 묘하게 이해가 될까 말까 했다. 현재 금액을 만들 수 있는 가짓 수를 찾는 문제인데 이해하기 쉽게 가정을 해본다. [동전]번호 1 2 3 4 금액 10 20 30 40 60원을 만들기 위해서는 동전의 개수만큼 루프를 돈다 해당 인덱스의 동전이 만들 수 있는 금액부터 최대액 까지 루프를 돈다. 이 금액을 만들기 위한 가지수는 루프를 돌면서 [금액- 현재 동전의 가치] 만큼씩 더해준다for(동전의 가지수 i) for(가능한 금액 j) dp[금액 j] += dp[금약 j - i 번째 동전의 개수] 이런 식의 루프를 형성한다. 제일 중요하다고 생각한 부분은 dp배열.. 2024. 11. 10. 배낭 알고리즘 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. 이전 1 2 3 4 5 ··· 17 다음
