반응형 16291 파이썬(Python) 분할정복 개념과 예제 - 백준 1629 분할정복 알고리즘이란? 분할정복은 여러 알고리즘 한번에 해결할 수 없는 문제를 잘게 쪼개서 해결할 만한 부분문제들로 만든다음에, 그 문제들을 해결하면서 정복해가며 문제를 해결하는 방법으로 보통 재귀함수로 구현합니다. 문제를 잘게 쪼개서 해결한다고 하니까 동적 계획법(DP, 다이나믹 프로그래밍)이랑 똑같은것이 아닌가? 라고 생각이 들것입니다. 확실히 DP의 하향식 접근법이랑 유사한 부분이 많지만 부분문제가 중복되지 않는 부분에서 차이가 있습니다. DP문제, 예를 들어 피보나치 수열 구하기 등은 부분문제가 중복돼서 다른 상위 문제를 푸는데 해결되기 때문에 메모리제이션 기법을 사용합니다. (예를 들어 a10을 구하기 위해서 부분문제를 a9 a8로 나눴을때, a8의 부분문제 a7은 a9를 해결하는데도 쓰이므로 .. 2023. 9. 24. 이전 1 다음
