다이나믹 프로그래밍 (Dynamic Programming)

2022. 4. 9. 23:46· 이코테/다이나믹 프로그래밍
목차
  1. DP를 사용하기 위한 조건
  2. 분할 정복(Divide and Conquer)과의 차이점
  3. 메모이제이션과 DP
  4. 문제를 접근하는 방식

한창 백준 문제 풀 때 DP의 개념에 대해 정리한 글이다. 이번 글에서는 추가적으로 알게 된 것들만 정리해보자.

https://aodtns.tistory.com/16?category=993972

 

백준 1003번 - 피보나치 함수

피보나치 함수를 구현하는 문제이다. 하지만 일반적인 재귀함수를 이용하는 방법으로 풀면 시간 초과가 뜰 것이다. 이를 해결하기 위해서 동적 계획법에 대해 알아보자. 동적 계획법 (Dynamic Prog

aodtns.tistory.com

 

DP를 사용하기 위한 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 

 

분할 정복(Divide and Conquer)과의 차이점

분할 정복과 비슷한 느낌이지만 DP는 문제들이 서로 영향을 미치고 있다는 점이다.

예를 들어 퀵 정렬에서 Pivot이 자리를 변경해서 자리를 잡으면 그 Pivot의 위치는 바뀌지 않고 그 Pivot을 다시 처리하는 부분 문제는 존재하지 않는다. 합병 정렬에서도 마찬가지로 부분 문제를 쪼갠 뒤 정렬을 하면 그 부분 문제에 대해서 다시 처리하지 않는다.

 

메모이제이션과 DP

DP의 전형적인 형태는 Bottom Up 방식이다. 이 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 하며, 메모이제이션은 Top down 방식에 국한되어 사용되는 표현이다. 

DP와 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 그저 이전 결과를 기록해 놓는다는 넓은 개념이므로 DP와는 별도의 개념이다. 

 

 

문제를 접근하는 방식

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 DP를 사용하기 위한 조건을 생각해보고 부분 문제들의 중복 여부를 확인해보자.

일단 Top Down 형태로 코드를 작성한 뒤에 부분 문제에서 구한 답이 큰 문제에서도 적용될 수 있다면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.

 

저작자표시 (새창열림)
aodtns
aodtns
인생은 새옹지마
맹의 코딩 기록장인생은 새옹지마
aodtns
맹의 코딩 기록장
aodtns
전체
오늘
어제
  • 카테고리 (116)
    • BE (22)
      • JSP (6)
      • Spring Boot (12)
      • Node.js (1)
      • Docker (1)
      • JPA (1)
    • AI (12)
      • 머신 러닝(ML) (11)
      • 딥 러닝(DL) (1)
    • 네트워크 (7)
      • 네트워크 기본 (1)
      • AWS (6)
    • DB (1)
      • SQL (1)
    • FE (11)
      • HTML (4)
      • CSS (5)
      • JS (1)
      • React (1)
    • CS (1)
      • Back End (0)
      • 디자인패턴 & 방법론 (1)
      • 컴퓨터 구조 & 운영체제 (0)
    • VCS (1)
    • 기획(UI, UX) (1)
      • 소프트웨어 마에스트로 (1)
    • 이코테 (13)
      • 그리디 (1)
      • 구현 (1)
      • DFS, BFS (1)
      • 정렬 (7)
      • 이진 탐색 (1)
      • 다이나믹 프로그래밍 (1)
      • 최단 경로 (0)
      • 그래프 이론 (0)
      • 부록 (1)
    • 백준 문제풀이(파이썬) (44)
      • 기본 수학 1 (1)
      • 기본 수학 2 (4)
      • 재귀 (2)
      • 브루트 포스 (2)
      • 정렬 (0)
      • 백트래킹 (5)
      • 동적 계획법 1 (15)
      • 그리디 알고리즘 (3)
      • 정수론 및 조합론 (2)
      • 스택 (1)
      • 큐, 덱 (1)
      • 분할 정복 (4)
      • 이분 탐색 (2)
      • 우선순위 큐 (2)
    • 일상 (3)

블로그 메뉴

  • 💼 깃허브
  • 📄이력서

인기 글

최근 글

hELLO · Designed By 정상우.v4.2.1
aodtns
다이나믹 프로그래밍 (Dynamic Programming)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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