[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)

인트로 +컴퓨터공학을 전공하셨거나 코딩 테스트를 준비하시는 분들은 한 번쯤 접해보셨을 동적 프로그램(DP, 동적 계획법)을 쉽게 이해하기 위해 작성한 글입니다. ★ 동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다. 이렇게 보면 동적 프로그래밍은 분할 정복이 동일하다고 생각할 수 있지만 해를 구하기 위해 쪼갠 "부분 문제"의 특성이 다르다. 분할 정복과 비교했을 때 동적 프로그래밍의 도드라지는 특성은 작게 쪼개진 "부분 문제"가 중복돼서 나타난다는 것이다. 이에 대해선 차차 알아보기로 하고 알기 쉽게 동적 프로그래밍을 이해해 보자. 동적 프로그래밍 (DP, 동적 계획법) 피보나치 수열을 예로 들어 동적 프로그래밍을 설명하..