전체태그 보기

#동적프로그래밍 (3개의 포스트)

hecklebot
재귀와 동적 프로그래밍 재귀적 해법의 접근법 재귀적 해법은 부분문제에 대한 해법을 통해 완성된다. 가장 흔하게 사용되는 방법은 상향식(botton-up), 하향식(top-down), 반반(half-half)이 있다. 1. 상향식 접근법 하나 풀고 그걸로 다음 거 풀고 다음 거 풀고.. 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는다. 가장...
doontagi
오버플로 문제를 푸는 과정, 또는 정답에서 경우의 수를 구해야 하는 경우 구하고자 하는 정수의 수가 너무 커져서 int형의 size 4바이트를 초과해서 오버헤드가 발생할 수 있다. 이 경우 재귀 함수의 반환값에 모듈로 연산을 처리해 주면, 수의 크기가 훨씬 줄어들어 오버헤드를 방지할 수 있다. 예제 - 삼각형 위의 최대 경로 수 이 전에 풀었...
doontagi
문제 정의 지금까지 배워왔던 브루트 포스, 분할 정복, 일반 DP, 최적화 DP 모두 문제 해결 과정에서 가장 어려우면서 핵심적인 부분이 큰 문제를 적절한 부분 문제로 나누는 작업이다. 단순 LIS 문제는 수열이 한 개만 주어져서 부분 문제와 상위 문제들 사이의 관계가 비교적 명확하게 드러났는데, JLIS의 경우 수열이 두 개이기 때문에 그 과정이 ...