Dynamic Programming 이란?

분류.

 

수학적 최적화 기법 그 자체 혹은 컴퓨터 프로그래밍 기법의 일종입니다.

 

정의.

복잡하고 큰 문제를 단순하고 작은 하위 문제로 쪼개어 문제를 해결하고 그것들을 저장한 뒤 필요할 때마다 가져와 사용해  문제를 해결하는 기법입니다.

 

장점.

중복되는 계산을 피해 계산횟수를 줄일 수 있습니다. 하위문제가 기하급수적으로 커지는 경우에 적용하기 좋습니다.

문제를 해결하기 위한 모든 방법을 검토하고 그 중 최적의 풀이를 찾아내는데에 유리합니다.

 

활용.

최장부분공통수열

벨만-포드 알고리즘

다익스트라 알고리즘

플로이드워셜 알고리즘

부분집합 합 알고리즘

배낭문제

 

DP 활용한 코딩테스트 문제 풀이들

퇴사 (링크)

파도반수열 (링크)

LIS문제들 (링크)

정수삼각형 (링크)

. . .

 

순간 헷갈린 부분

1. Dynamic Programming Language와는 상관 없는 질문이었다.

 

응당 프론트엔드 개발하면 Javascript 기초 개념 Dynamic Programming Language의 특징은? 질문이 나올 것 같아 기계적으로 글의 제목 질문 보고 처음에 든 생각이 이 개념이었습니다. 

Dynamic Programming은 개념 자체를 전체 프로그램 구성 잡으며 생각하거나 코딩테스트 문제 풀며 줄여 불러 DP DP 하다보니.. 

둘은 다른 개념!