본문 바로가기

Programming Problems/Dynamic Programming

longest Chunked palindrome list Examples : Input : VOLVO Output : 3 Explanation : (VO)L(VO) Input : merchant Output : 1 Explanation : No chunks possible. Input : ghiabcdefhelloadamhelloabcdefghi Output : 7 Explanation : (ghi)..
숫자 n 이 주어졌을 때, 완전제곱수의 합으로 표현할수 있는 최소 갯수는? 우선 "최소"를 물어본데다, 최적해가 없어 보이고(자료구조해도), DP가 될 것 같아 보이니까 완전탐색에서 시작해서 DP로 캐핑해보자.그냥 완전탐색을 생각해 보면, 본인보다 작은 모든 완전제곱수를 1 ~ 최대 갯수만큼 채우면서 재귀를 돌려보자.int findmin(int n, int curr, int total){if(curr==0) return 0;int ret = INT_MAX;for(int i = 0 ; curr*i<=n ; i++){re..
합이 같은 두 부분집합으로 배열을 쪼갤 수 있을까? 진짜 멍청한 조합탐색(정말 순서 없이는 절대 풀 수가 없어서 - 폭탄이 터진다던가 - 결국에는 순서를 전부 기록해야 결과 확인이 가능한 경우)고른다. 마지막에서 계산한다. 확인한다.여기에서 더 발전시킬 수 없을까? "마지막에 하는 작업을 분산시킬 수 있나"마지막에 뭘 하는데? 합을 구한다. 그러면 합을 단계별로 구할 수 있잖아? 당연하지.그러면 현재까지의 합을 인자로 넘겨가며 계산한다.어 인자가 두개네, curr, sum >> DP cap..
배열 원소간 모든 차이값을 주어진 값 이하로 맞추는 최소 변환 수 차이값을 주어진 값 이하로 맞추면서, 원래 배열에서 최소 한도로 움직이도록 해야 한다. 그 바꾼 값을 반환하자.ex )[1,4,2,3]target = 1;>> ans :[2,3,2,3]바꾼 양 : 2  >>> ans = 2** 솔직히 이 문제는 "최적 값을 구하시오" 그리고 "숫자 상한이 100이다" 에서 - 아 이 문제는 DP구나 가 바로 떠올라서 완전 탐색으로 넘어갈 생각을 했어야 한다. 뭐 그리디 한..