다이나믹 프로그래밍

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 다이나믹 프로그래밍 (Dynaminc Programming)은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 알고리즘이다. 동적 계획법이라고도 불린다.

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.선영: 그럼 안돼. 만약, "

완전 탐색을 이용해서 해당 문제를 풀 경우, 모든 도시에 대한 순열을 구해서 최소 비용을 탐색해야하는데, 그러면 최악의 경우 16! 만큼의 경우의 수가 나오므로 시간내에 문제를 해결할 수 없다.

bottom-up 방법을 활용해서 bfs식으로 해당 문제를 해결했다.또, 숫자 체크에 기존 배열을 이용하기엔 숫자의 자릿수가 너무 많아서 비트마스킹을 사용하였다.

dp에 어디서부터 왔는지 방향까지 지정해서 풂

https://www.acmicpc.net/problem/1256dpx : x개의 a와 y개의 z로 만들 수 있는 문자열 수dp 배열에 a와 y의 갯수에 대해 만들 수 있는 문자열의 수를 저장해나가고, 구한 갯수를 기반으로 사전 순서를 고려하여 로직을 짰다.x

https://www.acmicpc.net/problem/1351문제에서 제공한 점화식을 이용해 재귀함수를 작성해서 풀면 되는 문제이다.메모이제이션을 이용한 DP로 문제를 풀 경우, N의 범위가 $$10^{12}$$ 이므로, 배열로는 안되고 map 을 이용해서

https://www.acmicpc.net/problem/11568이 문제는 n의 범위가 1000이라서 2중 반복문을 이용해서 $$O(n^2)$$의 시간복잡도로도 풀이가 가능하다.cache\[i] : i번째 인덱스에서 끝나는 LIS의 최대 길이j를 0부터 i