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

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

동적 계획법 (Dynamic Programming)

본문내용넣기

 

동적 계획법 TIPS

• 기저 사항
• 캐시 확인
• 구하기

위의 3가지 사항을 고려하여 코드를 짠다.

---

이항 계수 (Combination)

 

Q) 상자 안에 공 5개가 있다. 공 2개를 꺼내는 방법은?

A) 5C2

 

 

---

 

이항 계수 구하기 구현

 

#include <iostream>
#include <thread>
#include <windows.h>
using namespace std;
 
int combination(int n, int r)
{
    // 기저 사례 (안 뽑거나 다 뽑거나)
    if (r == 0 || n == r)
        return 1;
 
    return combination(n - 1, r - 1) + combination(n - 1, r);
}
 
int main()
{
    __int64 start = GetTickCount64();
 
    int lotto = combination(45, 6);
 
    __int64 end = GetTickCount64();
 
    cout << end - start << "ms" << endl;
}

 

 

---

 

동적 계획법 구현

 

#include <iostream>
#include <thread>
#include <windows.h>
using namespace std;
 
// 메모이제이션(Memoization)
int cache[50][50];
 
int combination(int n, int r)
{
    // 기저 사례 (안 뽑거나 다 뽑거나)
    if (r == 0 || n == r)
        return 1;
 
    // 이미 답을 구한 적이 있으면 바로 반환
    int& ret = cache[n][r];
    if (ret != -1)
        return ret;
 
    // 새로 답을 구해서 캐시에 저장
    return ret = combination(n - 1, r - 1) + combination(n - 1, r);
}
 
int main()
{
    ::memset(cache, -1, sizeof(cache)); // cache는 음수값이 나올 수 없으므로 -1을 초기값으로 세팅해준다.
 
    __int64 start = GetTickCount64();
 
    int lotto = combination(45, 6);
 
    __int64 end = GetTickCount64();
 
    cout << end - start << "ms" << endl;
}

 

 

---

 

마무리

마무리