Longest Common Subsequence1 DP, Dynamic Programming의 개념과 유형 DP, 즉 Dynamic Programming은 동적 프로그래밍이다. 동적 프로그래밍은 한 마디로 하나의 문제를 단 한 번만 풀도록 하는 알고리즘을 말한다. 동적 프로그래밍을 사용하기 위해서는 다음과 같은 조건을 만족해야 한다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 즉, 크고 어려운 문제가 있으면 그것을 먼저 작게 나누어서 해결한 뒤, 나중에 전체의 답을 구하는 것이 DP이다. 이 과정에서 '기억하여 이용한다'는 '메모이제이션(Memoization)'이 사용된다는 점에서 분할정복과 차이가 있다. 메모이제이션이란 이미 계산한 결과를 다시 계산하지 않도록 'Table'에 저장하여 필요 시 꺼내 이용하는 것을 말한다. DP 문제 해.. 2023. 7. 2. 이전 1 다음
