알고리즘 설계 기법 - 동적 프로그래밍 기법

알고리즘 설계 기법

동적 프로그래밍 기법 (Dynamic programming)

• 분할 정복 기법과 유사하게 부분 문제의 해답을 이용하는 방식으로 문제를 해결하는 방식
• 주어진 문제를 여러 개의 소문제로 분할하여 문제를 해결
• 상향식 설계기법
  • 작은 문제부터 먼저 해결한 후 그 결과를 큰 문제에서 활용함으로써 효율성을 높이는 방법

동적 프로그래밍 방식 적용 방법

• 분할 정복식 방법과 마찬가지로 문제를 나눈 후, 주어진 부분 문제들을 한 번 계산한 후에는 특정 장소에 저장
• 부분 문제의 해가 필요할 때 이를 다시 계산하지 않고, 이전에 저장해둔 결과를 이용
• 일반적으로 동적 프로그래밍에서 부분 문제의 값을 저장하는 장소는 배열 형태를 사용

피보나치 수열 계산 과정의 트리

• 중복 계산 발생
  • 다시 계산하지 않고 한번 계산한 값을 저장해 놓고 사용

분할 정복 기법 Vs. 동적 프로그래밍 기법

• 분할정복기법(하향식 설계 기법)
  • 분할되는 솜누제가 독립적이어서 소문제를 다시 재귀적으로 풀어 그 결과를 합한다.
  • 중복된 계산이 계속 발생
  • 중복문제를 방지하기 위해 동적 프로그래밍 기법 사용
• 동적 프로그래밍 기법(샹향식 설계 기법)
  • 부분 문제의 해답을 이용하는 방식으로 문제를 해결(분할 정복 기법과 동일)
  • 소문제의 계산 결과를 표(배열)에 저장해 놓고 필요할 때 저장된 값을 호출하여 사용
  • 따라서 중복 계산 제거

동적 프로그래밍 적용 대상

• 최적화 문제
• 최소치 또는 최대치를 구하는 최적화 문제에 적용
• 최적해는 기본적인 소문제의 최적해로부터 더 큰 크기의 소문제의 최적해를 구하는 과정을 거침
• 최적화 문제의 최적해는 여러 개가 있을 수 있지만 그 중의 하나를 구하면 됨

동적 프로그래밍 방법 적용 예

• 피보나치 수열
• 조약돌 놓기 문제
• 행렬 경로 문제
• 연쇄 행렬 곱셈
• 이항 계수
• 최단 경로 구하기

조약돌 놓기 문제

• 조약돌을 놓는 방법(제약조건)
• 각 열에는 적어도 하나의 조약돌을 놓아야 한다.
• 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다.
• 목표
  • 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌 놓기

행렬 경로 문제

• 양수 또는 음수 원소들로 구성된 N x N 행렬
• 행렬의 좌상단에서 시작하여 우하단까지 이동
• 이동 방법 (제약조건)
  • 오른쪽이나 아래쪽으로만 이동 가능
  • 왼쪽, 위쪽, 대각선 이동 불가
• 목표
  • 행렬의 좌상단에서 시작하여 우하단까지 이동되, 방문한 칸에 있는 수들을 더한 값이 최소가 되도록 한다.