23.01.18 TIL 다이나믹 프로그래밍(DP)

오늘 한 일

• 백준 3문제 풀기
• 자바 강의 듣기

공부하면서 궁금한 점

다이나믹 프로그래밍(Dynamic Programing)

다이나믹 프로그래밍은 큰 문제를 작게 나누어 푸는 기법이다.

가장 큰 특징은 나누어 둔 작은 문제들을 한번씩만 풀어야 한다는 것이다.

즉, 작은 문제들의 결과를 배열에 저장시키고 그 결과를 사용하는 것이다. 

 

접근 방법 

접근 방법으로는 크게 두가지가 있는데

1. Bottom-up방식 (상향식)

-작은 문제부터 구해 나가며 큰 문제를 푸는 방식

-보통 for문을 많이 사용

 

2. Top-down방식 (하향식)

-큰 문제에서 필요할 때 작은 문제를 해결해 푸는 방식

-보통 재귀를 많이 사용

 

대표적으로 피보나치 수열이 있다

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

앞의 두 수를 더하면 다음 수가 되는 방식의 수열이다.

 

Top-down방식

// 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }

 

Bottom-up방식

     d[1] = 1;
     d[2] = 1;
     int n = 50; // 50번째 피보나치 수를 계산

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

 

---

 내일 할 일

• 백준 3문제풀기
• Spring강의 듣기