Demi 님 뭐하시는분이신가요??


전 대학생입니다 우연히 이 사이트에 오게 되었는데 하나부터 열까지 프로그래밍언어를 포함한 컴퓨터 이론에 대해서 깊이 알고계신거같네요..

현직에 종사하시는 개발자 선배님이신가요? 존경합니다

한가지 질문드릴것.. Dynamic programming 에 대해 간략히 설명해주시면 감사하겠습니다

  • 알 수 없는 사용자

조회수 296


1 답변


Demi는 아니지만..

Dynamic programming은 문제 해결 시 최적의 방식으로 해결한다는 방법론을 말하고, 보통 재귀 함수를 사용할 때 이전에 사용했던 작업을 반복할 때가 있는데, 이 작업결과를 저장해놓고, 반복작업시에 저장한 데이터를 재활용하여 연산횟수를 줄이는데 사용하곤 합니다.

피보나치 함수를 예를 들어 아래와 같을 때

int f(int n)
{
    if(n == 0 || n == 1)
        return n;
    else
        return f(n-1) + f(n-2);
}

일때 f(4)를 구하기 위해 아래와 같은 연산을 하는데

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

여기서 f(2)를 2번 호출을 합니다. 이 때 f(2)의 결과를 미리 저장해놓고, f(2)를 호출할 때 저장한 결과물을 그대로 사용하는게 동적계획법의 한 예입니다.

  • 2016년 02월 02일에 작성됨
    프론트앤드, 임베디드 초보개발자입니다

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close