728x90 Knuth's Optimization 썸네일형 리스트형 [알고리즘]Knuth's optimization 크누스 최적화 백준의 11066번 문제를 풀다가 발견한 최적화 기법이다. (문제를 해결했던 코드) 이 알고리즘은 동적 계획법으로 해결하는 문제에서 특수한 조건일 때 시간 복잡도를 O(n3)에서 O(n2)까지 줄일 수 있는 강력한 알고리즘이다. 사용할 수 있는 동적 계획법의 종류에는 이차원 배열인 C와 C를 이용한 Dynamic Programming을 적용한 이차원배열인 DP가 있다고 했을 때 다음과 같은 조건이 필요하다. 점화식의 형태: DP[i][j]=min(DP[i][k]+DP[k][j])+C[i][j] (i<k<j) 사각 부등식: \(C[a][c] + C[b][d] 더보기 이전 1 다음