11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ** 문제 유형 동적 프로그래밍, LIS ** 풀이 가장 긴 증가하는 부분 수열(LIS) 문제는 전형적인 동적 프로그래밍 문제 수열의 크기가 N일 때, 기본적인 동적 프로그래밍 알고리즘으로 O(N^2)에 해결 가능 D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이 N = 6일 때, n = int(input()) array = list(map(int, input(..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ** 문제 유형 동적 프로그래밍 ** 풀이 배낭 문제(Knapsack Problem)으로 알려져 있는, 전형적인 동적 프로그래밍 문제 물품의 수 = N, 배낭에 담을 수 있는 무게 = K 동적 프로그래밍을 이용하여 시간 복잡도 O(NK)로 문제 해결 가능 +) 핵심 아이디어 모든 무게에 대하여 최대 가치를 저장하기 D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치 각..

1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net ** 문제 유형 동적 프로그래밍 ** 풀이 사용할 수 있는 타일의 종류는 2개: (1), (00) 두 가지 종류의 타일을 이용하여, N 길이의 수열을 만드는 모든 경우의 수를 계산 가장 전형적인 동적 프로그래밍 문제 N이 최대 1,000,000 이므로 시간 복잡도 O(N)으로 해결해야 함 +) 과정 N = 2일 때, 경우의 수는 2가지 -> (11), (00) N = 3일 때, 경우의 수는 3가지 N = 4일 때, 경우의 수는 5가지 동적 프로그래밍 문제를 풀기 위해..