개발기록장

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 입력 첫째 줄에..

다이나믹 프로그래밍이란? 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 기법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식 조건 다이나믹 프로그래밍은 다음 조건들을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있고 그 작은 문제의 답을 모에서 큰 문제를 해결할 수 있는 경우 동일한 작은 문제를 반복적으로 해결해야하는 경우 메모이제이션(Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다. 한 번 계산한 결..