김머성 블로그

동적계획법 PS 팁

동적계획법이란 큰 문제를 같은 해법을 가지는 재귀적인 부분문제들로 나눠서 각각의 해를 더해나가며 큰 덩어리의 해를 구하는 알고리즘이다. 문제 난이도가 올라갈 수록 점화식이나 DP테이블을 만들 때 어떻게 만들어야 할지 헷갈린다. 그래서 테이블 형태를 구상하거나 점화식을 구현할 때 도움이 됐던 팁 몇가지를 적어보겠다. 1. 문제 단계 분할 말 그대로 문제를 단계별로 분할한다. 이전 단계와 현재 단계에 관계가 있도록 분할 해야한다. 다음 단계의 최적해를 유추해 낼 때 현재(혹은 이전) 단계의 최적해를 사용해야한다. 만약 다음 단계의 최적해를 유추해 낼 때 현재 단계의 최적해를 전혀 사용하지 않는다면 문제를 잘못 이해했을 가능성이 상당히 높다. 2. 각 단계마다 영향을 주는 요소 갯수로 테이블 생성 - 만약 각..

[BAE/<JOON> 문제풀이] 11060. 점프점프

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net 더보기 #include #include #include using namespace std; int main() { vector arr, dp; int n; cin >> n; arr.resize(n + 1); dp.resize(n + 1); for (int i = 1; i > arr[i]; } dp[1] = 0; for (int i = 2; i = i) { dp[i] = min(dp..

[BAE/<JOON> 문제풀이] 2302. 극장좌석

https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 > n >> m; vector dp; vector arr; arr.resize(m + 2); dp.resize(n + 1); for (int i = 1; i > arr[i]; } int s = 2; int d = 1; for (int i = 0; i

동적 계획법::메모이제이션

동적 계획법이란:: 문제를 같은 해법을 가지는 재귀적인 덩어리로 분할 해서 각각 분할된 부분 문제들을 해결하고 이를 합쳐나가며 전체의 해를 찾는 풀이법을 말한다. 완전 탐색과 다른 점은 이미 계산된 해를 계산하지 않는다는 점이다. 이 때, 나눠진 부분 문제들이 같은 문제 일 경우, 의미없는 중복계산이 발생되어 코드가 느려진다. 메모이제이션은 각각의 부분문제들의 대한 해법을 따로 테이블에 계산해놓고 같은 부분 문제가 나올 경우, 그 해를 사용하는 알고리즘 기법이다. 이를 통해서 중복된 계산을 피하고 백트래킹으로는 답을 구하기 힘든 문제들을 비교적 쉽게 계산 할 수 있다. 중복 계산을 소거하기 위해서 사용되는 대표적인 기법이다. 부분 문제에 대한 해를 구했을 경우 그 해를 저장해놓고 이 후, 풀이과정에서 같..

[BAE/<JOON> 문제풀이] 1495.기타리스트

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 이것도문제 종류 중 하나 같다. 정확히 어떤 문제였는지는 생각이 안나는데 덧셈 뺄셈을 번갈아 사용하며 최종값을 만드는 문제 유형이다. 이런 유형을 따로 모아서 정리해봐야겠다. 더보기 #include #include using namespace std; int main() { int n, s, m; cin >> n >> s >> m; vector arr; vec..

[BAE/<JOON> 문제풀이] 2098. 외판원 순회

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 더보기 #include #include #include using namespace std; int n; vector arr; int dp[17][1