동적 프로그래밍
큰 문제를 더 작은 문제로 분해하여 해결하는 알고리즘 기법입니다. 이 기술은 더 작은 문제의 결과를 저장하고 더 큰 문제를 해결하는 데 사용합니다. 이를 메모이제이션이라고도 하며 일반적으로 재귀적으로 구현됩니다.
동적 프로그래밍은 최적화 문제를 해결하는 데 효과적입니다.
예를 들어, 주어진 자원의 사용을 최대화하여 최대 이익을 얻는 문제, 두 문자열 사이에서 가장 긴 공통 하위 문자열을 찾는 문제, 목표에 대한 최소 비용 경로를 찾는 문제에 사용됩니다.
'추천 관련글,
![[Java] String,](https://t1.daumcdn.net/keditor/emoticon/face/large/073.png "[Java] String,")
![[kotlin 문법] 변수와 데이터](https://vest.fantacola.kr/wp-content/plugins/contextual-related-posts/default.png "[kotlin 문법] 변수와 데이터")
일반적인 동적 프로그래밍 알고리즘
- 피보나치 수열 계산
- LCS(Longest Common Subsequence) 문제
동적 계획법으로 풀 수 있는 문제의 속성
1. 부분이 겹치는 문제가 있는 경우(Overlapping Subproblem)
- 큰 문제를 더 작은 문제로 분해할 수 있는 경우(피보나치 수열)
2. 최적의 하부 구조
- 작은 문제를 해결하면 더 큰 문제에 대한 답이 나올 수 있습니다.
동적 프로그래밍으로 피보나치 수 구현
메모이제이션이 없는 함수와 메모이제이션이 있는 함수로 구현할 수 있습니다.
저장하지 않고 작동
let Fibonacci = (n) => {
n > 2 ? Fibonacci(n - 2) + Fibonacci(n - 1) : 1;
};메모리 기능이 있는 기능(하향식)
let fiboArr = ();
let fiboMemoization = (n) => {
if (n <= 2) {
fiboArr(n) = 1;
}
if (!fiboArr(n)) {
fiboArr(n) = fiboMemoization(n - 2) + fiboMemoization(n - 1);
}
return fiboArr(n);
};n=10일 때 결과의 차이를 느껴보자. (원래 10으로 설정했는데 너무 길어서 줄였습니다…)
메모이제이션 미사용
7
5
3
1
2
4
2
3
1
2
6
4
2
3
1
2
5
3
1
2
4
2
3
1
2
======================================
메모이제이션 사용
7
5
3
1
2
4
2
3
6
4
5나는 그런 극명한 차이를 본다.
메모이제이션이 있는 방법 2(상향식)
let fiboArr = ();
let fiboBottomUp = (n) => {
fiboArr(0) = 0;
fiboArr(1) = 1;
for (let i = 2; i <= n; i++) {
fiboArr(i) = fiboArr(i - 1) + fiboArr(i - 2);
}
return fiboArr(n);
};for 문으로 처음부터 추가하는 방식입니다.
인상
새로운 알고리즘을 배울 때 항상 고려해야 할 것이 있습니다. 또 어디에 사용해야 할까요? 그래서 조사를 좀 해봤습니다.
그것은 배낭 문제(유한한 용량에 다른 값을 채울 때 값의 합을 최대화하는 문제), 건물 건설 최적화 및 최단 경로 문제(Dijkstra)와 같은 것에 사용하기 위한 것입니다.
언젠가는 무엇을 사용할 것인가? 무언가를 배우는 것은 재미있습니다.
원천