https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. Logic 1. 1은 어떻게 계산 하던지 자기 혼자 더하는게 무조건 이득 2. 양수는 무조건 큰숫자부터 곱해서 더하고 혼자남으면 그냥 혼자 더히기 3. 음수는 절댓값이 큰 숫자부터 곱해서 더하고 혼자 남으면 그냥 더하기 or 0이 있으면 넘어가기 4. 0은 -1이 없거나 음수의 갯수가 짝수면 필요없지만 -가 홀수면 음수를 없애는데 사용 2. Code #include using namespa..
코테
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. Logic - 버틸수 있는 무게 >= 지금까지의 무게 + 이번(넣을 or 넣지 않을) 차례의 무게 - 가능하다면 이후의 항의 최댓값에 현재 배낭의 value를 더해주기 #include using namespace std; vector goods; int dp[101][100001]; int n, k; int solve(int ..
1. Dynamic Programming 이란? Dynamic Programming 즉 동적 계획법은 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 내가 이해한 DP란 재귀를 활용하게 되면 알고리즘 문제를 풀 때 이미 계산한 값도 중복해서 계산을 해야 하지만 DP는 내가 생성한 DP테이블에 계산한 값을 저장해 놓기 때문에 동일한 연산을 마주치면 값을 계산하지 않고 dp테이블에서 가져와서 하위 연산을 하지 않기 때문에 시간복잡도를 줄일 수 있음. 동적계획법이라고 하기보단 "memoization / 값 저장해서 필요할 때 가져오는 방법" 이라고 이해하면 편할 것 같다 2. DP와 재귀 연산횟수 비교 (백준 2576 계단 오르기) 해당 문제 또한 ..
