본문 바로가기
NOTE/Algorithm

[자료구조] 다이나믹 프로그래밍 강의 정리

by DevAthena 2018. 4. 1.

출저 - > 유튜브 강의 https://www.youtube.com/watch?v=0o2hF-To_6Q 를 보면서 정리



[ 다이나믹 프로그래밍 ]

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

- 두가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

1. Overlapping Subproblem (겹치는 부분문제)

2. Optimal Substructure (최적 부분구조)



 



ex - 피보나치 수

1
2
3
4
5
6
7
8
9
10
11
int fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
cs



아래와 같이 중복되는 문제 발생




ex - 중복을 제거한 메모된 피보나치 수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int memo[100];
int fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }
    else
    {
        if (memo[n] > 0)
        {
            return memo[n];
        }
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return memo[n];
    }
}
cs



다이나믹을 푸는 두 가지 방법이 있다.

1. Top-down

2. Bottom-up

 

아래는 Bottom-up을 통해 피보나치를 해결한 것이다.

1
2
3
4
5
6
7
8
9
10
11
int d[100];
int fibonacci(int n)
{
    d[0] = 1;
    d[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        d[i] = d[i - 1] + d[i - 2];
    }
    return d[n];
}
cs



10->5->4->2->1 보다

10->9->3->1 이 더 빠르다.




위 '1로 만들기' 문제를 Top-down 방식으로 풀게 되면..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int go(int n)
{
    if (n == 1)
        return 0;
 
    // memoization
    if (d[n] > 0)
        return d[n];
    
    // N -> N-1
    d[n] = go(n - 1) + 1;
 
    // N -> N/2
    if (n % 2 == 0)
    {
        int temp = go(n / 2) + 1;
        if (d[n] > temp)
            d[n] = temp;
    }
 
    // N -> N/3
    if (n % 3 == 0)
    {
        int temp = go(n / 3) + 1;
        if (d[n] > temp)
            d[n] = temp;
    }
 
    return d[n];
}

cs




그리고, Bottom-up 방식으로 풀게 되면...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    d[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        // N -> N-1
        d[i] = d[i - 1] + 1;
        // N -> N/2
        if (i % 2 == 0 && d[i] > d[i / 2] + 1)
        {
            d[i] = d[i / 2] + 1;
        }
        // N -> N/3
        if (i % 3 == 0 && d[i] > d[i / 3] + 1)
        {
            d[i] = d[i / 3] + 1;
        }
    }
}
cs



타일링 https://www.acmicpc.net/problem/1793

2*n 타일링 https://www.acmicpc.net/problem/11726

2*n 타일링2 https://www.acmicpc.net/problem/11727

 


 



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

 



1시간 13분까지 들었당.

내일은 붕어빵 판매하기부터 들어야지.


저작자표시 비영리 변경금지

'NOTE > Algorithm' 카테고리의 다른 글

[알고리즘] 에러의 종류 (펌)  (0) 2018.04.01
[알고리즘문제] DFS와 BFS  (0) 2018.04.01
[알고리즘문제] 백준_음계  (0) 2018.04.01
[알고리즘문제] 백준_OX퀴즈  (0) 2018.04.01
[Algorithm] A* 알고리즘  (0) 2016.11.23

관련글

티스토리툴바