🍑동적 프로그래밍 동적 프로그래밍은 Dynamic Programming 즉, DP라고 불리는 알고리즘 기법이다. 복잡한 문제를 점화식으로 만들어 분할 정복할 때, 반복문 또는 재귀를 사용할 수 있는데 이 과정에서 계산의 결과 값을 저장해두어 중복되는 계산을 하지 않도록 만들어준다. 이는 점화식 이렇게 결과 값을 저장해두는 것을 메모이제이션이라고 하는데, 보통 배열의 형태로 수행된다. DP 과정 전체 문제를 부분 문제로 단순화한다. 1번의 과정에서 점화식을 도출한다. 점화식을 이용하여 배열로 간단히 해결할 수 있는지 생각한다. bottom-up top-down 없다면 재귀함수를 만들고 메모이제이션한다. 메모이제이션 방식은 보통 배열이다. 전체 문제를 해결한다. 대표 문제 피보나치 수열 구하기 피보나치 수열..

Quantization https://www.algospot.com/judge/problem/read/QUANTIZE 나의 답 알고리즘 수열을 정렬한다. 부분 수열들의 경우의 수를 돌면서 부분 수열의 오차합이 가장 적은 수열을 구한다. 2번 과정에 대해서 최적부분구조임을 발견하고 각 부분 수열의 오차합을 메모이제이션하는 방식으로 진행하여야한다. 하지만 본인은 메모이제이션을 부분 수열을 모두 완성했을 때 진행하는 식으로 하여 어쨌든 부분 수열을 만드는 재귀함수의 끝에 도달해야 메모이제이션을 쓸 수 있게 구현하였다. 이 점이 시간초과의 원인이 되었다고 생각한다. 코드 코드1 #include #include using namespace std; int N, S; int arr[100]; int* num_idx..