동적계획법

-1) 동적 계획법 개념

전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이를 활용하여 전체 문제를 해결하는 방법

동적 계획법을 효율적으로 활용하려면 아래 두 가지 조건을 만족해야

1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 함
   -> 중복 부분 문제

2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 함
   -> 최적 부분 구조

동적계획법의 핵심은 단순히 작은 문제를 조합해서 큰 문제를 해결하는게 아님 !
작은 문제들이 같아야 하고 반복되어야 함
큰 문제를 작은 문제들로 나눴지만 작은 문제들이 겹치지 않으면 효율적인 거 아님 x

점화식 세우기와 동적 계획법

동적 계획법으로 문제를 해결하는 절차는 아래와 같음

1. 문제를 해결하는 해가 이미 있다고 가정
2. 종료 조건을 설정
3. 과정 1,2를 활용해 점화식을 세움

** 그림을 그려서 식을 알아내 !

점화식 구현 : 재귀 활용
재귀는 재귀 함수의 반환값을 활용한다는 특징이 있음
재귀는 스택 메모리에 함수 호출 정보가 많이 쌓여 메모리 한계로 런타임 오류 생길 수 있음

문제가 생기면 쓸 수 있는 방법
1. 재귀 호출 자체를 쓰지 않는 반복문
2. 재귀 호출의 횟수를 줄이는 메모이제이션

재귀 호출의 횟수를 줄이는 메모이제이션
이미 계산한 값을 저장해두었다가 이후 쓸 일이 있을 때 활용하는 개념

점화식 구현 : 재귀 + 메모이제이션 활용

1. 메모이제이션을 위한 저장소 생성 : 이미 구한 해를 저장할 공간을 생성
2. 재귀 함수 정의 : 점화식을 재귀로 표현할 함수를 정의
   ( 이때 함수의 세부 구현은 고려하지 않음 )
3. 재귀 함수의 종료 조건을 정의
4. 재귀 함수의 일반 연산 처리 : 보통 동적 계획법에서는 점화식으로 나머지 문제를 처리, 그 과정에서 구한 결괏값은 메모이제이션 저장소에 저장

** 코딩테스트에서는 배열을 활용하여 메모이제이션하기를 추천 !

최장 증가 부분 수열 (Long Increasing Subsequence)

부분 수열이란?
주어진 수열 중 일부를 뽑아 새로 만든 수열
( 이때 각각의 원소는 전후 관계를 잘 유지해야 함 )

최장 증가 부분 수열이란?

부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열을 말함

• 숫자가 점점 증가함
• 원소 간의 전후 관계는 유지함
  -> 각 숫자로 끝나는 LIS 길이 중 최대값을 구하자

LIS의 길이 동적 계획법으로 구하기

점화식 :

• N은 현재 고려중인 인덱스, K는 N 이전에 올 수 있는 인덱스
• dp[N]=max(dp[K])+1 (단, K는 1<=K<N, arr[K]<arr[N])
• dp[1]=1 ( 종료조건 )

최장 공통 부분 수열 (Longest Common Subsequence)

부분 수열의 용어를 보고 단순히 '숫자의 나열'이라고 생각할 수 있지만
수학적인 의미로는 '특정 순서로 숫자를 나열한 것'

최장 공통 부분 수열이란?

두 수열이 어떤 기준에 따라 양쪽에서 공통으로 발견할 수 있는 가장 긴 부분 수열을 의미

부분 수열은 원소 사이의 순서만 유지하면 되고 반드시 연속할 필요는 없음

LCS 길이 찾는 방법?

1. 두 문자열의 길이가 1인 경우를 생각해보면 LCS의 문자의 값이 같은지에 따라 결정됨
   문자가 같으면 1 아니면 0
2. 문자열1의 첫번째~마지막 문자를 하나씩 짚어가면서 문자열2의 문자들과 모두 비교하여 같은 것이 있는지 확인

LCS의 길이 점화식 생각하기

• 두 문자열의 특정 문자가 같은지
• 같다면 찾은 두 문자의 위치가 이전에 찾은 문자의 다음에 있는지

1. LCS() 함수 정의
   LCS(i,j)=x[1...i]와 y[1...j]의 LCS의 길이

2. LCS(2,3)에서 +1을 하면 LSC(3,4) <- 단 새로 더하는 값이 같을 경우에 만족

3. 만약 새로 더하는 값이 다르다면 x[3]과 y[4]는 포함하지 않는 LCS의 길이를 찾아야 함
   즉 LCS(3,3) 혹은 LCS(2,4) 중에서 선택해야

x[i]와 y[j]가 다르면 LCS(i,j)=LCS(i-1,j)와 LCS(i,j-1)을 비교하여 큰 값으로 함

즉

• LCS(0,0)=0
• x[i]=y[j]이면 LCS(i-1,j-1)+1
• x[i]!=y[j]이면 max(LCS(i-1,j), LCS(i,j-1))