[18일 차] 알고리즘 (동적 계획법)

---

25/02/19 (수)

오잉 뭐했다고 수요일일까요

어제 스파링 반으로 접히고 몸 성한곳 없이 일어났습니다.

그래도 엄청 상쾌하네요

오늘도 열심히 달려보겠습니다!

---

 

1. 동적 계획법

1.1) 동적 계획법

package basic.Ch21_Memoization;

public class fibonacci {
    public static void main(String[] args) {
        //#1 재귀 호출
        System.out.println(fibo_rc(20)); //오래 걸림

        //#2 메모이제이션
        System.out.println(fibo_rc_memoi(50));

        //#3 동적 계획법 (점화식 + 메모이제이션)
        System.out.println( fibo_dp(50) );
    }

    public static long fibo_rc(int n){
        if(n == 1 || n == 2) return 1;
        return fibo_rc(n-1) + fibo_rc(n-2);
    }

    static long[] memoi_rc = new long[51];
    public static long fibo_rc_memoi(int n) {
        if(n == 1 || n == 2) return 1;
        if(memoi_rc[n] > 0) return memoi_rc[n];
        else return memoi_rc[n] = fibo_rc_memoi(n-1) + fibo_rc_memoi(n-2);
    }

    static long[] memoi_dp = new long[51];
    public static long fibo_dp(int n) {
        if(n == 1 || n == 2) return 1;

        memoi_dp[1] = 1;
        memoi_dp[1] = 1;

        for (int i = 3; i <= n ; i++) {
            memoi_dp[i] = memoi_dp[i-1] + memoi_dp[i-2];
        }

        return memoi_dp[n];
    }
}

• 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 함

 

1.2) 점화식 세우기와 동적 계획법

1. 문제를 해결하는 해가 이미 있다고 가정 (F0 = 0)
2. 종료 조건 설정 (F1 = 1)
3. 1, 2를 활용하여 점화식 세우기 (F2 = F(n+1) + Fn)

---

재귀 활용 점화식 구현

이 방식은 함수를 재귀하므로 스택 메모리에 함수들이 쌍혀 런타임 오류 발생 가능성

그러므로 문제가 생길 것 같을 때 취하는 다음과 같은 방법이 있음

• 재귀 호출 자체를 쓰지 않는 법 -> 반복문
• 재귀 호출의 횟수를 줄이는 법 -> 메모제이션

 

1.3) 재귀 호출의 횟수를 줄여주는 메모이제이션

 

1.4) 최장 증가 부분 수열

 

1.5) 최장 공통 부분 수열

 

 

2.  실습

2.1) 백준

https://www.acmicpc.net/problem/1915

https://www.acmicpc.net/problem/1149

 

2.2) 아파트 문제

 

2.3) 막대 문제

 

2.4) G4_1915_가장 큰 정사각형

 

 

3.  마무리

3.1) WorkShop

• 수를 더 크게해서 메모이제이션과 동적배열할당의 성능 비교

 

3.2) 더 공부할 것