Knapsack 알고리즘 (배낭싸기 알고리즘 ) " 당신이 보석을 털러 보석점에 침입했다. 각각의 보석 n개가 있고 보석마다 무게와 가치가 다르다. 당신의 가방에 담을 수 있는 무게에 한계가 있을 때, 당신이 가져나올 수 있는 보석들의 가치 합은 최대 얼마인가. " 무게와 가치가 따로 있고 가져갈 수 있는 최대 가치를 묻는 문제들, 이런 류의 문제는 Knapsack 알고리즘으로 풀 수 있다. 모든 경우를 다 따져보는 알고리즘, 즉 Greedy 알고리즘으로 이 문제를 해결할 수 있다. 하지만 시간복잡도가 2^n이기 때문에 n이 커지면 시간이 오래걸린다. 그리고 항상 최적의 답을 낼 거라는 보장이 없다. Greedy 알고리즘은. 그렇기에 Knapsack 문제는 다이나믹 프로그래밍으로 풀어야한다. w[i]가 i번째 보석의 무게, v[i]가 i번째 보석의 가.. 백준 12865 / 평범한 배낭 무게와 가치가 주워지는 n개 중 가장 최적의 무게로 최대의 가치를 뽑아내는 알고리즘은 Knapsack 알고리즘(https://naivep.tistory.com/72)이라고 따로 단어가 있다고 한다. D[i][j]를 첫번째부터 i번째까지 물건을 탐색했고, 탐색해서 담은 물건들의 무게 합을 j라고 할때 가중치의 합이다. 여기서 i번째 물건을 담은 경우와 담지 않은 경우가 있는데 담은 경우는 D[i-1][j-w[i]] + v[i]이다. ( w[i]는 i의 무게, v[i]는 i의 가치) 담지 않은 경우는 D[i-1][j] 여기서 모든 j의 경우에 대해 max값을 찾으면 된다. 코드 123456789101112131415161718192021222324252627282930313233343536#include#i.. 백준 11066 / 파일 합치기 연속 연속 연속 연속 다이내믹프로그래밍 문제 D[i][j]를 i부터 j까지 파일을 하나로 합치는데 드는 최소 비용이라고 하자. 메인 로직은 i부터 j 사이에 있는 어느 k에 대해 D[i][j] = min( D[i][j], D[i][k] + D[k+1][j] + i부터 j까지 다합친 크기) 이다. 여기서 최소값이기 떄문에 D를 연산에 들어가기 전 최대값으로 초기화해주어야한다. i부터 j까지 다 합친 크기를 한번 더 더해주는 이유는 i-k부터 끊고 k+1-j까지 끊은 걸 합쳐줄 떄 비용이 발생하기 떄문. for문으로 풀기엔 case 정의가 어려워 재귀로 풀어야한다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243.. 백준 11058 / 크리보드 d[n]을 n번 눌러서 출력할 수 있는 A의 최대 개수라고 하자. 마지막 입력 그러니까 n-1에서 n으로 넘어가는 입력에 따라 경우를 나누어보자. 1. 마지막에 1를 눌렀을 경우 d[n-1]에서 A가 하나 추가되니 d[n]은 d[n-1]+1이다. 2. 마지막에 2를 눌렀을 경우 마지막에 2를 누르는 경우는 최대값이 될 수가 없음으로 무시 3. 마지막에 3을 눌렀을 경우 마지막에 3을 누르는 경우 또한 최대값이 절대 될 수가 없음으로 무시 4. 마지막에 4를 눌렀을 경우 n이 7이상인 모든 경우엔 마지막에 4를 누르고 끝나야 최대값이다. 4를 눌렀다는 것은 2와 3을 이전에 수행했다는 뜻. 고로 n-3때 2를 누르고 n-2때 3, n-1에 4를 누르는 경우이다. 그러므로 d[n] = 2*d[n-3] 그러나.. 백준 2293 / 동전 1 다이나믹 프로그래밍 문제 풀이법은 1,2,3 더하기 4 문제와 같다. (https://naivep.tistory.com/66) 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우라는 뜻은 중복을 허용하지 않는다는 뜻. d[i]가 i원을 만들 수 있는 경우의수라고 하면 모든 동전마다 그 동전으로 i원을 만들 수 있는 경우의 수를 d[i]에 추가해준다. 그렇기 때문에 for문의 순서는 for(동전의 개수)for(0부터 k까지) 가 되고, 중복이 허용되는 경우는 for(0부터 k까지)for(동전의 개수) 로 하면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#include#incl.. 백준 15989 / 1,2,3 더하기 4 1,2,3을 이용하여 수를 만드는데 중복 없이 만드는 경우의 수를 묻는 문제이다. 코드를 보면 코드 1234567891011121314151617181920212223242526272829303132333435363738#include#include#include#include#include#include#include using namespace std; int d[10001]; int main() { //freopen("Text.txt", "r", stdin); int testcase; cin >> testcase; int nums[3] = { 1,2,3 }; d[0] = 1; for (int j = 0; j > n; cout 백준 10942 / 팰린드롬? 거꾸로 읽어도 같은 것을 팰린드롬이라고 한다. 처음엔 스트링으로 받은다음 reverse를 사용하여 풀어보려 했는데 시간초과. O(MN)인데 M의 최대가 백만이니 시간초과가 날수 밖에. 그리하여 다이나믹 프로그래밍으로 풀었다. D[S][E]를 S번째 수부터 E번째 수까지 팰린드롬이면 1 아니면 0 아직 구하지 못했으면 -1로 설정했다. 탑다운 방식으로 구현했는데 로직은 1. S==E 이면 팰린드롬 2. S+1 == E 일때 arr[S]==arr[E]이면 팰린드롬 다르면 X 3. arr[S]==arr[E]일때 D[S+1][E-1]가 1이면 팰린드롬 아니면 X 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445.. 백준 1890 / 점프 우선, 경로의 개수의 최대값이 2^63-1이니 BFS로 풀면 메모리초과가 난다. (ex) 모든 칸이 1로된 100x100 게임판) 다이나믹 프로그래밍으로 풀어야 한다. d[i][j]가 i,j에 도착할 수 있는 모든 경우의 수라고 했을때, 0보다 크고 i보다 작은 어떠한 k에 대해서 map[k][j] + k가 i가 되는 경우를 찾는다면, d[i][j]는 d[k][j]로 이루어질 것이다. 또한, map[i][k] + k가 j가 되는 경우를 찾는다면 d[i][j]는 d[i][k]로 이루어질 것이다. d의 값에 2^63-1이 들어갈 수 있으니 d는 long이상을 선언해주어야한다. 코드 (34~43번째 코드가 핵심) 123456789101112131415161718192021222324252627282930313.. 이전 1 2 3 4 5 6 7 ··· 12 다음
