haejun IT

백준 파도반 수열 풀이 백준 사이트 특성상 알고리즘의 분류가 되어 있어 DP 문제라는 것을 알 수 있지만 실전같은 경우는 어떻게 DP 문제라는 것을 유추할 수 있을까? 위의 문제에서 제시한 예시를 보면 이 전의 연산 결과에 따라서 다음의 연산 결과를 저장한다. 고로 작은 것을 통해 큰 것의 최적해를 찾는 것이기 때문에 DP를 사용하면 된다는 것을 유추할 수 있다. 또한 입력 N의 범위가 1

다이나믹 프로그래밍 (DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top-down, Bottom-up)으로 구성된다. 동적 계획법이라고도 부른다. 일반적으로 프로그래밍 분야에서 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 ..