Dynamic Programming

  divide-and-conquer은 서로 상관관계가 없는 문제를 해결하는데 적합하다.

반면, dynamic programming은 서로 상관관계가 있는 문제를 해결하는데에 적합하다. 

 

dp[i][j] --> 개의 보석을 만큼의 한도의 가방에 넣었을 때 보석의 가치 

 

 보석 1개를 넣었을 때 보석의 무게가 100, 가치가 1000이라 했을 때

 

dp[1][100]=1000

 

dp[[i][j]=max(dp[i-1][j],  

 

LIS 최장 증가 부분 수열 11053

카드 구매하기 11052

포도주 시식 2156

--> 일반항만 생각하면 되는 것이 아니고 한 단계 더 생각해야 한다.

 

1074  Z

 분할과 정복은 문제 자체로 나오기보다는 수단으로 나온다.  

  4등분하고 Z 형태의 순서로 방문하는 것은 크기와 상관없이 항상 적용되는 패턴이다.

  좌표가 어느 사분면에 해당하는지 먼저 알아내야 한다. 배열을 4등분한 후에, 재귀적으로 순서대로 방문한다. 

 탐색을 했다는 것을 어떻게 코딩적으로 표현할 것인가. 

 

모*싸인 코테를 보다가 느낀 것이 x,y 0 start idx 이런 것들이 은근 구현에 있어서 짜증나게 신경 많이 써야 하는 부분임.

 

solvle 함수 안에서 로직이 끝나는 부분도 포함. 

문제를 보고 bottom up이 아닌 top down식으로 풀면 해결책이 있으리라는 것이 보이고, 

void solve( int x,int y, int n){

   if (x==r && y==c){

      cout<<ans <<'\n';

   }

   if( r< x+n && r>=x && c <y+n && c>=y){

      solve(x,y,n/2);

      solve(

   

divide-and-conquer를 사용하는 대표적인 알고리즘으로는 binary search, merge sort, quick sort, matrix multiplication 등이 있다. 

이진탐색, 합병 정렬 등이 코딩테스트의 주제로 따로 출제되지는 않더라도 반드시 알아야 하는 테마라고 생각한다!