다이나믹 프로그래밍

최적화 문제정의최적화 문제란 주어진 조건 하에서 목표를 최대화하거나 최소화하는 해를 찾는 문제를 말한다.구성요소목표함수: 최적화하려는 대상으로 이를 최대화하거나 최소화한다.제약조건: 최적화 과정에서 반드시 지켜야할 조건이다. 예를 들어 자원의 제한 등이다.변수: 최적화 대상이 되는 요소로 주로 생산량, 경로, 작업 스케줄 등이다.예시일상생활에서 지도를 따라 최단경로 찾기가 있다. 시작점에서 도착점까지의 이동거리, 시간, 비용 등을 최소화하려하기 때문이다. 금융에서는 포트폴리오 최적화, 가격 책정 최적화가 있고 운송 등에서 버스 배차시간 최적화 등이 있다.해결방법론최적화 문제의 특징에 따라 적용할 수 있는 방법들이 나뉜다. 최적화문제가 최적부분구조를 갖고 있는 경우에 분할정복 기법을 적용할 수 있다. 하지..

• format_list_bulleted Dev Notes/IT 취업 준비
• · 2024. 11. 29.

[알고리즘] 다이나믹 프로그래밍

의미최적부분구조 | 중복하위문제복잡한 문제를 간단한 하위 문제로 나눠 푸는 최적화기법 중에 하나다. 문제가 최적부분구조이고 하위문제들이 중복되는 경우에 동적 프로그래밍 전략을 적용할 수 있다. 최적부분구조란 문제의 최적 해결방법이 하위 문제들의 최적 해결방법으로 구성되는 구조다.용도배낭 문제와 동전 교환문제와 같은 최적화 문제, 최장공통 부분수열과 편집거리와 같은 문자열 처리, 최단경로 문제, 최소 비용경로와 같은 경로 찾기, 최적 자산 배분문제, 작업 스케줄링 문제 등 복잡한 문제를 효율적으로 해결하는 데에 쓰인다. vs 분할정복유사점문제를 나눠서 푼다작은 문제로 쪼갠다작은 문제도 최적화 문제다차이점최적화 문제 등 쪼개진 문제에서 중복된 문제들이 발생한다.구현전략탑다운큰 문제를 작은 문제로 쪼개서 푸는..

• format_list_bulleted Dev Notes/IT 취업 준비
• · 2024. 8. 19.

다이나믹 프로그래밍

다이나믹 프로그래밍이 필요한 이유공간을 희생해서 시간을 벌자.현실의 문제들 중에 그대로 컴퓨터로 해결하기에는 어려운 것들이 많다. 해를 구하는데 시간이 오래 걸리거나 메모리 공간을 매우 많이 필요한 경우가 그러하다. 그래도 메모리공간을 담보로 연산속도를 향상 할 수 있는 방법들이 존재한다. 다이나믹 프로그래밍이 그 중에 하나다.적용조건1. 큰 문제를 작은 문제로 나눌 수 있다.2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.기본 아이디어Memoization, DP table피보나치 수열을 예를 들자. 피보나치 수열은 연속 된 두개의 항이 그 다음 항의 합인 수열이다.f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1피보나치 수열은 재귀함수로 구현할 수 있다..

• format_list_bulleted Dev Notes/IT 취업 준비
• · 2024. 4. 5.