명이나물 라이브러리

DP(다이나믹 프로그래밍), 중복 계산을 줄여주는 알고리즘이번에는 코딩테스트에서 자주 나오는 DP, 다이나믹 프로그래밍에 대해 공부했다.처음에는 이름부터 어렵게 느껴졌다.Dynamic Programming이라는 이름만 보면 뭔가 복잡한 알고리즘처럼 보이지만, 핵심은 생각보다 단순하다.한 번 계산한 값은 다시 계산하지 말고 저장해두었다가 재사용하는 것이다.즉, DP는 이전에 구한 작은 문제의 답을 이용해서 더 큰 문제의 답을 구하는 방식이다.1. DP란 무엇인가?DP는 Dynamic Programming의 줄임말이고, 한국어로는 동적 계획법이라고 부른다.하지만 이름보다 중요한 것은 개념이다.DP의 핵심은 다음과 같다. 핵심 개념설명저장한 번 구한 답을 배열 등에 저장한다재사용같은 계산이 필요할 때 다시 계..