11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 다이나믹 프로그래밍(DP) 문제입니다. dp 배열에는 dp[i]의 값과 비교하면서 현재까지의 가장 긴 증가하는 부분수열의 길이가 업데이트되게 됩니다. 그렇게 해서, dp 배열의 값 중 가장 큰 값을 출력 size = int(input()) A = list(map(int, input().split())) dp = [..
다이나믹 프로그래밍
1912번: 연속합 (acmicpc.net) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 다이나믹 프로그래밍(DP) 문제입니다. 먼저 수열을 입력받고, dp라는 배열도 하나 생성해 줍니다. (for 문을 통해 주어진 수열의 크기만큼 일단 0으로 채워줍니다.) 그리고, numbers의 값과 dp 안에 있는 값들을 서로 비교하며 가장 큰 값을 찾아냅니다. 그림으로 표현하면 이런 구조일 겁니다. n = int(input()) numbers = list(map(int, input().split())) dp = [0 f..
