728x90
반응형
다이나믹 프로그래밍(Dynamic Programming)
큰 문제를 작은 문제로 쪼개어 해결하는 알고리즘 기법입니다. 이 기법은 작은 문제의 결과를 저장하고, 이를 이용해 큰 문제를 해결합니다. 이를 메모이제이션(Memoization)이라고도 부르며, 일반적으로 재귀적인 방법으로 구현됩니다.
다이나믹 프로그래밍은 최적화 문제를 해결하는데 효과적입니다.
예를 들어, 주어진 자원을 최대한으로 활용하여 최대 이익을 얻는 문제, 두 문자열 사이의 최장 공통 부분 문자열을 찾는 문제, 최소 비용으로 목표 지점에 도달하는 경로를 찾는 문제 등에 이용됩니다.
대표적인 다이나믹 프로그래밍 알고리즘
- 피보나치 수열 계산
- LCS(Longest Common Subsequence) 문제
다이나믹 프로그래밍으로 풀 수 있는 문제의 속성
1. 겹치는 부분 문제가 있는 경우 (Overlapping Subproblem)
- 큰 문제를 작은 문제로 쪼갤 수 있는 경우(피보나치 수열)
2. 최적화 부분 구조 (Optimal Substructure)
- 작은 문제를 풀어나감으로써 큰 문제의 정답을 구할 수 있는 경우
다이나믹 프로그래밍을 이용해 피보나치 수 구현해보기
메모이제이션이 없는 함수와 메모이제이션이 있는 함수로 구현할 수 있습니다.
메모이제이션이 없는 함수
let Fibonacci = (n) => {
n > 2 ? Fibonacci(n - 2) + Fibonacci(n - 1) : 1;
};
메모이제이션이 있는 함수(top-down방식)
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 (bottom-up)
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문을 이용하여 처음부터 더해가는 방식입니다.
소감
새로운 알고리즘을 알게 되면 항상 생각하는 것이 있습니다. 대체 어디에 사용해야하는 것일까 입니다. 그래서 좀 찾아봤는데요.
배낭문제(제한된 용량에 가치가 다른 물건을 넣을 때, 가치의 합을 최대화하는 문제), 건물 건설 최적화, 최단 경로 문제(다익스트라) 같은 것에 사용이 된다고 합니다.
뭐 언젠가는 사용하겠죠? 뭔가를 배운다는 것을 즐겁네요.
출처
반응형
'코딩 개발' 카테고리의 다른 글
Macbook 에서 AWS EC2 Window 원격 제어 (0) | 2023.05.02 |
---|---|
Agile & Waterfall 개발 방식 (0) | 2023.04.02 |
TDD 테스트 주도 개발 (0) | 2023.03.02 |
IT 5분 잡학 사전 EP39~EP45 (0) | 2023.03.02 |
IT 5분 잡학 사전 EP30~EP34 (0) | 2023.02.27 |