Swimmer

실패 DP로 풀어서 시간초과가 안될것이라 생각했는데, 시간 초과로 Fail.. 이항 정리 방식 + DP 로 접근하니 시간 초과 안됨 DP로 풀 수 있는 방식은 이항 정리로도 접근 가능함을 배웠음 #include #include // 포인트 // 바로 DP 형식으로 푸니 시간초과 이슈를 해결할 수 없었음, 함수 : GetConnectCaseByDynamicProgramming // 이항 정리 방식으로 푸니 시간 초과 이슈를 해결할 수 없었음, 함수 : GetConnectCaseByBinomialTheorem // 이항 정리 방식에 DP를 더해 배열 값을 사용하니 시간 초과 이슈를 해결할 수 있었음 typedef unsigned long long int uint64_t; uint64_t GetConnectC..

강화학습 문제는 MDP로 정의되는 문제이다. 따라서 강화학습 문제를 풀고 싶으면 MDP 문제를 푸는 기법을 사용하면 된다. MDP 문제는 Agent가 환경을 아는 상황(State Transition Matrix와 Discounted rate를 아는 상황)이냐 그렇지 않느냐에 따라 적용할 수 있는 기법이 다르다. 가장 먼저 환경을 아는 상황에서는 Dynamic Programming 기법 (이하 DP)를 적용할 수 있다. DP를 적용해 문제를 풀기 위해선 문제가 2가지 특성을 가지고 있어야 한다. 첫번째는 Optimal structure이다. 큰 문제의 하위 문제인 작은 문제에서의 최적 값이, 큰 문제에서도 최적값인 것이다. 두번째는 Overlapping problems이다. 큰 문제를 풀기 위해서 작은 문..