"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 15장의 써머리입니다."

15. 동적 계획법(Dynamic Programming)

1) 동적 계획법 개념

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


활용 조건

• 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 함
• 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 함
  
  

* 동적 계획법은 작은 문제들이 같아야 하고 반복되어야 함
 → 최적 부분 구조(Optimal Substructure) : 작은 문제의 해결책의 합으로 큰 문제를 해결할 수 있는 구조
 → 중복 부분 문제(Overlapping Subproblems) : 큰 문제를 나누었을 때 작은 문제가 여러 개 반복되는 문제

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

동적 계획법으로 문제 해결 절차

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

점화식 구현 : 재귀 활용

재귀 - 재귀 함수의 반환값을 활용한다는 특징이 있음

Fact(N):
	if (N이 1이면) 1 반환 # 종료 조건
	else Fact(N-1) * N 반환 # 일반

호출한 함수가 많으면 많을수록 스택 메모리에 함수 호출 정보가 많이 쌓임
→ 입력값이 크다면 메모리 한계로 런타임 오류 발생 가능
⇒ 재귀 호출 사용 전에 항상 메모리 한계에 대한 생각을 하고 이 문제가 발생하지 않도록 주의

재귀 호출해서 문제 발생 시 해결 방안

1. 재귀 호출 자체를 쓰지 않는 법 → 반복문
2. 재귀 호출의 횟수를 줄이는 법 → 메모이제이션
   
   

재귀 호출의 횟수를 줄여주는 메모이제이션

메모이제이션 : 이미 계산한 값을 저장해두었다가 이후 쓸 일이 있을 때 활용하는 개념
⇒ 함수의 결과를 메모이제이션해서 재귀 호출을 다시 하는 것이 아니라 메모이제이션을 활용해서 바로 계산

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

메모이제이션 조합

1. 메모이제이션을 위한 저장소 생성 : 이미 구한 해를 저장할 공간을 생성
2. 재귀 함수 정의 : 점화식을 재귀로 표현할 함수를 정의, 이때 함수의 세부 구현은 고려 X
3. 재귀 함수의 종료 조건을 정의 : eg) 피보나치 수의 첫 번째, 두 번째 수는 1로 정해져 있으므로 메모이제이션 저장소에 해를 미리 넣어두고 종료 조건으로 생각
4. 재귀 함수의 일반 연산 처리 : 보통 동적 계획법에서는 점화식으로 나머지 문제 처리, 그 과정에서 구한 결과값은 메모이제이션 저장소에 저장

fibodata[1...N] # 메모이제이션을 위한 배열 선언, 0으로 초기화
fibo(N) : (함수 정의)
	if(fibodata[N] != 0) fibodata[N] 반환 # 메모이제이션 활용
	if(N이 2 이하이면) fibodata[N]에 1 삽입 # 메모이제이션, 종료 조건
	else fibodata[N]에 fibo(N-1) + fibo(N-2) 삽입 # 메모이제이션, 일반항

fibodata[N] 반환

문제 해결 과정

• 점화식 작성(가정한다)
• 재귀 방식으로 풀어보기(반복한다)
• 동적 계획법으로 재귀 + 메모이제이션으로 구현(기억한다)

점화식으로 문제를 작은 문제로 나눠서 접근하는 과정 공부(최적 부분 구조)

메모이제이션으로 반복되는 작은 문제에 연산 횟수를 효율적으로 줄일 수 있음(중복 부분 문제)

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

부분 수열이란?

주어진 수열 중 일부를 뽑아 새로 만은 수열을 의미, 이때 각각의 원소는 전후 관계 유지

최장 증가 부분 수열이란?

부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열을 의미
eg) [1, 4, 2, 3, 1, 5, 7, 3] ⇒ [1, 2, 3, 5, 7]

최장 증가 부분 수열은 엄격하게 증가하는 오름차순이어야 함.
eg) [1, 1, 3, 5]는 같은 값이 존재하므로 LIS가 아님

LIS 특징

• 숫자가 점점 증가함
• 원소 간의 전후 관계는 유지함
  
  

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

전체 수열의 LIS 길이를 구하는 문제는 각 숫자로 끝나는 LIS 길이 중 최댓값을 구하는 문제로 바꾼 것임을 알 수 있음(최적 부분 구조), 각 숫자로 끝나는 LIS를 구할 때 이전 LIS 길이를 참조함

• dp[N] = arr[N]을 마지막 원소로 하는 LIS 길이

dp로 점화식을 세우면

• dp[N] = max(dp[K]) + 1(단, K는 1 ≤ K < N, arr[K] < arr[N]
• dp[1] = 1(종료 조건)
  
  

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

컴퓨터 과학에서는 수열의 의미를 좀 더 폭넓게 해석 → 특정 순서로 나열한 객체를 의미, 즉 객체는 문자, 숫자 등의 자료형이므로 컴퓨터 과학에서 부분 수열은 특정 순서로 객체를 나열한 것

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

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

LCS 길이 찾는 방법?

입력값을 작게 하여 반복하여 풀 수 있는 작은 문제가 나오는지에 집중

LCS의 길이 점화식 생각하기

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

LCS 길이 알고리즘 분석

총 연산 횟수는 dp를 채우는 것과 같으므로 O(N*M)

2) 몸 풀기 문제

문제 70) LCS 길이 계산하기

주어진 두 개의 문자열 str1과 str2에 대해 최장 공통 부분 수열의 길이를 계산하는 함수 구현

def solution(str1, str2):
  x = len(str1)
  y = len(str2)
  
  dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
  
  for i in range(1, x + 1):
    for j in range(1, y + 1):
      if str1[i - 1] == str2[j - 1]:
        dp[i][j] = dp[i - 1][j - 1] + 1
      else:
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  
  return dp[x][y]

assert solution("ABCBDAB", "BDCAB") == 4
assert solution("AGGTAB", "GXTXAYB") == 4

3) 합격자가 되는 모의 테스트

문제 73) 피보나치 수

2 이상의 n이 입력되었을 때 n 번째 피보나치 수를 1234567로 나눈 나머지를 반환하는 함수 구현

def solution(n):
    dp = [0, 1]
    
    for i in range(2, n + 1):
        dp.append((dp[i - 1] + dp[i - 2]) % 1234567)
    
    return dp[n]