목록DP (1)

코딩은 마라톤

동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer)

1. 정의 동적계획법 (DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함 Memoization : 프로그램 실행 시 이전 계산 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 일반적으로 재귀함수로 구현한다. 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않는다...
CS/알고리즘 2023. 12. 24. 18:47
이전 Prev 1 Next 다음