728x90 동적계획법 썸네일형 리스트형 [백준알고리즘] 2293번: 동전 1 -C [백준알고리즘] 2293번: 동전 1 -C https://www.acmicpc.net/problem/2293 단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ 처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다. 역시나 시간초과가 발생했다. 그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다. dp[i][j] = dp[i - 1][j] + dp[i][j - nlist[i]] (i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을.. 더보기 [알고리즘]Knuth's optimization 크누스 최적화 백준의 11066번 문제를 풀다가 발견한 최적화 기법이다. (문제를 해결했던 코드) 이 알고리즘은 동적 계획법으로 해결하는 문제에서 특수한 조건일 때 시간 복잡도를 \(O(n^3)\)에서 \(O(n^2)\)까지 줄일 수 있는 강력한 알고리즘이다. 사용할 수 있는 동적 계획법의 종류에는 이차원 배열인 \(C\)와 \(C\)를 이용한 Dynamic Programming을 적용한 이차원배열인 \(DP\)가 있다고 했을 때 다음과 같은 조건이 필요하다. 점화식의 형태: \(DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j]\) \((i < k < j)\) 사각 부등식: \(C[a][c] + C[b][d] 더보기 [백준알고리즘] 1520번: 내리막 길 -Python [백준알고리즘] 1520번: 내리막 길 -Python https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 20200408 아래 새로 풀었다. 요즘 계속 DP를 다시 보고 있다. 오늘은 내리막 길을 풀어봤는데 금방 풀렸다. 개인적으로 dp 중에서는 쉬운 편이었다고 생각을 한다. 이번에는 최저의 방법을 구하는 것이 아닌 가능한 경우의 횟수를 구하는 문제다. 그러다.. 더보기 [백준알고리즘] 12865번: 평범한 배낭 -Python [백준알고리즘] 12865번: 평범한 배낭 -Python 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 제목처럼 평범한 Dynamic Programming문제이다 처음에는 DFS와 upper bound를 이용한 Branch and Bound를 사용하려 하다가 사실상 Brute Force보다 조금 나은 수준의 코드가 되어버린 것.. 더보기 이전 1 2 3 4 다음