다이나믹 프로그래밍과 분할 정복

다이나믹 프로그래밍

• 다이나믹 프로그래밍은 동적 계획법이라고 불리는 알고리즘
  • 입력 크기가 작은 부분 문제들을 해결한 후에
  • 해당 부분 문제의 결과값을 활용해서
  • 보다 큰 크기의 부분 문제를 해결하고
  • 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• Memoization 기법을 사용함.
  • 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 예로, 피보나치 수열이 있음.

분할 정복

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
  • 재귀함수
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
• 예로, 병합 정렬과 퀵 정렬이 있다.

공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할

차이점

• 동적 계획법은 부분 문제는 중복되어, 상위 문제 해결 시 재활용되는 반면에 분할 정복은 부분 문제는 서로 중복되지 않는다.
• 그렇기 때문에 memoization 기법은 동적 계획법에서만 사용된다.

다이나믹 프로그래밍 예제 문제

• [ ] 돌게임
• [ ] 점프
• [ ] 가장 긴 바이토닉 부분 수열
• [ ] 내리막 길
• [ ] 이동하기
• [ ] 전깃줄

분할 정복 예제 문제

• [ ] 쿼드트리
• [ ] 종이의 개수
• [ ] 색종이 만들기
• [ ] 별 찍기 - 11
• [ ] 히스토그램에서 가장 큰 직사각형
• [ ] 행렬 제곱
• [ ] 트리의 순회
• [ ] 히스토그램