반응형 메모이제이션2 BOJ 1005 : ACM Craft 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1005 위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다. 4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다. 따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다. 이런 문제는 위상 정렬을 이용해서 풀 수 있다. 1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다. 2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다. 입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다. ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다. #.. 2021. 7. 14. BOJ 14501, 15486 : 퇴사, 퇴사 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/14501 www.acmicpc.net/problem/15486 퇴사 1의 경우는 완전 탐색으로 풀 수 있지만, 퇴사 2는 N이 매우 크므로, 다이나믹 프로그래밍, 메모이제이션(memoization)으로 풀어야 한다. DP[i] = i일 전까지의 최대 이익 이라고 정의를 하자. i일에 일을 수행하지 않으면, DP[i + 1] = DP[i]와 기존 memoization의 값 중 큰 값이 된다. i일에 일을 수행한다면, i일 전까지의 최대 이익인 DP[i]와 i일에 받을 보수 P[i]를 더한 값 vs 기존 memoization의 값 중 큰 값. 즉, DP[i + T[i]] = DP[i] + P[i] 와 DP[i + T[i]] 중 큰 값을 선.. 2021. 2. 15. 이전 1 다음 반응형
