[TIL] 알고리즘 : 동적계획법 DP

어느덧 마지막 이론 .. 이주동안 수고한 나자신과 우리 모두에게 박수 ~ .. 넘 스트레스 많이 받고 했었는데 이제 끝이라니까 또 아쉽구 그르넹 역시 주어졌을때 최선을 다해 임해야 ㅎ ㅏ는것 ..

 

대망의 DP ! 시작 !

 

Chap 6. 동적 계획법

DP의 대략적인 두가지 방법

1. 재귀로 메모이제이션 Memoization
2. 반복문으로 타뷸레이션 Tabulation

 

1. 배낭 채우기 문제 (Knapsack Problem)

도둑이 N가지의 보석이 무한히 있는 가게에 들어와, 
W kg을 넣을 수 있는 배낭에 보석을 넣어 훔쳐갈 때, 
훔쳐가는 보석들의 가치의 합의 최대는 얼마이며, 
어떤 보석을 얼마나 가져가야 하는가?

Case 1. N<=10, W<= 100 인 경우
Case 2. N<=100, W<=10000 인 경우
Case 3. 각 N개의 보석이 1개씩만 있는 경우

1. 일번 케이스는 숫자가 매우 작아서 굳이 DP 할 필요없음. 완전탐색 or Greedy로 가능
2. 이번 케이스는 DP 사용하여 10000*100의 시간복잡도 내에서 탐색 가능
3. 알아야할 조건이 더 많음

• 보석을 쪼갤 수 없다면, Greedy로 접근시 가방에 빈 공간이 생길 수 있어서 비효율적일 수 있음
• 조합 탐색, 백트래킹으로 접근한다면 시간이 오래걸림

따라서 , DP로 !

대략적으로 무엇이 필요할까?

• 보석별 무게와 가치 정보 필요
• 현재 배낭에 채워진 무게를 인덱스로
• 현재 배낭에 채워진 보석의 가치 배열 D[i]
• 현재 사용된 보석이 무엇인지 나타낼 배열 p[i]

 

2. 부분 문제와 점화식

- 주어진 순열에서 i번째 숫자를 포함하는 연속된 구간의 최대 합

1. 수열에 음수가 없는 경우 : 그냥 전체 수열의 원소의 합이 정답

 

2. 수열에 음수가 있는 경우

• 주어진 수열 A[i]
• DP 캐시를 위한 D[i] : A[i]값을 포함하여, A[1] ~ A[i]까지 고려했을때 연속된 구간의 합의 최댓값
• D[i] = max ( D[i-1] + A[i] , A[i] )
• 의미 : 웬만하면 계속 쭉 더하되, D[i-1] 값이 음수라면 그냥 지금까지의 히스토리 다 버리고 새로 시작하는것이 유리하다
• 이렇게 끝까지 D[i]를 구한 후, D[1] ~ D[i] 중 제일 큰 값이 정답
• 점화식 : Di = max( Ai + Di-1 , Ai ) 

 

- 최대공약수를 최대로 접근하는 방법

: 길이가 N인 수열이 주어질때, 그 중 한개를 제외한 나머지 숫자들의 최대공약수가 최대가 되는 값을 구하기

• 한개를 뺀 나머지 숫자들에 대해, 빠지는 숫자를 기준으로 좌우측 구간에 대한 계산 결과값 활용
• 최대공약수는 유클리드 호제법을 이용해 계산

https://www.acmicpc.net/problem/14476

14476번: 최대공약수 하나 빼기

 

- 최장 증가 수열 LIS (Longest Increasing Subsequence)

• 수열 A[i]
• 임의의 지점 i에 대해, i 이전의 지점에서, i번째 값보다 작은 것 중 최대값을 취한다
• 점화식 : Di = max({Dk}) + 1
• 이진탐색 또는 인덱스드트리를 사용해 O(nlogn)의 시간복잡도까지 낮출수있움 (안쓰면 n^2임)

유사 : LCS

 

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

- 행렬 곱 접근법 (사선 DP, 구간 DP)

: N개의 행렬이 주어지고, 순서대로 곱셈을 한다고 할때, 곱셈 연산의 최솟값을 구하기

• 연산횟수 (AxB) = rA * cA * cB = rA * rB * cB (r: i번째 row의 크기, c: i번째 colum의 크기)
• 어떤 순서로 연산을 하든지, 크기가 r1 * cN인 행렬이 된다는 성질 이용
• 시간복잡도 O(a*N^3) : 0<a<1라 N^2와 유사한 정도까지 빨라질수있음
• 점화식 : 직접 쓰기 복잡 나중에 수기로 쓸랭

 

- 외판원 순회 TSP

• next i : 다음에 방문할 도시 숫자
• v : 현재 도시를 방문하기까지 이미 방문한 도시들의 비트마스크 값
• 점화식 : D[v][next i] = min( D[v에서 도시 i를 방문하지 않은 비트마스크 값][i] + W[i][next i] )
• 시간복잡도 ( 2^n ) * ( n^2 ) 
• 비트마스크 안쓰고 ~~ visited를 사용하면 시간복잡도 n! 임. 매우 허접

 

- 폐지 두 번 줍기 문제

 

넘 얼레벌레 끝냈낭 ㅎㅎ 무튼 고생했다 이제 문제풀자 !