동적계획법2 [SW역량] 14501. 퇴사 N수가 작아서, 완전탐색으로 풀어도되고, 그렇지 않고 가능하다면 DP로 풀어도 되는 문제이다. 여러가지 DP 해법을 보다가, 가장 와 닿는 풀이방법을 찾았다. d[i] : i일로부터 N일까지 최대 수익 이라고 정하면, 식을 자연스럽게 세울 수 있다. d[i] = max(d[i+1], d[i + t[i]] + p[i]) 이제 d[i]를 solve(int i)라고 놓고, 리턴값을 d[i]으로 설정해서 풀어보자. 그렇다 Top-down 방식의 동적계획법이다. 기저 조건은, d[N + 1] = 0 d[N + 1 초과] = - INF 라는 것이다. 이것은 예제 하나를잡아 하나하나 대입해가면서, 마지막 조건을 생각하면 이해가 쉬운 편이다. Hint: 마지막 날의 t[i]가 1이라면, d[i + t[i]] + p[i.. 2019. 10. 19. 8. 동적계획법(DP) 2 메모이제이션 구현 패턴 int fun(int a, int b) { // Process the base case if (...) return ...; // (a, b)에 대한 답을 구한 적이 있으면 return int& ret = cache[a][b]; if (ret != -1) return ret; // Get what you want here ... return ret; }memset(array, 0, sizeof(array)); for문보다 쉽게 초기화 할 수 있음. 단, 0과 -1만 '운 좋게도' 초기화 될 수 있습니다. 메모이제이션의 시간 복잡도 분석 = (부분 문제 수) x (한 부분 문제 당 반복문의 수행 횟수) 2019. 8. 26. 728x90 이전 1 다음
