DP를 정리해보자!

DP

원하는 값을 얻기위해 그 전의 값들을 완벽하게 구할 수 있고 그 값을 사용하는 정의가 깔끔하게 떨어져 있는 것

• 즉, 어떤 상태의 값을 저장하기 위한 별도의 배열과 초기값설정, 작은값과 큰 값사이의 점화식이 요구되는 알고리즘이다.
• 내 개인적으로는 문제를 풀때 이 문제가 DP 인지 아닌지 판별하기 어렵다.
  • 타일 문제 , 1로 만들기와 같이 대놓고 DP 문제도 있지만, 
  • 퇴사2와 같이 완전탐색이 먼저 떠오르는 문제도 존재했다.(처음에는 DP인지 추측도 못했다....)
  • 특히 퇴사2 는 아직도 점화식 도출 과정이 익숙해지지 않음.
  • 그래서 위와같은 경우처럼 입력값이 너무 커서 O(N)이내의 문제로 풀어야 하는 경우 DP를 의심해보는 편이다 
• DP배열에 저장하는 방식은 1차원 배열 , 2차원 배열 등 각각의 인덱스에 어떤 상태를 놓느냐에 따라 식이 달라진다.
• 작은 값을 쪼개서 얻고자 하는 최종 결과의 관계를 고민하자
• 각각의 상태에 나올 수 있는 결과값을 식으로 도출하는과정이 필요하다.

점화식이 여러 작은 합으로 되어있는 경우

• 타일링

배열 안에서 한 칸씩 탐색하는 경우

• 정수 삼각형
  • 아래나 오른쪽 대각선 아래로 최대 합
  • dp[i][j] 에서 아래 , 왼쪽 아래 2가지 경우 밖에 없음 그 중 선택하며

조건에 따라 선택적으로 합치는 경우

• 가장 긴 증가(감소)하는 부분수열

아이템(원하는 값을 얻기위한 최적 값)을 적절히 고르는 문제

• Knapsack

점화식의 나올 수 있는 형대가 다양하다....

DP 문제들

문제의 경우 풀면서 더 추가하자. (까먹으면 어쩔수 없지요~~)

 

출처 : https://stonejjun.tistory.com/24

ㄴ 정리가 잘 되어있다!

• 탑다운:큰 문제를 작은 문제로 쪼개서 푸는 것 , 바텀업:작은 문제를 큰문제로 합치는 것
• 점화식으로 내가 알고있는 정보를 쓰면 바텀업이고, 모르는 정보를 쓰면 탑다운이다.
• 바텀 업과 탑 다운 방식의 큰 차이는 바텀업은 전체를 다 구해야 하지만 , 모두를 구해야할 때 탑 다운 방식은 오히려 재귀함수로 구현하기 때문에 문제의 특성에 따라 메모리 소비차이가 각 방식에 따라 클 수 있다.

기본 문제

• 2×n 타일링 : 제일 DP 하면 떠오르는 기본 문제
• 1로 만들기 : DP의 기본222
• 계단 오르기 : 식에 대해 고민해보는 문제!

자주 풀어보자!

• Knapsack : dp[i][j] : i까지 보석을 고려하였을때 무게가 j인 상태에서 최대 가치 -> 무게와 가치 두 개를 고려해야하기 때문에 그리디로는 접근하기 어렵다!
• 가장 긴 증가하는 부분 수열 : DP문제로 유명하지만 자주 까먹는 문제.... (이해를 확실히 하자!)
  • dp[i] 에 저장 하는 것은 해당 인덱스가 가장 마지막 수열의 값으로 올경우 가능한 자리수
  • i의 전까지 값은 이미 확인을 했기 때문에 j 값이 i보다 작으면 그 dp값에 +1한 값의 수열 길이를 가지게 된다.
  • Max(dp[j]+1)의 값이 해당 dp[i]의 값이 된다.
• 퇴사2 : 내 애증의 문제… 구간에 대한 최소 비용과 최대 효율 둘다 고려해야하는 문제
  • 입력 값이 크기 때문에 완전탐색으로는 안됨. 시간복잡도는 O(N)으로 구해야할듯
  • 시간당 최대 수익을 구해야 함 그런데 상담마다 상담기간이 존재함
  • dp[i]는 해당 일차에 얻을 수 있는 최대수익이라하자
  • 1일에 상담기간이 3일이면 4일차부터는 1일차 ~ 3일차 까지 중 최대 수익이 모두 반영되어있어야하는거 아닌가? → 이 과정에서 for 문 안에서 조건 처리를 해야하나고민했지만 그러면 O(N^2)이 됨
  • 그럼 어떻게 O(N)으로 반영하는가?→ 딱 한 개의 DP배열의 값만 수정해야한다? 딱 그 상담 끝나는날의 수익을 수정한다면? 그러면 dp [상담 끝나는날] = dp[상담 시작날] + 그 그 일차의 값

          for(int i = 1; i <= N;i++){
              if(T[i] + i <= N+1){
                  D[i + T[i]] = Math.max(D[i]+P[i],D[i + T[i]]);
                  D[i] = D[i]+P[i];
              }
          }
  

  • 마지막 예제의 경우: 그 6일차와 8일차 사이의 7일차의 최댓값은 80 하지만 6일차 이후 바로 8일차를 하면 90으로 더 이득 → 그일차의 최댓값과는 별도의 그 일차 이전의 누적 최댓값을 저장할 필요가 있다.= dp[N]이 갱신될 수 없는 경우가 생기기 때문에 반복문을 돌 때마다 따로 정답의 최댓값을 기억하고 있어야 한다

int max = 0;
for(int i = 1; i <= N;i++){
	max = Math.max(max,D[i]);
	if(T[i] + i <= N+1){
		D[i] = Math.max(max + P[i],D[i]+P[i]);
		D[i + T[i]] = Math.max(D[i],D[i + T[i]]);
	}
}

 

결국 공부하다 느낀것.... ??둘 다 쪼개서 최종의 결과를 얻는 알고리즘인데 그리디랑 큰 차이가 뭐지?

차이가 있다는것은 알겠지만 구체적으로 무엇인지 아리송해서 의문이 들었다.

DP와 그리디의 차이점은?

• DP는 전체 문제를 작은 부분 문제로 나누어 해결하는 방식. 각 부분 문제의 최적해를 찾아 전체 문제의 최적해를 구한다.
• 그리디는 현재 상황에서 가장 좋아 보이는 선택을 하는 방식. 이는 전체 문제의 최적해를 보장하지 않지만, 빠른 시간 내에 근사치에 가까운 해를 구할 수 있다.
• 배낭 알고리즘(Knapsack)으로 그 차이를 볼 수 있음 : DP 알고리즘을 사용하면 최적해를 구할 수 있지만, 그리디 알고리즘을 사용하면 최적해를 보장하지 않는다.

-> 결국 DP는 쪼개진 문제들의 해 역시 퍼펙트해야한다는것 (like 퍼즐 맞추듯이) 그렇기에 전체가 깔끔해지는 과정을 찾아야한다.
그리디는 당장의 최적값을 고르는 것이기에 반례가 존재할 수 있다는것! 즉 얻고자 하는 과정의 관점이 확연히 다르다!