'Programming Problems/Dynamic Programming'에 해당되는 글 4건

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)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)


------------------

최악의 경우

(abcde) 1 개는 보장된다.

최선의 경우

abcba >> n개가 보장

azcba >> 3개

(a)(zcb)(a)

일단 팰린드롬인 애는 그대로 포장할 수 있다. 포장해도 되는 애를 안해서 얻는 이득이 있나?

팰린드롬인 단어를 포장하지 않는 경우 갯수가 무조건 감소하거나 같게 되므로 이득이 없다는 것을 안다. 만약 팰린드롬인 단어를 포함해야만 다른 곳의 아수라장을 피할 수 있다면?

a(c)za(c)z

안되면 더 큰걸 잡아야지 "안됨" 이 되는게 아니라서, 이런 그리디 솔루션은 어렵다.

이렇게 답이 막히면 완전탐색부터 시작해 보자. DP로 비벼질 지도?

acbac >> a c 달라서 안됨! ac는 됨! 이걸로 묶어서 그 안에껄 재귀하자. 오 이거 되겠네. 디피문제구나.

리얼 완전탐색을 생각하니 디피로 풀리는구나. 막히면 완전탐색!

postfix = prefix 경우를 순회하면서 모두 찾는다. 각각의 경우에 대해 2 + 안쪽 재귀 결과값을 구해서 그 최솟값을 찾아준다.

아, 그리고 *** " 최솟값 " 이 나오면 DP 일 가능성이 매우 높다.


막히면 완전탐색..

막히면 완전탐색..

막히면 완전탐색..!!!!


!!!!!


int findminbrackets(string & s, index k){

// base case

if(k==s.size()/2) return 1;

string tmp(s.begin()+k,s.end()-k-1);

string cmp = tmp;

reverse(tmp.begin(),tmp.end());

if(cmp==tmp) return s.size()-2*k;

// general case, find postfix == prefix

int ret = 1;

for(int i = k+1 ; i <= s.size()-k; i++){

int j = i;

int l = k;

int flag = 0;

while(j<=s.size()-k){

if(s[l]==s[j]){

j++;

k++;

}else{

flag = 1;

break;

}

}

if(flag==1) continue;

// found a postfix==prefix

ret = max(ret,2+findminbrackets(s,s.size()-j+1));

}

return ret;

}


caching을 쓰면 결국에는 가능한 k의 값이 N개 뿐이고, 각 순회에 대해 O(N)의 행위를 하므로 O(N^2) 이다..!!

Programming Problems/Dynamic Programming

숫자 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++){

ret = min(ret, i+findmin(n-curr*i,curr-1,total));

}

return ret;

}


time complexity : 함수실행 N * sqrt(N), 실행당 대량 sqrt(N) 회 수행 >> O(N^2) 알고리즘 쯤 될듯.

Programming Problems/Dynamic Programming

합이 같은 두 부분집합으로 배열을 쪼갤 수 있을까?

진짜 멍청한 조합탐색(정말 순서 없이는 절대 풀 수가 없어서 - 폭탄이 터진다던가 - 결국에는 순서를 전부 기록해야 결과 확인이 가능한 경우)

고른다. 마지막에서 계산한다. 확인한다.


여기에서 더 발전시킬 수 없을까? "마지막에 하는 작업을 분산시킬 수 있나"

마지막에 뭘 하는데? 합을 구한다. 그러면 합을 단계별로 구할 수 있잖아? 당연하지.


그러면 현재까지의 합을 인자로 넘겨가며 계산한다.


어 인자가 두개네, curr, sum >> DP capping이 가능해진다.

게다가, sum = total/2 면 자동으로 종료가능하다..!!


(참고로 이 문제는 knapsack와 유사한 DP다)


bool canfind(vector<int> & data, int curr, int total, int sum){

if(total>sum) return false;

if(total==sum) return true;

bool ret = canfind(data,curr+1,total,sum+data[curr]);

return ret | canfind(data,curr+1,total,sum);

}


... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아 진짜 DP 너무 좋아..

재귀DP짱짱

시간복잡도 : O(MN) maximum cap to total sum

사실 모든 int에 대해 counting sort를 하면 O(N) 아니냐 하는 것 만큼이나 눈가리고 아웅이긴 한데 ㅋㅋ;;;
사실 2^N 이 MN보다 작을 가능성도 충분하다. 아 그래도, 하드캡이 2^N 인지라 이것보다는 무조건 빠르다. 캐싱이 추가된거기 때문에 최악의 경우가 재귀가 된다. 적어도 조금은 낫다!!

Programming Problems/Dynamic Programming

배열 원소간 모든 차이값을 주어진 값 이하로 맞추는 최소 변환 수

차이값을 주어진 값 이하로 맞추면서, 원래 배열에서 최소 한도로 움직이도록 해야 한다. 그 바꾼 값을 반환하자.


ex )

[1,4,2,3]

target = 1;

>> 

ans :

[2,3,2,3]

바꾼 양 : 2  >>> ans = 2



** 솔직히 이 문제는 "최적 값을 구하시오" 그리고 "숫자 상한이 100이다" 에서 - 아 이 문제는 DP구나 가 바로 떠올라서 완전 탐색으로 넘어갈 생각을 했어야 한다. 뭐 그리디 한두번은 해볼 수 있었겠지만 안정적으로 DP를 해놓고 찾았을꺼다. **


솔루션 : 


그리디 솔루션 :


한쪽 끝에서부터 생각해 보자. 한도 내로 맞추기 위해서 1을 움직일까 4를 움직일까?

아님 중간으로 맞출까?

일단 움직이는 총량은 같다. 어찌됬든, 차이를 그렇게 만들어야 하기 때문.


그럼 그 다음 값이 무엇이냐에 따라 결정되겠다.

만약 1,4,5 였으면 3,4,5 로 바꾸는 것이 최선이고(4를 내리면 5를 내려야 한다. 5 뒤에 어떤 값이 있다고 할때)


1 4 5 3


3 4 5 4


1 4 100 1 1 1 1 1 1


최적화는 방법이 조금 복잡할 수 있어서 다른 방법이 있을까?


아니면 꼬리치는 용같은 방식으로 그냥 각자의 최소를 가져다 댄다.

1 4 2 3

3 4 2 3

2 3 2 3 >> 그리고 차이값을 계산한다.


1 4 100 1 1 1 1 1 1

3 4 100

98 99 100 1


//


아니면 전체의 평균에서 출발해 볼까? 거시적으로 보는거야.


1 4 5 3 >> 평균 13/4 = 3.xxx


3 3 3 3 >> 그리고 여기에서 각자 더 작은애는 작은쪽으로 큰애는 큰쪽으로 암튼 전후로 최소 움직임을 찾아보는거야.


별로 아닌듯.. 불연속적인 차이값들 구성이 가능해서


// 아니면 극단적인 값부터 배치 ? .. 노


DP 방법이 있는 것 같다.

curr 뒤에의 값을 맞춘 최솟값을 m 이라고 하면

지금 값을 뒤에의 값들과 맞추는 비용 k와

뒤에의 값들을 평행이동 해서 앞의 값과 맞추는 비용 l 중 작은 경우로 결정한다.

평행이동이 아니라, 왼쪽 끝을 움직이고 나머지가 조건에 맞도록 하는 비용이 되겠다..

리턴받는 값을 제일 왼쪽의 숫자 + 횟수로 하고.


그러면 평행이동을 하는 것이 그 이후의 최솟값임이 보장되나?


1 4 2 3


2 3, 0

4


" 지금 이 점을 이 값으로 fix 하고 다음을 정했을 때의 최솟값 "


curr 부터 끝까지 배치하는 최소 수, curr의 값을 반환받아 보자.


3 99 100 99


3을 상방 배치하는 경우 95

나머지를 하방 배치하는 경우 매우 큼

>>

98 99 100 99, 값 : 95+그거


------------------


그리디 아님 DP 문제다!! 한번 더 고민해 보자.


겁나 어렵네 ;;


역시 iterative DP 문제였음.. 내 약한 부분..


아 근데 값의 상한이 100이라는 점을 안 썼네;;

값의 상한이 100이라는 점은 "카운팅 소트" 를 한다 라는 생각도 있겠지만

"값에 대해 DP를 돌려버린다" 도 가능하다 ㅋㅋㅋ

일단 창의적인 솔루션도 좋은데 DP를 간단하게 먼저 생각해 보는게 좋겠다. DP는 시스테매틱하니까..!!


----------------


내 약한 부분이 아니라 접근 방법이 전문적이지 못했다.


1. 바로 보이는 접근(답을 아는 경우나 정말 간단히 답이 보이는 경우)

2. 나이브 솔루션이라도 하나 굳힌다. 정말 개노가다 방법이어도 좋다. 여기서 출발한다.

3. 성질을 연구해서 DP로 줄이거나 그리디 솔루션을 찾는다.

-----------------


그리디는 답이 없는게 확실해졌고 결국 DP 문제였음.. 최적화기도 하니까 최적화 보이면 아 DP겠구나.. 생각해야겠다


값의 상한이 100이기 때문에, MAX 를 DP에 넣어서 풀어도 충분하다.


dp >> curr을 j로 바꿨을때 최솟값


값의 상한이 100이기 때문에 그냥 때려박아서 풀어도 된다.


즉,


1 4 2 3 이면 1을 0에서 100까지 전부 해버리는거다.


아, 결국 이런 완전탐색이었구나!!


헐........... 값의 범위가 있어버리면 이거를 완전탐색 해버리는거다. 그리고 DP를 하는거지


깨닳음


int findmin(vector<vector<int>> & cache, vector<int> & data, int K, int curr, int prev){

if(curr==data.size()) return 0;

if(cache[prev][curr]!=-1) return cache[prev][curr];

int ret = INT_MAX;

for(int i = 0 ; i <= 100 ; i++){

if(abs(i-prev)<=K){

ret = min(ret,findmin(data,curr+1,i)+abs(i-prev));

}

}

cache[prev][curr] = ret;

return ret;

}


결론 : DP는 결국에 고상한 척 하는 노가다다. 그것도 아주 많은 갈래로 쪼개지는 노가다를 단지 그 "쪼개짐의 값의 범위" 로 상한을 정해놓았을  뿐..


아 진짜 그러네 결국에 완전탐색인데 완전탐색중에 "쪼개짐의 값의 범위" 가 제약되어 있는 경우에 그 쪼개짐의 값의 범위에 대해 상한이 정해지는 것 뿐이네. 결국에는 O(5^N) 이딴 알고리즘인데.


만약 인자가 두개 뿐이어도 그 인자 하나가 1억의 범위를 가져버리면 DP고 뭐고(가능은 하다..) 심지어 안 겹치면 정말..!!


DP의 성질

* 겹쳐야 빨라진다.

* 범위가 좁아야 상한의 의미가 있다


암튼 저거의 시간 복잡도는 O(MAX^2 * N) 이다 ( 각 재귀함수에서 MAX 회 수행시간 )


이게 1억이었어봐 ..


숫자의 범위는 카운팅 소트 뿐이 아니라 DP에서도 매우매우매우 !!! 중요하다 !!