[알고리즘] Dynamic Programming (동적 계획법)

2016. 10. 14. 09:13·프로젝트 관련 조사/알고리즘
반응형

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95


동적 계획법

정의 : 어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법


최적 하위구조(Optimal Substructure)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다.

분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만, 동적 계획법은 이전 단계의 답에 의존적이다. 그래서 한번 푼 적 있는 문제는 다시 푸는 일이 없도록 테이블 등에 저장해둔다.


알고리즘

1. 문제를 부분 문제로 나눈다.

2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다.

3. 테이블에 저장되어 있는 부분 문제의 답을 이용하여 점차적으로 상위 부분의 문제의 답을 구한다.


동적 계획법의 활용

1. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의할 수 있다.


이것을 그냥 코드로 옮기면 다음과 같이 작성된다.

1
2
3
4
5
6
7
8
int Fibonacci(int n) {
    if (n > 1)
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    else if (n == 1)
        return 1;
    else
        return 0;
}
Colored by Color Scripter
cs

이 알고리즘의 수행시간은 으로 상당히 비효율적이다.

동적 계획법을 이용하여 이 알고리즘을 재구성해보자.

먼저 문제를 부분 문제로 나눈다.


은  과 의 합이다. 은 와 의 합이다.

그리고 은 과 의 합이다. 이로부터 이라는 문제를 ,, …, , , 의 하위구조로 나눌 수 있는 것을 알 수 있다.

두번째로 작은 부분의 답을 구한뒤 테이블에 저장한다.


 인덱스

 저장된 값

 0

 0

 1

 1

 2

 1

 3

 2

 4

 3

 5

 5

 6

 8

 ...

 ...

 n-2

 

 n-1

 

 n 



과 는 이미 정의되어 있는 값을 저장하면 되고, 부터는 테이블에 저장된 값을 이용하여 답을 구해 나간다. 이렇게 계속 구해나가면 의 값을 구할 수 있다.

이렇게 구한 피보나치 수의 시간 복잡도는 이다.

분할정복으로 구한 시간 복잡도는 이였지만 동적 계획법으로 구한 시간 복잡도는 로써 분할정복보단 떨어진다. 더 나은 기법을 알기 위해서가 아니라 알고리즘 설계 기법의 이해를 위한 것이므로 뭐가 더 우수한지는 논외로 하기로 한다.

반응형
저작자표시 (새창열림)

'프로젝트 관련 조사 > 알고리즘' 카테고리의 다른 글

[C++] [STL] deque 정리 및 예제  (0) 2016.10.15
[알고리즘] Backtracking (백트래킹)  (0) 2016.10.14
[알고리즘] Divide and Conquer (분할정복)  (0) 2016.10.14
[알고리즘] Greedy Algorithm (탐욕 알고리즘)  (0) 2016.10.14
[C++ STL] Header <algorithm> – 1. Sort 파헤치기 (1)  (0) 2016.10.10
'프로젝트 관련 조사/알고리즘' 카테고리의 다른 글
  • [C++] [STL] deque 정리 및 예제
  • [알고리즘] Backtracking (백트래킹)
  • [알고리즘] Divide and Conquer (분할정복)
  • [알고리즘] Greedy Algorithm (탐욕 알고리즘)
호레
호레
창업 / IT / 육아 / 일상 / 여행
    반응형
  • 호레
    Unique Life
    호레
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 법률
        • 기본
        • 개인정보보호법
        • 정보통신망법
        • 전자금융거래법
        • 전자금융감독규정
        • 신용정보법
        • 온라인투자연계금융업법
      • 창업
        • 외식업 관련
        • 임대업 관련
        • 유통업 관련
        • 세무 관련
        • 마케팅 관련
        • 기타 지식
        • 트렌드
        • Youtube
      • IT기술 관련
        • 모바일
        • 윈도우
        • 리눅스
        • MAC OS
        • 네트워크
        • 빅데이터 관련
        • A.I 인공지능
        • 파이썬_루비 등 언어
        • 쿠버네티스
        • 기타 기술
      • 퍼블릭 클라우드 관련
        • Azure
        • GCP
        • AWS
      • 정보보안 관련
        • QRadar
        • Splunk
        • System
        • Web
      • 기타
        • 세상 모든 정보
        • 서적
      • 게임 관련
        • 유니티
      • 부동산
      • 맛집 찾기
        • 강남역
        • 양재역
        • 판교역
        • ★★★★★
        • ★★★★
        • ★★★
        • ★★
        • ★
      • 결혼_육아 생활
        • 리얼후기
        • 일상
        • 육아
        • 사랑
        • Food
      • 영어
        • 스피킹
        • 문법
        • 팝송
        • 영화
      • K-컨텐츠
        • 드라마
        • 영화
        • 예능
      • 독서
      • 프로젝트 관련 조사
        • 시스템 구축
        • 로그 관련
        • 웹
        • APT
        • 모의 해킹
        • DB
        • 허니팟
        • 수리카타
        • 알고리즘
        • FDS
      • 기업별 구내 식당 평가
        • 한국관광공사
        • KT telecop
        • KT M&S
        • KT powertel
        • KT cs 연수원
        • 진에어
      • 대학 생활
        • 위드윈연구소
        • 진로 고민
        • 채용정보
        • 자동차
        • 주식
        • 악성코드
        • 게임 보안
      • 쉐어하우스
  • 블로그 메뉴

    • 홈
    • 게임 관련
    • IT 기술 관련
    • 태그
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    유니티
    맛집
    무역전쟁
    AWS
    런치
    판교맛집
    점심
    수제버거존맛
    판교
    수제버거
    수제버거맛집
    마케팅
    돈까스
    쥬쥬랜드
    대통령
    판교역
    이재곧죽습니다
    보안가이드
    복리후생
    상호관세
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
호레
[알고리즘] Dynamic Programming (동적 계획법)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.