프로그래민👨‍💻

Knapsack을 활용한 문제이다. Knapsack dp문제를 활용하여 접근해보았다. dp[N][cost]를 생성하고 메모리가 기준값을 넘을 때 마다 cost값을 최솟값으로 갱신하는 방법으로 접근해보았다. 맨처음 이 문제를 접근했을때 cost값대신 메모리 값으로 접근하였는데, cost 값기준으로 접근하는 것을 생각해내는데 오래걸렸다. 다만 cost값을 기준으로 접근하니깐 문제를 수훨하게 풀 수 있었다. 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 56 57 58 59 pac..

유명한 Knapsack 문제이다. Knapsack 대표적인 문제이다. 보통 Knapsack 문제를 접근할때는 크게 두가지 방법이 있다. 크게 브루트포스와 dp로 접근할 수 있다. 브루투포스로 접근은 단순하게 고르고, 안고르고를 반복하며 재귀호출하는 방식이다. 이 방식은 시간복잡도가 2^N 이기에 대다수의 문제에서 적용이 힘들다. 이 문제또한 N의 최대값이 100이기에 적용이 불가하지만 한번 코드는 작성해보았다. 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 42 43 44 45 46 47 package algostudy2..

dp와 dfs를 같이 활용한 문제이다. 저번에 풀었던 1520번 내리막길과 비슷한 문제이다. 마찬가지로 dfs를 도는데 최대 n의 크기가 500이 되므로 중간에 이차원 dp 배열을 통해 메모이제이션을 활용하는 전략을 사용했다. 이 문제도 마찬가지로 dp 이차원 배열을 -1로 초기화 시키고 dfs 의 반환값을 dp[i][j]로 반환하면서 dp값을 찾는 방식이다. 다만 이 문제에서 유의할점은 각 위치에서의 최대값을 찾는 것이기 때문에 dp를 갱신할때 dfs+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 ..

dfs와 dp를 같이 활용하는 문제였다. 맨처음 문제를 보았을때 백트래킹으로 접근해보았다. 하지만 M과 N이 최대 500을 가지고 있기에 시간초과를 우려하게 되었다. 따라서 메모제이션을 활용할 수 있는 dp를 같이 접목해보았다. dp[i][j]라는 배열을 두고 i,j에서의 M,N을 도달하는 방법의 수를 가지도록 설계를 하였다. 즉 dfs를 돈 경험이 있는 i,j 위치를 탐색해야할때 다시 dfs를 도는 것이 아니라 dp[i][j] 값만을 반환하도록 메모이제이션을 활용해주었다. 이 때 주의할점은 이차원 dp 배열의 초기값을 -1로 하는 것이랑 dfs 메소드가 dp[i][j]를 반환하도록 설계하는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

다이나믹 프로그래밍을 활용한 문제였다. 이 문제는 성냥개비를 활용하여 가장 큰 수와 가장 작은 수를 만들는 문제였다. 모든 조합의 경우를 확인하는 방법도 있지만 보다 효율적으로 확인할 수 있는 DP가 있기에 DP를 사용하여 큰 수, 작은 수를 각 각 구하였다. 우선 간단한 큰수의 경우 계속 자릿수를 늘려가는 방법 생각해보았다. 우선 가장 작은 성냥개비가 드는 수는 1로써 성냥 두개를 사용하게 되는데 이것을 이용하여 모든짝수를 구할 수 있었다. 홀수의 경우 7이 성냥 세개를 사용하는데 이것을 이용하여 하나의 홀수 + 나머지는 짝수를 사용하는 방식을 사용할 수 있었다. 따라서 다음과 같은 점화식을 사용할 수 있었다. dp[2] = 1, dp[3] = 7, dp[i] = concat(dp[i-2], 1) 또한..

다이나믹 프로그래밍 문제이다. 1차원 DP문제로써 점화식을 세우는데 오래걸리진 않았다. 각 k 에선 k-동전가치 만큼에서 경우들을 더해주면 구할 수 있으므로 다음과 같은 점화식을 구했다. for 1부터 k까지 for 모든 동전가치 dp[k] = dp[k] + dp[k-동전가치] 하지만 이문제에선 하나의 조건이 더 있는데 바로 동전의 구성이 같다면 카운팅을 안해주는 것이었다. 바로 중복의 경우르를 제거해주는 것인데, 이것을 어떻게 구현할지 한참을 고민하였다. 답은 바로 1부터 k까지가 아니라 모든 동전에 대해서 먼저 처리를 해주는 것이었다. for 모든 동전가치 for 1부터 k까지 dp[k] = dp[k] + dp[k-동전가치] 다음과 같은 점화식으로 풀 수 있는 문제였다. 1 2 3 4 5 6 7 8 ..

DP문제이다. 코딩테스트에 나왔던 문제이다. 그 당시 효율성을 해결하지 못하여 풀지 못했어서 다시 풀어보았다. 맨처음 문제를 보고 자연스럽게 바텀업이 생각났고 DP로 접근하게 되었다. 다음과 같은 점화식으로 DP를 풀었다. DP[i] = min(DP[i], DP[i-현재 코인의 값] + 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 42 43 44 45 46 47 48 49 package study4; import java.io.BufferedRe..

DP를 이용하여 쉽게 구할 수 있는 문제이다. 이 문제는 끝자리의 자연수가 가장 중요한 문제이다. 그래서 다음과 같은 설계를 해보았다. dp[N][i] => N의 자리수를 가진 자연수 중에서 i의 수를 맨끝 자리로 가지는 자연수, 예를 들면 534 는 dp[3][4]에 속하는 하나의 자연수가 된다. 이와 같은 것을 이용하여 다음과 같은 점화식을 세웠다. dp[N][i]= dp[N-1][i-1] + dp[N-1][i+1] 단, i=0일땐 i+1 만 i=9일땐 i-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 package boj.base; import java.io.Buffere..

DP를 이용한 문제이다. 이 문제의 기본 점화식은 다음과 같다. dp[n]= dp[n-1] (1을 더해주는 경우) + dp[n-2] (2를 더해주는 경우) + dp[n-3] (3을 더해주는 경우) , 하지만 이 문제에서는 연속하여 두개이상의 자연수를 사용하면 안되는 조건이 생겼기에 다음과 같이 dp배열을 설계하였다. dp[n][i] => i의 숫자를 맨마지막 숫자로 가지는 경우 예를 들면 n=3일 경우 dp[3][1]은 2+1 이 있으므로 1, dp[3][2]은 1+2 이 있으므로 1, dp[3][3]은 3이 있으므로 1이 나오게 된다. 이런식으로 최종 점화식을 구하면 dp[n][1] = dp[n-1][2] + dp[n-1][3], 1을 더하는 경우 n-1에서 2와 3으로 끝나는 것에 더할 수 있음. d..

DP를 사용하는 문제이다. 이 문제는 DP를 사용하는 문제인데 다음과 같은 점화식을 가진다. dp[n]= max(dp[i] + cost[n-i], cost[n]) (1