GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결
알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub.
github.com
특정 형태의 점화식을 갖는 dp에 대하여 시간 복잡도를 O(N^3)에서 O(N^2)으로 줄이는 기법이다.
자주 등장하는 주제도 아니고 증명도 매우 어렵다고 하여 증명은 생략하였다.
AtCoder Educational DP Contest N - Slimes 문제에 해당 기법을 적용할 수 있다.
N이 작기 때문에 O(N^3)으로도 풀린다.
2023/01/06 추가
Knuth's Optimization을 적용할 때 메모리 접근을 비효율적으로 하면 실행 시간이 매우 길어진다.
메모리 접근을 효율적으로 하도록 소스 코드를 개선하였다.
끝
'알고리즘' 카테고리의 다른 글
| Euler's phi function (0) | 2022.10.05 |
|---|---|
| Union-Find (0) | 2022.10.04 |
| Order Statistic Tree (0) | 2022.10.01 |
| Fenwick Tree (0) | 2022.09.30 |
| 유클리드 알고리즘 관련 정리 (0) | 2022.09.26 |
