알고리즘 5강 :: 동적 프로그래밍 알고리즘 원리, 연쇄 행렬 곱셈

알고리즘 5강을 보며 배운내용

 

 

앞에서 분할정복에 대해 2강에 들었는데

동적 프로그래밍 알고리즘도 방법, 원리 특징을 2강에 걸쳐 배운다

 

 

동적 프로그래밍 알고리즘 원리

1. 문제 크기가 작은 문제에 대해 해를 구하고,
2. 크기가 조금 더 큰 문제의 해를 단계적으로 구해가는
3. 상향식 접근 방법(bottom up)

작은 문제의 해는 테이블에 저장 해놓고 재사용

 

해를 구축하는 테이블을 이용한다고 해서 동적 프로그래밍이라 한다

 

소문제들 서로 독립적일 필요 없고, 중복되는 부분 존재한다

 

 

주로 최적화 문제

최적화 문제에 사용한다

최솟값, 최댓값, 피보나치 수열, 연쇄 행렬 곱셈 ...

 

 

사용하려면

최적성의 원리(Principle of optimality) 만족해야 동적 프로그래밍을 적용할 수 있다

=> 주어진 문제의 최적해는 소문제의 최적해로 구성된다

 

적용 과정

1. 최적성의 원리 성립되나?
2. 최적해를 제공하는 점화식 도출
3. 소문제부터 점화식 해를 구해서 테이블에 저장
4. 소문제 해를 이용해서 점차적으로 큰 상위 문제 해를 구한다

 

 

연쇄 행렬 곱셈

n개의 행렬을 연쇄적으로 곱할 때 최적의 곱셈 순서를 구하는 문제

최적의 곱셈 순서 => 최소 곱셈 횟수 갖는 순서

 

⌛ 시간 복잡도

O(n³)

 

점화식(어지럽다..)

 

알고리즘

점화식 그대로 가져다 써서 간단하다고 하시네...

 

 

정리해보면

처음부터 이해하기 어려우니 개념을 제대로 알고가자

연쇄 행렬 곱셉도 동적 프로그래밍 방법을 사용한다

즉 점화식을 생각해내는 것이 중요하고,

이처럼 점화식이 이미 널리 알려진 것이면

알고 있으면 혹은 검색할 수 있으면 사용할 수 있을 것 같다

 

아무튼 작은 문제로 큰 문제를 풀어갈 수 있도록

작은 문제의 결과를 저장

상위 문제에서 앞의 작은 문제 값을 이용해서 구하고 또 저장

이렇게 올라가며 진정 풀고 싶은 문제의 값을 구하는 방법

이게 동적 프로그래밍 방식

 

 

math by Jeswin Thomas #unsplash