암기는 제공된 입력에 대한 결과의 기록을 유지함으로써 메소드가 동일한 입력 세트에 대해 두 번 이상 실행되지 않도록 함으로써 재귀 알고리즘의 성능을 향상시키는 데 사용되는 동적 프로그래밍에 기반한 기술입니다. 배열). 재귀적 방식의 하향식 접근 방식을 구현하여 암기를 달성할 수 있습니다.
기본적인 피보나치 예제를 통해 이 시나리오를 이해합시다.
1차원 암기
우리는 상수가 아닌 매개변수가 하나만 있는 재귀 알고리즘을 고려할 것이므로(하나의 매개변수만 값을 변경함) 이 방법을 1차원 기억이라고 합니다. 다음 코드는 피보나치 수열에서 N'번째(N까지의 모든 항)를 찾는 코드입니다.
예시
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("Calculating fibonacci number for: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
} 출력
위의 코드를 n=5로 실행하면 다음 출력이 생성됩니다.
Calculating fibonacci number for: 5 Calculating fibonacci number for: 4 Calculating fibonacci number for: 3 Calculating fibonacci number for: 2 Calculating fibonacci number for: 2 Calculating fibonacci number for: 3 Calculating fibonacci number for: 2
n=5에 대한 피보나치 값:5
2와 3에 대한 피보나치 수는 한 번 이상 계산됩니다. 위의 조건, 즉 n=5인 피보나치 수열에 대한 재귀 트리를 그려서 더 잘 이해합시다.
여기서 node의 두 자식은 그것이 만드는 재귀 호출을 나타냅니다. 보시다시피 F(3) 및 F(2)는 두 번 이상 계산되며 각 단계 후에 결과를 캐싱하여 피할 수 있습니다.
결과를 캐싱하기 위해 인스턴스 변수 memoize Set를 사용할 것입니다. n이 이미 memoize Set에 있는지 확인하고, 그렇다면 값이 반환되고, 그렇지 않으면 값이 계산되어 집합에 추가됩니다.
예시
import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
private Map<Integer, Integer> memoizeSet = new HashMap<>(); // O(1)
public int fibMemoize(int input) {
if (input == 0)
return 0;
if (input == 1)
return 1;
if (this.memoizeSet.containsKey(input)) {
System.out.println("Getting value from computed result for " + input);
return this.memoizeSet.get(input);
}
int result = fibMemoize(input - 1) + fibMemoize(input - 2);
System.out.println("Putting result in cache for " + input);
this.memoizeSet.put(input, result);
return result;
}
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("Calculating fibonacci number for: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}
public static void main(String[] args) {
TutorialPoint tutorialPoint = new TutorialPoint();
System.out.println("Fibonacci value for n=5: " + tutorialPoint.fibMemoize(5));
}
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Adding result in memoizeSet for 2 Adding result in memoizeSet for 3 Getting value from computed result for 2 Adding result in memoizeSet for 4 Getting value from computed result for 3 Adding result in memoizeSet for 5
n=5에 대한 피보나치 값:5
보시다시피 2와 3에 대한 피보나치 수는 다시 계산되지 않습니다. 여기에서는 입력에 대해 값이 계산되고 그렇지 않은 경우 특정 입력에 대한 값이 집합에 추가되는 경우 모든 피보나치 계산이 집합에서 확인되기 전에 이미 계산된 값을 저장하기 위해 HashMap을 도입합니다.
2차원 암기
위의 프로그램에는 상수가 아닌 매개변수가 하나만 있었습니다. 아래 프로그램에서 우리는 재귀 호출마다 값을 변경하는 두 개의 매개변수가 있는 재귀 프로그램의 예를 살펴보고 이를 최적화하기 위해 두 개의 상수가 아닌 매개변수에 대한 기억을 구현할 것입니다. 이것을 2차원 암기라고 합니다.
예:-표준 Longest Common Subsequence(LCS)를 구현할 것입니다. . 시퀀스 세트가 주어지면, 가장 긴 공통 부분 시퀀스 문제는 최대 길이의 모든 시퀀스의 공통 부분 시퀀스를 찾는 것입니다. 가능한 조합은 2n입니다.
예시
class TP {
static int computeMax(int a, int b) {
return (a > b) ? a : b;
}
static int longestComSs(String X, String Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + longestComSs(X, Y, m - 1, n - 1);
else
return computeMax(longestComSs(X, Y, m, n - 1), longestComSs(X, Y, m - 1, n));
}
public static void main(String[] args) {
String word_1 = "AGGTAB";
String word_2 = "GXTXAYB";
System.out.print("Length of LCS is " + longestComSs(word_1, word_2, word_1.length(),word_2.length()));
}
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Length of LCS is 4
위의 중간 재귀 트리에서 lcs("AXY", "AYZ")는 두 번 이상 해결되었습니다.
이 문제의 Overlapping Substructure 속성의 결과로 Memorization 또는 Tabulation을 사용하여 동일한 하위 문제의 사전 계산을 피할 수 있습니다.
재귀 코드의 암기 방식은 다음과 같이 구현됩니다.
예시
import java.io.*;
import java.lang.*;
class testClass {
final static int maxSize = 1000;
public static int arr[][] = new int[maxSize][maxSize];
public static int calculatelcs(String str_1, String str_2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (arr[m - 1][n - 1] != -1)
return arr[m - 1][n - 1];
if (str_1.charAt(m - 1) == str_2.charAt(n - 1)) {
arr[m - 1][n - 1] = 1 + calculatelcs(str_1, str_2, m - 1, n - 1);
return arr[m - 1][n - 1];
}
else {
int a = calculatelcs(str_1, str_2, m, n - 1);
int b = calculatelcs(str_1, str_2, m - 1, n);
int max = (a > b) ? a : b;
arr[m - 1][n - 1] = max;
return arr[m - 1][n - 1];
}
}
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
arr[i][j] = -1;
}
}
String str_1 = "AGGTAB";
String str_2 = "GXTXAYB";
System.out.println("Length of LCS is " + calculatelcs(str_1, str_2, str_1.length(),str_2.length()));
}
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Length of LCS is 4
접근
메서드(calculatelcs)에는 2개의 상수(암기에 영향을 미치지 않음)와 2개의 상수가 아닌 인수가 있는 4개의 인수가 있는 것으로 나타났습니다. (m 및 n) 모든 재귀 메서드 호출에서 값을 변경합니다. 따라서 암기를 달성하기 위해 arr[m-1][n-1]에 lcs(m,n)의 계산된 값을 저장하는 2차원 배열을 도입합니다. lcs(m, n)의 이전 계산이 이미 완료되었으므로 동일한 인수 m 및 n을 가진 함수가 다시 호출될 때마다 더 이상 재귀 호출을 수행하지 않고 arr[m-1][n-1]을 반환합니다. arr[m-1][n-1]에 저장되어 재귀 호출 횟수를 최소화합니다.
3차원 암기
이것은 3개의 상수가 아닌 인수를 갖는 재귀 프로그램에 대한 암기를 달성하기 위한 접근 방식입니다. 여기에서는 3개의 문자열에 대한 LCS의 길이를 계산하는 예를 들어보겠습니다.
여기서 접근 방식은 주어진 문자열에 대해 가능한 모든 하위 시퀀스(가능한 전체 하위 시퀀스는 3ⁿ임)를 생성하고 그 중에서 가장 긴 공통 하위 시퀀스와 일치시키는 것입니다.
우리는 계산된 값을 저장하기 위해 3차원 테이블을 도입할 것입니다. 하위 시퀀스를 고려합니다.
-
A1[1...i] 나는
-
A2[1...j] j
-
A3[1...k] k
공통 문자(X[i]==Y[j]==Z[k])를 찾으면 나머지 문자를 반복해야 합니다. 그렇지 않으면 다음 경우의 최대값을 계산합니다.
-
X[i]가 다른 사용자를 위해 반복되도록 둡니다.
-
다른 사용자를 위해 Y[j] 반복 실행
-
다른 사용자를 위해 Z[k] 반복 실행
따라서 위의 아이디어를 재귀 함수에 공식화하면
f(N,M,K)={1+f(N-1,M-1,K-1)if (X[N]==Y[M]==Z[K]최대(f(N- 1,M,K),f(N,M-1,K),f(N,M,K-1))}
-
f(N-1,M,K) =X[i]가 다른 사용자를 위해 반복되도록 둡니다.
-
f(N,M-1,K) =다른 사용자를 위해 Y[j] 반복 실행
-
f(N,M,K-1) =Z[k]가 다른 사용자를 위해 반복되도록 둡니다.
예시
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
class testClass {
public static int[][][] arr = new int[100][100][100];
static int calculatelcs(String str_1, String str_2, String str_3, int m, int n, int o) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
arr[i][j][0] = 0;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= o; j++) {
arr[0][i][j] = 0;
}
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= o; j++) {
arr[i][0][j] = 0;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= o; k++) {
if (str_1.charAt(i - 1) == str_2.charAt(j-1) && str_2.charAt(j1) == str_3.charAt(k-1)) {
arr[i][j][k] = 1 + arr[i - 1][j - 1][k - 1];
}
else {
arr[i][j][k] = calculateMax(arr[i - 1][j][k], arr[i][j - 1][k], arr[i][j][k - 1]);
}
}
}
}
return arr[m][n][o];
}
static int calculateMax(int a, int b, int c) {
if (a > b && a > c)
return a;
if (b > c)
return b;
return c;
}
public static void main(String[] args) {
String str_1 = "clued";
String str_2 = "clueless";
String str_3 = "xcxclueing";
int m = str_1.length();
int n = str_2.length();
int o = str_3.length();
System.out.print("Length of LCS is " + calculatelcs(str_1, str_2, str_3, m, n, o));
}
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Length of LCS is 4