[알고리즘] Dynamic Programming(동적 계획법)

⛈️ 메모이제이션이란?

 

 

**메모이제이션(Memoization)**은 동적 프로그래밍의 기법 중 하나로, 이미 계산한 결과를 저장해두고, 같은 계산을 다시 하지 않도록 하는 방법입니다. 이렇게 하면 불필요한 계산을 줄여 성능을 향상시킬 수 있습니다.

 

 

⛈️ 메모이제이션을 적용한 동적 프로그래밍의 단계

 

1. 답을 기록할 배열 정의

• 메모이제이션을 위해 문제의 특성에 맞는 배열을 정의합니다. 배열의 크기와 초기화 방법은 문제의 점화식과 조건에 따라 달라집니다.
• 예를 들어, 피보나치 수열의 경우 int[] memo 배열을 정의하고, memo[i]가 피보나치 수 F(i)를 저장하도록 합니다.

 

2.재귀 함수와 메모이제이션 적용

• 기본 사례(Base Case): 문제를 더 이상 나눌 수 없는 상태에서 반환할 값입니다. 이 값은 메모이제이션 배열에 직접 저장되지 않을 수 있습니다.
• 메모이제이션 체크  : 재귀 호출 시, 메모이제이션 배열에서 이미 계산된 결과가 있는지 확인합니다. 저장된 결과가 있으면 그것을 반환합니다.
• 결과 저장: 하위 문제를 계산한 후, 그 결과를 메모이제이션 배열에 저장합니다.

 

3.종료 조건 추가

• 유효하지 않은 인덱스나 기본 사례를 처리하여 잘못된 접근을 방지합니다. 예를 들어, 배열의 범위를 벗어난 인덱스 접근을 방지하거나, 음수 인덱스를 처리합니다.

---

 

 

 

예를 들어 :: 문제: 피보나치 수열

피보나치 수열은 다음과 같은 규칙을 따릅니다:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n > 1)

 

메모이제이션 적용

1. 결과 저장: 피보나치 수를 계산할 때, 이미 계산된 값을 저장해두고 나중에 필요할 때 이 값을 사용합니다.
2. 계산 재사용: 같은 피보나치 수를 여러 번 계산하지 않고, 저장된 결과를 참조합니다.

출처: 취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편

 

 

요약

• 문제를 더 작은 하위 문제로 나눕니다.
• 하위 문제의 결과를 저장해두고 재사용합니다.
• 중복 계산을 피하여 성능을 향상시킵니다.