들어가기에 앞서
참고한 자료를 바탕으로 비전문가가 정리한 글이므로 오류가 있을 수 있습니다.
오류에 대한 피드백은 언제든지 환영합니다. 부디 댓글로 알려주시길 바랍니다. 감사합니다.
동적 계획법이란?
동적 계획법(이하 DP)은 큰 문제를 작은 문제로 나누어 해결하는 방법입니다. 이때, 작은 문제들의 해결책을 저장하고 활용하여 중복 계산을 피합니다. 이런 특징으로 인해 DP는 “기억하며 풀기” 라고도 불립니다. DP는 주로 최적 부분 구조와 중복 부분 문제의 조건을 만족하는 문제에 적용됩니다.
1) Overlapping Subproblems(중복 부분 문제) - 동일한 작은 문제들이 반복해서 나타나는 문제
2) Optimal Substructure(최적 부분 구조) - 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과값을 구할 수 있는 경우
동적 계획법의 원리
동적 계획법은 다음과 같은 원리에 기반합니다.
1.
작은 문제들의 해결책 저장: 작은 문제들을 해결하고 그 결과를 저장합니다.
2.
저장된 해결책 활용: 저장된 해결책을 활용하여 큰 문제의 해결에 활용합니다.
3.
중복 계산 제거: 중복되는 계산을 피하여 효율적으로 해결책을 찾습니다.
동적 계획법의 응용
동적 계획법은 다양한 분야에서 응용됩니다. 예를 들어, 다음과 같은 문제들에 적용될 수 있습니다.
1.
피보나치 수열 계산: 재귀적으로 피보나치 수열을 계산하는 것보다 DP를 활용하여 효율적으로 계산할 수 있습니다.
2.
최단 경로 문제: 다익스트라 알고리즘 등의 최단 경로 알고리즘에서 DP를 적용하여 최적해를 찾을 수 있습니다.
3.
4.
class Solution {
public List<List<Integer>> generate(int numRows) {
// f(1) = 1 , f(2) = 2
// 계산된 리스트를 계속 저장해야함
List<List<Integer>> pascal = new ArrayList<>();
if(numRows == 1){
pascal.add(new ArrayList<>(List.of(1)));
return pascal;
}
else{
pascal.add(new ArrayList<>(List.of(1)));
pascal.add(new ArrayList<>(List.of(1, 1)));
if(numRows>2){
for(int i=3 ; i<numRows+1; i++){
int n = pascal.get(i-2).size();
List<Integer> prevPascal = pascal.get(i-2);
List<Integer> nextPascal = new ArrayList<>();
nextPascal.add(1);
for(int j = 0 ;j< n-1;j++){
nextPascal.add(prevPascal.get(j) + prevPascal.get(j+1));
}
nextPascal.add(1);
pascal.add(nextPascal);
}
// System.out.println(pascal.get(1).toString());
}
return pascal;
}
}
}
Java
복사
분할정복,재귀와의 차이점
분할 정복:
•
분할 정복은 문제를 나누어서 해결하는 전략으로, 주로 재귀적으로 문제를 해결합니다.
•
큰 문제를 작은 부분 문제로 나누어 각 문제를 해결한다는 점은 DP와 같지만, 각 부분 문제가 독립적이며 중복으로 발생하지 않는다는 점에서 차이가 있습니다.
•
주로 정렬 알고리즘 (예: 합병 정렬, 퀵 정렬)이나 이진 탐색과 같은 문제에 적용됩니다.
재귀 :
•
재귀는 함수가 자신을 호출하는 것을 허용하는 프로그래밍 기법입니다.
•
DP와 마찬가지로 문제를 하위 문제로 나누어 작은 입력에 대해 반복적으로 해결하는 데 사용되지만, 값을 저장하지 않기에 반복되는 계산을 피할 수 없는 경우가 많습니다.
•
예를 들어, 피보나치 수열을 계산하는 재귀적인 방법은 중복 계산이 많아 효율적이지 않습니다.
packge com.test;
public class Fibonacci{
// DP 를 사용 시 작은 문제의 결과값을 저장하는 배열
// Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음)
static int[] topDown_memo;
static int[] bottomup_table;
public static void main(String[] args){
int n = 30;
topDown_memo = new int[n+1];
bottomup_table = new int[n+1];
long startTime = System.currentTimeMillis();
System.out.println(naiveRecursion(n));
long endTime = System.currentTimeMillis();
System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime));
System.out.println();
startTime = System.currentTimeMillis();
System.out.println(topDown(n));
endTime = System.currentTimeMillis();
System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime));
System.out.println();
startTime = System.currentTimeMillis();
System.out.println(bottomUp(n));
endTime = System.currentTimeMillis();
System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime));
}
// 단순 재귀를 통해 Fibonacci를 구하는 경우
// 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
public static int naiveRecursion(int n){
if(n <= 1){
return n;
}
return naiveRecursion(n-1) + naiveRecursion(n-2);
}
// DP Top-Down을 사용해 Fibonacci를 구하는 경우
public static int topDown(int n){
// 기저 상태 도달 시, 0, 1로 초기화
if(n < 2) return topDown_memo[n] = n;
// 메모에 계산된 값이 있으면 바로 반환!
if(topDown_memo[n] > 0) return topDown_memo[n];
// 재귀를 사용하고 있음!
topDown_memo[n] = topDown(n-1) + topDown(n-2);
return topDown_memo[n];
}
// DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
public static int bottomUp(int n){
// 기저 상태의 경우 사전에 미리 저장
bottomup_table[0] = 0; bottomup_table[1] = 1;
// 반복문을 사용하고 있음!
for(int i=2; i<=n; i++){
// Table을 채워나감!
bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
}
return bottomup_table[n];
}
}
Java
복사