[DP & GA] Dynamic Programming & Greedy Algorithm

이번에는 Dynamic Programming에 대해서 알아보겠습니다.

해석하면 동적 프로그래밍이라고 하지만.. 절대 동적이지 않습니다.. Dynamic Programming은 각 경우에 대한 table을 만들어서 점화식을 도출해내는 방식을 말하는데 간단한 문제에 대해서 알아봅시다. 풀어볼 문제는 백준 알고리즘의 1003번 문제입니다!

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

문제는 간단한 피보나치 수열에 대해서 fibonacci(n)이라고 했을 때 fibonacci(N)을 호출하면 fibonacci(0), fibonacci(1)을 얼마나 불러오는지

구하는 문제입니다. 문제에 보면 피보나치 수열에 대한 함수를 줬는데,

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

이렇게 함수를 줬어요. 사람이라면 저걸 보고 먼저 각 조건문에 카운트를 해주는 방식을 사용 했겠죠..?전 그랬는데.. 그러니까 시간초과!!ㅋㅋㅋ 

 먼저 피보나치 수열는 수열의 기본으로 나오는 예시 이기 때문에 모두 안다고 생각하고..! 한번 동적 프로그래밍으로 풀어봅시다. 

제가 동적 프로그래밍은 table을 만들어서 접근한다고 하였는데, 지금 우리가 구해야할 것은 0, 1번째가 몇 번 호출 되었는지?를 구하는 것이니까.. 이것에 대한 table을 그려봅시다. 

간단하죠??? 이렇게 풀면 완성!!! 코드는 아래에 있습니다. 

피보나치 코드

Dynamic Programming의 중요한 점은?? table을 이쁘게 만들기!!! 기억하시기 바랍니닷!!!!

Dynamic Programming이랑 비슷한 풀이법으로 Greedy Algorithm이라고 있어요. 둘은 사실 똑같은(?) 방법인데, Dynamic Programming으로 하면 연산량이 많아지는 경우에 주로 사용한다고 합니다. Greedy Algorithm의 목표는 동적 프로그래밍의 점화식 도출과는 조금 다르게 각 단계에서의 최적값을 얻는 것입니다!!! 오홍..!! 이번에도 간단한 문제로 알아봅시다. 문제는 백준 알고리즘의 11399번 문제입니다.

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

 문제는 ATM기를 기다리는 사람들이 있는데, 사람들이 총 기다린 시간의 최솟값을 얻는 문제입니다. 저도 문제를 많이 풀지는 않았지만, Dynamic Programming을 적용해야 하는 문제는 해당 단계의 값을 원하고, Greedy Algorithm은 최대, 최소값을 원하더라구요. 이것도 하나의 TIP이 될 수 있겠네요. 이 문제는 간단하네요!! 정답은 그냥 가장 적게 사용하는 사람을 앞에 두면 됩니다. 뭐 이건 당연하겠죠? 이게 왜 Greedy냐면, 그리디 알고리즘은 각 단계의 최적 값을 원하는데, 문제에서 보면 다음 사람의 업무 시간은 전 사람 다 하는거 기다리고 자기꺼 하는 시간의 합이잖아요. 그럼 각 단계에서 최적값이 되려면? 전 사람의 업무 시간이 짧으면 되죠. 약간 어거지 문제이긴 하지만, 결국 최적화 문제는 맞네요..!!!

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    int N;
    int person[1005];
    int sum[1005];
    int result = 0;
    cin>>N;
    for(int i=1; i<=N; i++) cin>>person[i];
    sort(person+1,person+N+1); sum[1] = person[1]; result = sum[1];
    for(int i=2; i<=N; i++)
    {
        sum[i] = person[i] + sum[i-1];
        result+=sum[i];
    }
    cout<<result<<endl;
    
    return 0;
}

코드는 간단하게 STL을 사용해서..! 역시 갓티엘... 정리해보자면!!

---

Dynamic Programming의 중요한 점은?? table을 이쁘게 만들기!!! | 언제쓰지 ?? 해당 단계의 값을 원할 때 

Greedy Algorithm의 중요한 점은?? 각 단계에서 최적화 | 언제쓰지?? 총 최대, 최소를 구할 때

---

이렇게 할 수 있겠네요!!! 그럼 이만 가보겠습니다~~!!