[알고리즘] DP 알고리즘 (& 재귀함수)

DP 알고리즘

• 접근 방식에 가까운 알고리즘임❨쓰이는 상황이 구체적이지 않음❩
• 복잡한 문제를 간단한여러 개의 문제로 나눠 푸는 기법임
• 메모이제이션 기법을 활용 -> 중복 계산을 줄임
  • 메모이제이션: 동일한 계산을 반복해야하는 경우, 한 번 계산한 결과를 저장했다가 다시 씀
  • 메모이제이션 기법을 활용하기 위해 값을 저장하는 공간을 DP table이라고 함
  • DP table은 문제의 재귀적인 구조에 따라 1차원 배열, 2차원 배열 또는 그래프, 트리 등으로 다양한 형태를 가질 수 있음

• 문제의 재귀적인 구조❨관계식❩을 찾는 것이 중요함

 

문제 풀 때 접근법

• 문제의 재귀적인 구조 파악 
• 수식으로 표현
• 초기값 처리

 

실제 문제에서 DP 알고리즘

• 실제 DP를 적용할 수 있는지 판단할 때 중요한 것은 문제의 재귀적인 구조(관계식)을 파악하는 것
• 재귀적 구조를 확인했으면 수식으로 표현, 초기값 처리 등을 진행하면 됨
  
  
• If, 문제의 재귀적 구조를 파악할 수 없다면
• 그 문제는 DP 알고리즘 문제가 아니거나, 문제를 재해석해서 재귀적 구조를 찾아햐 하는 문제임
  
  
• 브루트포스 → 그리디 → DP 순으로 접근해보셈

 

DP 알고리즘 구현 방법

• 재귀적인 구조를 찾고, 찾은 구조에 걸맞는 DP Table을 완성.
• DP table은 Bottom-Up 방식이나 Top-Down 방식을 사용함.
  • Bottom-Up: 작은 부분부터 완성, 보통 반복문 이용 → DP table 전체를 완성해야 하는 경우
  • Top-Down: 큰 부분(구하고자 하는 값)을 기준으로 필요한 부분만 구함, 재귀함수 이용 → DP table을 일부만 완성해도 되는 경우

 

Tip! 재귀함수

• 구조
  • Base case(기본 케이스): 재귀 함수를 종료하는 부분
  • Recursive Case(재귀 케이스): 자기 자신을 호출하는 부분
    
    
• 종료하는 부분의 코드(Base Case)를 작성할 때는 Recursive Case의 마지막 부분이 어딘지를 생각해 볼 것