DP, Dynamic Programming 동적 계획법 알고리즘과 예제

알고리즘
2024. 4. 26. 20:03
목차
  1. 동적 계획법이란?
  2. 피보나치 수를 구하는 함수에 DP알고리즘 적용하기
  3. DP 알고리즘 구현하는 방식
728x90

동적 계획법이란?

 

크기가 크거나 복잡한 문제를 효율적으로 풀기위해 작거나 간단한 어러개의 문제로 나눠서 푸는 방법으로, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.

입력 크기가 작은 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계기법으로 프로그램 성능의 향성을 기대할 수 있다.


피보나치 수를 구하는 함수에 DP알고리즘 적용하기

 

  1. 문제를 부분 문제로 분할
    • fibonacci(0) = 0, fibonacci(1) = 1
    • fibonacci(n) =  fibonacci(n-1) + fibonacci(n-2) (n>=2)
  2.  
  3. 가장 작은 부분 문제부터 해를 구한다.
  4. 부분문제들의 해를 테이블에 저장하고 이를 이용하여 상위 문제의 해를 구한다.

메모제이션은 위 과정의 3번과 같이 부분 문제들의 해를 메모리에 저장하는 기법으로 동적 계획법 알고리즘에서 핵심이 되는 기술이므로 중요한 개념이다.


DP 알고리즘 구현하는 방식

 

1. recursive 방식

함수의 호출을 이용한 재귀적 방법이다.
재귀적 구조는 엄청난 중복호출이 발생할 수 있으므로 내부에 시스템 호출 스택을 사용하는 overhead가 발생할 수 있다.

def fibo(n):
if n<2:
return n
else:
return fibo(n-1) + fibo(n-2)

 

2. iterative 방식

반복문을 이용한 반복적 방법
Memoziation을 반복적 구조에 사용하여 DP알고리즘을 구현하는 거이 위의 재귀적 구조에 비해 실행속도와 성능면에서 보다 효율적.
반복문을 이용하여 작은 값부터 상위로 값을 구해나간다.

def fibo(n):
f = [0,1]
for i in range(2, n+1):
f.append(f[i-1] + f[i-2])
return f[n]
728x90

'알고리즘' 카테고리의 다른 글

[이코테] 미로탈출 (파이썬)  (0) 2024.06.29
[파이썬] 큐  (0) 2024.04.30
Memoization 개념, 재귀  (0) 2024.04.26
  1. 동적 계획법이란?
  2. 피보나치 수를 구하는 함수에 DP알고리즘 적용하기
  3. DP 알고리즘 구현하는 방식
'알고리즘' 카테고리의 다른 글
  • [이코테] 미로탈출 (파이썬)
  • [파이썬] 큐
  • Memoization 개념, 재귀
hapBday
hapBday
hapBday
개발자로 성장하기 위한 기록들
hapBday
전체
오늘
어제
  • 분류 전체보기 (199)
    • CS (12)
      • 컴퓨터네트워크 (11)
      • 운영체제 (0)
      • 분산 시스템 (0)
      • 데이터베이스 (1)
    • Spring (45)
      • Spring 핵심 원리 (13)
      • Spring MVC (15)
      • Spring DB (12)
      • Spring Security (4)
    • JPA (14)
    • 알고리즘 (30)
      • 프로그래머스 (6)
      • 백준 (20)
    • Design Pattern (0)
    • 언어 (5)
      • JAVA (5)
    • ASAC 웹 풀스택 (38)
      • Spring Boot (21)
      • React (0)
      • DevOps (8)
    • 트러블슈팅 (14)
    • DevOps (5)
      • Docker (5)
    • ETC (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • github

공지사항

인기 글

태그

  • CORS
  • 3-layerd 아키텍쳐 패턴
  • JPA
  • docker
  • Java
  • basicerrorcontroller
  • spring security
  • 구현
  • docker best practices
  • MVC
  • jwt
  • docker workflow
  • currency control
  • multi-stage
  • s-lock
  • 프로그래머스
  • x-lock
  • aws lambda
  • 백준
  • spring boot
  • Session
  • 김영한
  • 티스토리챌린지
  • S3
  • 인프런
  • CSRF
  • 오블완
  • Spring
  • cookie
  • 트랜잭션

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
hapBday
DP, Dynamic Programming 동적 계획법 알고리즘과 예제
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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