알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다. 대표적인 문제 세 가지 : 막대기 자르기, 최장 공통 부분 수열, 0/1 배낭 1. 막대기 자르기 일단 막대기부터 잘라봅시다. 하나의 긴 막대기가 있는데 막대기 조각마다 가격이 다릅니다. 막대기를 적절하게 잘라서 가장 가격이 높게 만들어야 합니다. 길이(i) 0 1 2 3 4 5 6 7 8 9 10 가격(Pi) 0 1 5 8 9 10 17 17 20 24 30 예를 들면 길이가 4인 막대기를 자를..
