[게임 프로그래머 입문 올인원] 모던 C++ : 동적 계획법 (85강)

A. 동적 계획법 (Dynamic Programming)

1. Dynamic Programming

a. 동적 계획법이란?

🌟 큰 문제를 작은 하위 문제로 나누어 푸는 알고리즘 설계 기법

 

최적화 문제나 최단 경로 문제와 같이 큰 문제를 작은 부분으로 나누어 해결해야 하는 경우에 사용

ex) 피보나치 수열 계산, 그래프 최단 경로 찾기, 배낭 문제

 

b. 동적 계획법의 특징

• 중복 계산 최소화: 동적 계획법은 작은 하위 문제의 해답을 저장하고 재활용하여 중복 계산을 피해 시간 복잡도를 획기적으로 줄임
• 최적 부분 구조: 큰 문제의 최적 해결 방법이 작은 하위 문제의 최적 해결 방법으로부터 구성될 수 있어야 함. 이를 통해 작은 하위 문제의 해답을 결합하여 전체 문제의 최적 해답을 찾을 수 있음
• 상향식 접근법: 하위 문제부터 시작하여 상위 문제의 해답을 구하는 방식으로 문제를 해결. 이를 통해 전체 문제의 해답을 구할 수 있음

 

c. 이항계수

문제

 

962598회를 반복해서 같은계산을 했음

 

도식화, 중복되어서 계산한게 두개씩 있음

 

이렇게 cache에 중복

 

메모이제이션이라고 하고,  사용할 최대 숫자는 50으로 설정

 

-1로 밀어줌

 

복사하지 않고 원본을 넣어주기

 

d. 무기 강화 주문서 예제

문제

 

1강부터 되는 회수, 2강부터 되는 회수, 3강부터 되는 회수를 따로 계산해서 cache에 저장된다

 

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -