동적 프로그래밍 (dynamic programming)

 

하위의 작은 문제들을 풀고, 이를 이용해 더 큰 문제를 풀어나가는 방식.
격자(grid)로부터 시작한다.

  • 어떤 제한 조건이 주어졌을 때 무언가를 최적화하는 경우에 유용하다.

  • 하위 문제가 서로 의존하지 않는 경우에만 사용할 수 있다.

  • 모든 동적 프로그래밍의 답안에는 격자가 있다.

  • 격자의 각 칸에는 최적화하고자 하는 값을 적는다. (배낭문제의 경우 모든 물건의 총 가치)

  • 각 칸은 원래 문제에 대한 하위 문제이고, 다른 문제를 하위 문제로 가질 수 있다. 그러므로 원래의 문제를 어떻게 하위 문제로 나눌 수 있을지 생각해야 한다. 그렇게 하면 격자의 각각의 축이 어떻게 되어야 하는지 알아내는데 도움이 된다.

  • 해답을 계산해 주는 쉬운 공식이 존재하지 않는다.

 

최장 공통 부분 문자열

격자 만들기

  • 각 칸에 넣을 숫자는 무엇인가
  • 문제를 어떻게 하위 문제로 나눌 수 있는가
  • 격자의 축은 무엇인가

동적 프로그래밍에서는 무언가를 최대화 하는 것이 목표이다.

두 단어에서 공통적으로 가지는 가장 긴 부분 문자열, 즉 최장 공통 부분 문자열(LCS : longest common substring)을 찾는 경우

//hish와 fish의 최장 공통 부분 문자열을 찾는 경우 격자.

//단어를 직접 비교하는 대신에 his와 fis라는 단어를 먼저 비교한다.
//각 칸에 이 두 단어의 최장 공통 부분 문자열의 길이를 쓴다. 
//그러면 각각의 축이 그 두 단어를 의미함을 알 수 있다.
//격자는 아래와 같아진다.


      H     I     S     H
    ┌────┐┌────┐┌────┐┌────┐
 F  │ 0  ││ 0  ││ 0  ││ 0  │
    └────┘└────┘└────┘└────┘
    ┌────┐┌────┐┌────┐┌────┐
 i  │ 0  ││ 1  ││ 0  ││ 0  │
    └────┘└────┘└────┘└────┘
    ┌────┐┌────┐┌────┐┌────┐
 s  │ 0  ││ 0  ││ 2  ││ 0  │
    └────┘└────┘└────┘└────┘
    ┌────┐┌────┐┌────┐┌────┐
 h  │ 1  ││ 0  ││ 0  ││ 3  │
    └────┘└────┘└────┘└────┘

//각 칸을 채우기 위한 공식은 아래와 같다.
1. 만약 글자가 다르면 값은 '0' 이다.
2. 만약 글자가 같으면 값은 '좌측 상단 칸의 값+1'이 된다.

구현

if word_a[i] == word_b[j]:  # 글자가 같은 경우
    cell[i][j] = cell[i-1][j-1]+1
else :                      # 글자가 다른 경우
    cell[i][j] = 0

 

최장 공통 부분열(longest common subsequence)

두 단어에서 순서가 바뀌지 않고 공통으로 들어간 개수를 최대화 하는 경우

 

격자 만들기

//fosh와 fish의 최장 공통 부분열을 찾는 경우


      F     O     S     H
    ┌────┐┌────┐┌────┐┌────┐
 F  │ 1  ││ 1  ││ 1  ││ 1  │
    └────┘└────┘└────┘└────┘
    ┌────┐┌────┐┌────┐┌────┐
 I  │ 1  ││ 1  ││ 1  ││ 1  │
    └────┘└────┘└────┘└────┘
    ┌────┐┌────┐┌────┐┌────┐
 S  │ 1  ││ 1  ││ 2  ││ 2  │
    └────┘└────┘└────┘└────┘
    ┌────┐┌────┐┌────┐┌────┐
 H  │ 1  ││ 1  ││ 2  ││ 3  │
    └────┘└────┘└────┘└────┘

최장 공통 부분열 = 3

위쪽 칸과 왼쪽 칸 중에서
1. 만약 글자가 같지 않으면 둘 중 더 큰 값을 선택 (최장 공통 부분 문자열 문제와 다른점)
2. 만약 글자가 같으면 이 값은 '좌측 상단 칸의 값+1'이다

구현

if word_a[i] == word_b[j]:  # 글자가 같은 경우
    cell[i][j] = cell[i-1][j-1]+1
else :                      # 글자가 다른 경우
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

 

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘