tabulation
-
알고리즘: 백준 1932번 정수 삼각형 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 22. 07:21
최적 부분 구조와 중복되는 부분이 보인다. 다이나믹 프로그래밍으로! 점화식: n 번째 줄 0번째까지의 합 = n - 1번째 줄 0번째까지의 합 + n 번째 줄 0번째 값 n 번째 줄 1번째까지의 합 = max(n - 1번째 줄 0번째까지의 합, n - 1번째 줄 1번째까지의 합) + n번째 줄 1번째 값 n 번째 줄 2번째까지의 합 = max(n - 1번째 줄 1번째까지의 합, n - 1번째 줄 2번째까지의 합) + n번째 줄 2번째 값 ... n 번째 줄 n - 1번째까지의 합 = max(n - 1번째 줄 n - 2번째까지의 합, n - 1번째 줄 n - 1번째까지의 합) + n번째 줄 n - 1번째 값 n 번째 줄 n번째까지의 합 = n - 1번째 줄 n - 1번째까지의 합 + n 번째 줄 n번째 값..
-
알고리즘: 백준 1149번 RGB거리 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 21. 14:43
최적 부분구조와 중복되는 부분이 있으므로 다이나믹 프로그래밍으로 풀어줍니다. 점화식: 1. n번째 집에서 R을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 G을 칠할 때 비용의 최솟값, n - 1 번째 집에서 B을 칠할 때 비용의 최솟값 ) + n 번째 R을 칠하는데 드는 비용 2. n번째 집에서 G을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 R을 칠할 때 비용의 최솟값, n - 1 번째 집에서 B을 칠할 때 비용의 최솟값 ) + n 번째 G을 칠하는데 드는 비용 3. n번째 집에서 B을 칠할 때 비용의 최솟값 = min( n - 1 번째 집에서 R을 칠할 때 비용의 최솟값, n - 1 번째 집에서 G을 칠할 때 비용의 최솟값 ) + n 번째 B을 칠하는데 드는 비용 n개..
-
알고리즘: 다이나믹 프로그래밍(dynamic programming) 공부하기! (Memorization, Tabulation, 공간최적화)알고리즘 2020. 7. 10. 19:34
다이나믹 프로그래밍(Dynamic Programming)이란? 다이나믹 프로그래밍은 부분 문제들의 답을 중복되지 않게 최적의 방법으로 구하고 이를 통해 기존의 답을 구하는 방식이다. 정리하자면 어떤 한 문제가 최적부분구조와 중복되는 부분 문제가 있을 때 동적 프로그래밍을 사용하면 효율적이다. (두 조건을 만족하지 않아도 다이나믹 프로그래밍을 할 수 있다.) → 최적부분구조(Optimal substructure) 어떤 문제가 최적 부분구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해서 기존 문제의 최적의 답을 구할 수 있다. 예를 들면, 최단경로를 찾는 문제가 있다. → 중복되는 부분 문제(Overlapping subproblems) 주로 재귀(recursion)을 사용하는 경우, 중복되는 문제들..