탐색 알고리즘2 (이분탐색, DP)

탐색

 

DP(Dynamic Programming, 동적 계획법)

 

겹치는 결과를 별도의 메모리 영역에 저장해서 한번만 계산하고 재사용하도록 한다 

 

DP 공식 

f(n) = f(n-1) + f(n-2)

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

DP의 조건

1. 최적 부분 구조(Optimal Substructure)
   • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem)
   • 부분 문제가 중첩 돼서 여러번 등장
   • 동일한 작은 문제를 반복적으로 해결해야 한다.

 

** 메모이제이션 **

• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  
  • 값을 기록해 놓는다는 점에서 캐싱이라고도 한다
  • 한 번 계산된 결과를 담아 놓기만 하고 활용하지 않을 수도 있다
  • 재귀를 이용하기 때문에 필요 없는 계산은 안해도 된다 
  • 재귀를 사용하므로 스택 오버플로우 문제가 발생할 수 있다

 

** 타뷸레이션 **

• 문제를 부분 문제로 나눈 다음 작은 문제부터 최종까지 그 결과를 차례대로 계산하는 기법
  • 모두 계산하기 때문에 필요없는 계산을 해야 수 있다.
  • 메모이제이션은 필요할 때 계산한다면 타뷸레이션은 미리 계산해둔다.

 

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요합니다.
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있습니다.
  • 다른 알고리즘으로 풀이 방법이 떠오르지 않으면(시간복잡도가 너무 크면) 다이나믹 프로그래밍을 고려합니다.
  • 다이나믹 프로그래밍의 조건을 만족하는 지 확인합니다.
• 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있습니다.

 

 

*** 계속해서 업데이트 중입니다 ***