[알고리즘] 동적계획법

Posted by 백창
2015.10.22 14:47 자료구조&알고리즘/개념

# 동적계획법


 동적계획법은 분할정복법과는 정반대의 방식을 이용하여 문제를 해결한다. 동적계획법은 문제를 더 작은 문제로 분할한다는 점에서는 분할정복법과 비슷하지만 여기서는 작은 문제를 먼저 해결하고 저장하고 다른 계산에 그 저장된 결과를 이용한다.


 동적계획법은 상향식 접근 방법(bottom-up)이다. 계획이란 해답을 구축하는데 배열을 사용함을 의미한다.



# 예시


 파스칼의 삼각형이 비슷한 예시가 되겠다.


 원하는 결과를 얻기까지 결과값들을 배열에 저장하여 그 값을 다음 계산에 이용한다.


int bin(int n, int k){

index i, j;

int B[0..n][0,,k];


for( i = 0 ; i <= n ; i++ ){

for( j = 0 ; j <= min( i , k ) ; j++ ){

if( j == 0 || j == i )

B[i][j] = 1;

else

B[i][j] = B[i-1][j-1] + B[i-1][j];

}

}


return B[n][k];

}


'자료구조&알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] 동적계획법  (0) 2015.10.22
[알고리즘] 분할정복법  (0) 2015.10.12
[정렬 알고리즘] 시간복잡도  (0) 2015.10.12
Map 과 HashMap 차이  (0) 2014.12.26
[개념] 리스트  (0) 2014.11.04
이 댓글을 비밀 댓글로