DP 활용

편집 거리 문제

• 삽입 ,삭제 ,대체 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수
• strong -> stone
  
  

< DP를 이용하여 해결 >

• DP의 일반항, E[i,j] = S의 처음 i개 문자를 T의 처음 j개 문자로 바꾸는데 필요한 편집 거리
• stro -> sto로 바꾸기 위한 편집거리는 E[4,3]이다.
• 매순간 삽입, 대체, 삭제 총 3가지 연산의 경우의 수가 있다.
  
  
  -> E[4,3]=3가지 경우의 Min값이다.

-> E[i,j]에 대한 일반항을 도출할 수 있다.

E[i,j]=min{E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1]+a}
# 단, 대체에서 마지막 문자가 같다면 a=0, 다르다면 a=1

📒 DP는 일반항을 도출하고 일반항과 이전항의 관계 (= 점화식)를 구하는 것이 중요하다. 이때 점화식을 구하는 팁으로는 표를 그려 모든 경우의 수에 대한 값을 구해서 규칙을 찾아내거나, 매 순간 선택할 수 있는 경우의 수는 얼마나 되는지 생각하면 된다.

• 편집거리 문제의 초기값 설정은 위와 같이 설정해야 한다.
• 0개의 문자열에서 0개의 문자열로 가는 것은 0번의 편집연산

< 편집거리 문제 점화식 도출 >

for i=0 to m E[i,0]=i # 초기화
for j=0 to n E[0,j]=j # 초기화
for i=1 to m 
    for j=1 to n
        E[i,j]=min{E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1]+a}
return E[m,n]

막대기 자르기

• 가정 : 하나의 긴 막대기가 있고 막대기 조각마다 가격이 다르다. 막대기를 잘라 가장 높은 가격을 만들려면 어떻게 잘라야 할까
  
  -> 길이 4를 바로 파는 것보다 2로 잘라서 두개로 파는 것이 이득
  
  -> 일반항을 구하고 일반항을 통해 Rn에 대한 점화식을 구한다.

0/1 배낭 문제

• 문제 : 무게 제한이 50인 배낭에 다음 세 개의 물건을 넣을 때, 넣은 물건들의 가치 합이 최대가 되는 방법
  (단, 물건을 쪼개어 일부만 포함시킬 수 없다 = 0/1의 의미)
  
• 이전의 배낭 문제는 물건을 쪼개어서 넣을 수 있기 때문에 Greedy 알고리즘으로 해결 가능했다.
• 해당 문제를 Greedy 알고리즘으로 해결한다면 단위 무게당 가치순으로 채운다 = 무게 30, 가치 160
• 실제 최대값 = 무게 50, 가치 220

< DP를 활용 >

• m[i][w] : i개의 물건과 w 무게 제한으로 만들 수 있는 최대 가치
• m[0][w] = 0 for all w ,m[i][0] = 0 for all i
• i번째 물건 무게가 w보다 큰 경우 m[i][w]=m[i-1][w]
• 그렇지 않은 경우, m[i][w] = max(m[i-1][w], m[i-1][w-wi]+vi)
  -> i번째 물건을 선택한 경우와 선택하지 않은 경우의 최대 값을 선택

일반화된 거스름돈 문제

• 문제 : 주어진 n가지의 동전이 주어졌을 때 특정 돈을 만들수 있는 경우의 수는 몇가지 인가?
• ex) 만약 1c, 2c, 5c, 10c가 주어진 상황에 100c를 만들 수 있는 경우의 수는?
  -> 1k1 + 2k2 + 5k3 + 10k4 = 100 이라는 방정식이 도출된다

< DP를 활용 >

C(i,j) = i개의 동전을 가지고 j를 만들 수 있는 경우의 수
C(i,j) = C(i-1,j) + C(i-1,j-ai)

• i번째 동전을 선택하지 않는 경우 + i번째 동전을 선택하는 경우
• 동전의 경우의 수를 모두 구해야 하기 때문에 min값이나 max값을 구하지 않는다

위의 배낭문제도 일반화된 거스름돈 문제와 같이 해결이 가능하다.

• C(i,j) = True/False , i개로 j를 만들 수 있는지 없는지
• C(i,j) = C(i-1,j) OR C(i-1,j-ai)
• C(0,0) = 1