알고리즘 - 동적 계획법 (Dynamic Programming)

ofijwe·2024년 9월 4일

algorithm

Algorithm

목록 보기

4/4

📒 재귀 호출과 메모이제이션 (with Fibonacci)

1️⃣ 재귀

0(0항)과 1(1항)로 시작 → 이전의 두 수 합을 다음 항으로 하는 수열
- 0, 1, 1, 2, 3, 5, 8, 13 …
i번 째 값 계산하는 함수 F 정의 (재귀)
- F0 = 0, F1 = 1
- Fi = F(i-1) + f(i-2) for i ≥ 2

피보나치 재귀 알고리즘

    static long fibo1(int n) { // 재귀
        callCnt1++;
        if (n <= 2) return 1;
        return fibo1(n - 1) + fibo1(n - 2);
    }

f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
f(1) = f(0)

피보나치 재귀 문제점
- 중복 호출 多
- 시간 효율도 → 지수 시간의 복잡도
- 상태 공간 트리가 이진 트리처럼 됨
피보나치 재귀 문제점 해결책
- 메모이제이션 활용

2️⃣ 메모이제이션

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장
매번 다시 계산하지 않도록 함 → 전체 실행속도 향상
동적 계획법의 핵심 기술
메모제이션 가능한 함수
- 순수 함수
  - 함수 실행이 부수 효과를 일으키지 않는 함수
  - 동일한 input(같은 인자)에 대해 동일한 output(같은 리턴값) 반환하는 함수
  - 매개변수 이외에 함수 외부의 것들을 사용하지 않는 함수

메모이제이션 알고리즘

    static long fibo2(int n) { // 메모이제이션 (하향식 접근)
        callCnt2++;
        if (memo[n] == -1) { // 메모가 안 된 경우
            memo[n] = fibo2(n - 1) + fibo2(n - 2);
        }
        return memo[n];
    }

fibo1(n) 값 계산하자마자 저장(memoize) → 실행시간 O(n)

메모이제이션 문제점
- 추가적인 메모리 공간 필요
- 재귀 함수 호출로 인한 시스템 호출 스택 사용
- 실행 속도 저하 or 오버 플로우 발생 가능
메모이제이션 문제점 해결책
- 동적 계획법(DP) 활용

📒 동적 계획법

1️⃣ DP

동적 계획법 (Dynamic Programming
그리디 알고리즘과 같이 최적화 문제 해결 알고리즘
먼저 작은 부분 문제 해 구하기 → 이를 이용해 보다 큰 부분 문제 해결 → 최종적으로 원래 주어진 문제 해결하는 기법

2️⃣ DP 적용 조건

중복 부분문제 구조(Overlapping subproblems)
최적 부분문제 구조(Optimal substructure)

3️⃣ 중복 부분 문제 구조

DP는 큰 문제를 이루는 작은 문제들 먼저 해결 → 작은 문제 최적 해를 이용해 순환적으로 큰 분제 해결
- 순환적인 표현 : DP에서는 ‘점화식’ 사용
DP 문제의 순환적인 성질 때문에 이전에 계산되었던 작은 문제 해가 다른 곳에서 필요(Overlapping subproblem)
이를 위해 DP는 이미 해결된 작은 문제 해를 어떤 저장 공간(table)에 저장
저장된 해를 다시 필요할 때마다 재계산 X → table 참조 → 중복 계산 회피

4️⃣ 최적 부분 문제 구조

DP가 최적화에 대한 모든 문제에 적용되는 것 X → 최적화의 원칙 만족해야 함.
최적화 원칙
- 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제 해 역시 최적
DP의 방법이 큰 문제 최적 해를 작은 문제 최적 해를 이용해 구함 → 만약 큰 문제의 최적 해가 작은 문제의 최적 해로 구성 X → DP 적용 X
최적 원칙이 적용되지 않는 예 : 최장경로(Longest Path) 문제

5️⃣ 분할 정복 VS 동적계획법

분할 정복	DP
연관 없는 부분 문제로 분할	부분 문제 연관 X → 적용 X (점화식)
부분 문제 → 재귀로 해결	부분 문제 → 더 작은 부분 문제 공유
부분 문제 해 결합	모든 부분 문제 한 번만 계산
병합 정렬, 퀵 정렬	계산 결과 저장 후 재사용
하향식 방법 접근	상향식 방법 접근

6️⃣ DP 적용 접근 방법

최적해 구조 특성 파악
- 문제를 부분 문제로 나눔
최적해 값을 재귀적으로 정의
- 부분 문제의 최적해 값에 기반 → 문제 최적해 값 정의
상향식 방법으로 최적해 값 계산
- 가장 작은 부분 문제부터 해 구함 → 테이블에 저장
- 저장된 부분 문제 해 이용 → 점차 상위 부분 문제의 최적해 구함

7️⃣ DP (Fibonacci)

피보나치 수 : 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있음 → 최적 부분 구조
- 문제를 부분 문제로 분할
- 점화식 정의
- 가장 작은 부분 문제부터 해 구함 → 테이블에 저장 → 저장된 해 이용 → 상위 문제 해 구함

피보나치 DP 알고리즘

    static long fibo3(int n) { // DP (상향식 접근)
        long[] D = new long[n + 1];
        D[1] = D[2] = 1;
        for (int i = 3; i <= n; i++) {
            callCnt3++;
            D[i] = D[i - 1] + D[i - 2];
        }
        return D[n];
    }

계산하는 항(fibo_dp[n]) 개수
- n + 1 개수의 항 계산
- fibo_dp[0] ~ fibo_dp[n]까지 한 번씩만 계산

DP 알고리즘 장점
- 재귀 알고리즘과 달리 중복 계산 X
- 반복문 사용 → 함수 호출 발생 X
- 수행 속도 빠름

📒 재귀 VS 메모제이션 VS DP (with Fibonacci)

1. 알고리즘 종류

재귀적 접근: 단순한 재귀 호출을 통해 피보나치 수열의 n번째 항을 구한다.
메모이제이션(하향식 접근): 재귀 호출과 메모이제이션을 사용하여 이전에 계산된 결과를 저장하고, 동일한 계산을 피한다.
동적 계획법(DP, 상향식 접근): 작은 문제부터 차례대로 해결해 나가면서 최종 결과를 도출한다.

2. 주요 부분 및 코드 작성 방법

1. 재귀적 접근 (fibo1)

설명: 단순히 재귀를 사용하여 피보나치 수열을 계산한다. 이 방법은 반복 계산이 많아 시간이 오래 걸린다.

2. 메모이제이션 (fibo2)

설명: 메모이제이션을 사용하여 이전에 계산된 결과를 배열에 저장하고, 이미 계산된 값을 재사용하여 계산량을 줄인다.

3. 동적 계획법 (fibo3)

설명: 상향식 접근으로, 작은 문제부터 차례대로 계산하면서 최종 결과를 도출한다. 이 방법은 반복 계산을 최소화하여 가장 효율적이다.

3. 코드 설명

(1) 재귀적 접근 (fibo1)

기능: 피보나치 수열의 n번째 항을 재귀적으로 계산한다.

코드:

static long fibo1(int n) { // 재귀적 접근
    callCnt1++; // 호출 횟수 증가
    if (n <= 2) return 1; // n이 1 또는 2일 때는 1 반환
    return fibo1(n - 1) + fibo1(n - 2); // n-1항과 n-2항의 합
}

(2) 메모이제이션 (fibo2)

기능: 피보나치 수열의 n번째 항을 메모이제이션을 사용하여 하향식 접근 방식으로 계산한다.

코드:

static long fibo2(int n) { // 메모이제이션 (하향식 접근)
    callCnt2++; // 호출 횟수 증가
    if (memo[n] == -1) { // 메모가 안 된 경우
        memo[n] = fibo2(n - 1) + fibo2(n - 2); // 계산하여 메모에 저장
    }
    return memo[n]; // 저장된 값 반환
}

(3) 동적 계획법 (fibo3)

기능: 피보나치 수열의 n번째 항을 동적 계획법을 사용하여 상향식 접근 방식으로 계산한다.

코드:

static long fibo3(int n) { // 동적 계획법 (상향식 접근)
    long[] D = new long[n + 1]; // n까지 저장할 배열 생성
    D[1] = D[2] = 1; // 초기 값 설정
    for (int i = 3; i <= n; i++) {
        callCnt3++; // 호출 횟수 증가
        D[i] = D[i - 1] + D[i - 2]; // 점화식을 사용하여 값 계산
    }
    return D[n]; // n번째 피보나치 수 반환
}

(4) 메인 함수 (main)

기능: 사용자 입력을 받아 세 가지 방식으로 피보나치 수를 계산하고, 결과와 수행 횟수를 출력한다.

코드:

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 생성
    int N = Integer.parseInt(br.readLine()); // 사용자로부터 피보나치 수열의 항을 입력받음
    memo = new long[N + 1]; // 메모이제이션을 위한 배열 생성
    Arrays.fill(memo, -1); // 메모이제이션 배열 초기화
    memo[1] = memo[2] = 1; // 초기 값 설정

    System.out.println("메모이제이션 : " + fibo2(N)); // 메모이제이션 결과 출력
    System.out.println("메모이제이션 수행 횟수 : " + callCnt2); // 메모이제이션 호출 횟수 출력

    System.out.println("재귀 : " + fibo1(N)); // 재귀 결과 출력
    System.out.println("재귀 수행 횟수 : " + callCnt1); // 재귀 호출 횟수 출력

    System.out.println("DP : " + fibo3(N)); // DP 결과 출력
    System.out.println("DP 수행 횟수 : " + callCnt3); // DP 호출 횟수 출력
}

4. 전체 코드

package DP;

import java.io.*;
import java.util.*;

public class FibonacciTest {
    static long callCnt1, callCnt2, callCnt3; // 각 방법의 호출 횟수를 저장할 변수
    static long[] memo; // 메모이제이션을 위한 배열

    static long fibo1(int n) { // 재귀적 접근
        callCnt1++; // 호출 횟수 증가
        if (n <= 2) return 1; // n이 1 또는 2일 때는 1 반환
        return fibo1(n - 1) + fibo1(n - 2); // n-1항과 n-2항의 합
    }

    static long fibo2(int n) { // 메모이제이션 (하향식 접근)
        callCnt2++; // 호출 횟수 증가
        if (memo[n] == -1) { // 메모가 안 된 경우
            memo[n] = fibo2(n - 1) + fibo2(n - 2); // 계산하여 메모에 저장
        }
        return memo[n]; // 저장된 값 반환
    }

    static long fibo3(int n) { // 동적 계획법 (상향식 접근)
        long[] D = new long[n + 1]; // n까지 저장할 배열 생성
        D[1] = D[2] = 1; // 초기 값 설정
        for (int i = 3; i <= n; i++) {
            callCnt3++; // 호출 횟수 증가
            D[i] = D[i - 1] + D[i - 2]; // 점화식을 사용하여 값 계산
        }
        return D[n]; // n번째 피보나치 수 반환
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 생성
        int N = Integer.parseInt(br.readLine()); // 사용자로부터 피보나치 수열의 항을 입력받음
        memo = new long[N + 1]; // 메모이제이션을 위한 배열 생성
        Arrays.fill(memo, -1); // 메모이제이션 배열 초기화
        memo[1] = memo[2] = 1; // 초기 값 설정

        System.out.println("메모이제이션 : " + fibo2(N)); // 메모이제이션 결과 출력
        System.out.println("메모이제이션 수행 횟수 : " + callCnt2); // 메모이제이션 호출 횟수 출력

        System.out.println("재귀 : " + fibo1(N)); // 재귀 결과 출력
        System.out.println("재귀 수행 횟수 : " + callCnt1); // 재귀 호출 횟수 출력

        System.out.println("DP : " + fibo3(N)); // DP 결과 출력
        System.out.println("DP 수행 횟수 : " + callCnt3); // DP 호출 횟수 출력
    }
}

ofijwe

🖥️ Daily Dev Log ٩(๑❛ᴗ❛๑)۶

알고리즘 - 동적 계획법 (Dynamic Programming)

Algorithm

📒 재귀 호출과 메모이제이션 (with Fibonacci)

1️⃣ 재귀

2️⃣ 메모이제이션

📒 동적 계획법

1️⃣ DP

2️⃣ DP 적용 조건

3️⃣ 중복 부분 문제 구조

4️⃣ 최적 부분 문제 구조

5️⃣ 분할 정복 VS 동적계획법

6️⃣ DP 적용 접근 방법

7️⃣ DP (Fibonacci)

📒 재귀 VS 메모제이션 VS DP (with Fibonacci)

1. 알고리즘 종류

2. 주요 부분 및 코드 작성 방법

3. 코드 설명

4. 전체 코드

0개의 댓글

관련 채용 정보

알고리즘 - 동적 계획법 (Dynamic Programming)

Algorithm

📒 재귀 호출과 메모이제이션 (with Fibonacci)

1️⃣ 재귀

2️⃣ 메모이제이션

📒 동적 계획법

1️⃣ DP

2️⃣ DP 적용 조건

3️⃣ 중복 부분 문제 구조

4️⃣ 최적 부분 문제 구조

5️⃣ 분할 정복 VS 동적계획법

6️⃣ DP 적용 접근 방법

7️⃣ DP (Fibonacci)

📒 재귀 VS 메모제이션 VS DP (with Fibonacci)

1. 알고리즘 종류

2. 주요 부분 및 코드 작성 방법

3. 코드 설명

4. 전체 코드

0개의 댓글

관련 채용 정보

알고리즘 - 동적 계획법 (Dynamic Programming)