Dynamic Programming

Dynamic Programming

• Dynamic Programming은 greedy algorithm과 마찬가지로 최적화 문제를 해결하는 알고리즘이다. 최적화 문제란 가능한 해들 중에서 가장 좋은(최대 또는 최소)해를 찾는 문제이다.

• 다이나믹 프로그래밍은 입력 크기가 작은 부분문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다. 이때 부분문제들은 다음 문제를 해결할 때 기록해두어 필요할 때 다시 이용하는 메모이제이션 기법을 이용한다.

Algorithm 문제풀이 팁

• 작은 문제부터 해결하기

• 문제에 주어진 조건을 잘 읽고 마지막에 조건을 붙이는 경우로 생각해보기, 이렇게 하면 메모이제이션을 생각하기가 조금 수월함 마지막 경우 앞에는 어떤 경우 였을까?로 생각해볼 수 있다. 일반화해서는 n일 경우 n-1은 어떻게 이용할까를 생각해볼 수 있다.

  • 예를 들면, 2n 타일링문제 에서는 1*2 타일을 마지막에 붙이는 경우 2*1 타일을 마지막에 붙이는 경우로 생각해보기
  • 계단 오르기 문제에서는 마지막에 1칸을 이동한 경우, 2칸을 이동한 경우로 생각해보기
  • 1m, 2m로 네트워크 선 자르기 문제에서는 마지막에 1m로 자르는 경우, 2m로 자르는 경우 생각해보기
  • 가장 긴 부분 증가 수열 문제에서는 각 수를 마지막에 붙이는 경우로 생각해보기

출처: 알기 쉬운 알고리즘(양성봉 지음)