728x90
메모이제이션(Memoization)
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법이다. 값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다.
피보나치 수열
메모제이션을 추가한 방법의 시간복잡도는 O(N)
이다.
static int[] fibo; // 피보나치 수열 값을 저장할 배열 선언
public int DFS(int n) {
if(fibo[n] > 0 ) return fibo[n]; // 메모이제이션 ✨
if (n < 2) return fibo[n] = n;
else
return fibo[n] = DFS(n - 1) + DFS(n - 2);
}

조합수
💡 nCr =n-1Cr-1 + n-1Cr
int[][] dy = new int[35][35]; // 조합수를 저장할 배열 선언
public int DFS(int n, int r) {
if (dy[n][r] > 0) return dy[n][r]; // 메모이제이션 ✨
if (n == r || r == 0) return 1;
else return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
}
728x90
'Algorithm > 알고리즘' 카테고리의 다른 글
[JAVA/자료구조] 스택(Stack)과 큐(Queue) (0) | 2023.10.16 |
---|---|
[JAVA] 이진트리 순회(DFS, BFS) (0) | 2023.09.17 |
[JAVA/알고리즘] 이진 탐색 알고리즘을 이용한 문제해결 (0) | 2023.09.12 |
[JAVA/알고리즘] 이진 탐색(Binary Search) (0) | 2023.08.15 |
[JAVA/알고리즘] 정렬 알고리즘의 종류 (0) | 2023.08.08 |
728x90
메모이제이션(Memoization)
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법이다. 값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다.
피보나치 수열
메모제이션을 추가한 방법의 시간복잡도는 O(N)
이다.
static int[] fibo; // 피보나치 수열 값을 저장할 배열 선언
public int DFS(int n) {
if(fibo[n] > 0 ) return fibo[n]; // 메모이제이션 ✨
if (n < 2) return fibo[n] = n;
else
return fibo[n] = DFS(n - 1) + DFS(n - 2);
}

조합수
💡 nCr =n-1Cr-1 + n-1Cr
int[][] dy = new int[35][35]; // 조합수를 저장할 배열 선언
public int DFS(int n, int r) {
if (dy[n][r] > 0) return dy[n][r]; // 메모이제이션 ✨
if (n == r || r == 0) return 1;
else return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
}
728x90
'Algorithm > 알고리즘' 카테고리의 다른 글
[JAVA/자료구조] 스택(Stack)과 큐(Queue) (0) | 2023.10.16 |
---|---|
[JAVA] 이진트리 순회(DFS, BFS) (0) | 2023.09.17 |
[JAVA/알고리즘] 이진 탐색 알고리즘을 이용한 문제해결 (0) | 2023.09.12 |
[JAVA/알고리즘] 이진 탐색(Binary Search) (0) | 2023.08.15 |
[JAVA/알고리즘] 정렬 알고리즘의 종류 (0) | 2023.08.08 |