동적계획법 썸네일형 리스트형 LIS 문제링크: Longest Increasing Sequence 증가하는 부분 수열의 갯수를 구하는 문제이다. 동적계획법으로 풀 수 있으며, 아래보다 더 최적화된 O(NlogN) 방법이 가능하지만, 그 방법은 해당 수열을 저장하지 않는 방법이므로 일단 동적계획법을 이용해서 구현해 보았다. 현재 숫자보다 큰 숫자를 만나면 1을 더해주고, 해당숫자를 재귀적으로 호출해서 해결한다. 12345678910111213141516171819202122232425262728293031323334353637#include using namespace std;#define max(a,b) ((a)>(b) ? (a):(b))int C, N;const int MAXNUM=100001;const int MAXN = 501;int .. 더보기 이전 1 다음