반응형 [PCCP] 알고리즘 - 동적계획법 1. 이론- Dynamic Programming은 전체 문제를 한 번에 해결하는 것이 아닌 작은 부분 문제들을 해결하여 이를 활용하여 전체 문제를 해결하는 것- DP 활용 조건 - Optimal Substructure(최적부분구조): 큰 문제를 작은 문제로 나누었을 떄 동일한 작은 문제 반복 등장 - Overlapping Subproblem(중복부분문제): 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성- 해결과정 1) 점화식 세우기 2) 메모이제이션 저장소 생성 3) 재귀함수 정의 && 종료조건- 최장증가부분수열(Long Increasing Subsequence) - 부분수열: 주어진 수열 중 전후 관계를 유지하며 일부를 뽑아 새로 만든 수열 - LIS: 부분.. 2024. 12. 15. 이전 1 다음 반응형
