동적 프로그래밍

동적 프로그래밍

• 동적 프로그래밍은 제한 조건이 있을 때에 무언가를 최적화하는 경우 유용하다. 예를 들어 들어갈 수 있는 크기가 제한된 배낭에서, 값어치가 최대가 되도록 물건을 채우는 ''배낭 채우기'' 문제 같은 것이 그것이다.

• 동적 프로그래밍은 하위 문제가 서로 의존하지 않는 경우에만 사용할 수 있다. 예를 들어 배낭에 넣을 물건 - 책, 거울, 노트북 등 - 의 가치는 다른 물건들과 관계가 없다.

• 모든 동적 프로그래밍 답안에는 격자가 있다. 격자의 각 칸에는 최적화하고자 하는 값을 적는다. 배낭 채우기 문제의 경우 물건의 가치를 적는다.

  cell[i][j]의 최대값은 // i는 행, j는 열
  1. 지금까지 구한 cell[i-1][j]의 값 중에서 가장 최대값이거나
  2. 현재 물건의 가치 + 남은 공간의 가치(cell[i-1][j-물건의 가치])
  

• 각 칸은 원래 문제에 대한 하위 문제이고, 다른 문제를 하위 문제로 가질 수 있다. 격자를 만들기 위해서는 다음의 질문에 답해야 한다.

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

• 최장 공통 부분 문자열(Longest Common Substring)

  • 어떤 사람이 인터넷에 ''hish'라 검색했을 때에 이 사람이 'fish'를 검색하려 한 것인지, 'vista'를 검색하려 한 것인지 어떻게 알아낼까?

  • 'hish'라는 단어와 공통으로 가지는 가장 긴 문자열을 찾는다. 이는 연속된 문자열을 의미한다.

  • 여기서 하위 문제는 부분 문자열을 비교하는 것이다. 그러므로 각 축은 비교하고자 하는 두 단어가 된다.

  • 의사코드로 나타내면 격자의 값은 다음과 같다.

    if word_a[i] == word_b[j]: // word_a, word_b는 비교하고자 하는 단어이며 i는 행, j는 열.
    	cell[i][j] = cell[i-1][j-1] + 1 // 격자의 대각선 위 방향의 cell 값에 1을 더함
    else:
    	cell[i][j] = 0 
    

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

  • 위의 최장 공통 부분 문자열은 연속된 공통 문자의 개수를 찾는다. 즉 'fosh'가 기준 단어일 때, 'fish'와 'hush' 모두 최장 공통 부분 문자열은 2개이다.('s', 'h') 그러나 'fish'의 경우 순서가 일치하는 글자의 개수가 3개('f', 's', 'h')이므로 기준단어와 더 유사하다고 할 수 있다. 이처럼 두 단어에서 순서가 바뀌지 않고 공통으로 들어간 글자 개수를 최대화하는 것이 최장 공통 부분열이다.

  • 의사코드로 나타내면 격자의 값은 다음과 같다.

    if word_a[i] == word_b[j]: 
    	cell[i][j] = cell[i-1][j-1] + 1 // 최장 공통 부분 문자열과 동일
    else:
    	cell[i][j] = max(cell[i][j-1], cell[i-1],[j]) // 최장 공통 부분 문자열과 다름