[115일차]동적 프로그래밍

동적프로그래밍

동적 프로그래밍이란 유기적으로 연산한값이나 데이터를 저장하면서,
메모리에 할당을하며 연산 횟수를 줄이는 프로그래밍 기법이다.

한가지 예를들면 2의 n제곱을 구하는 연산에서,
2의 8제곱을 구할 때 2의 7제곱을 구했던 값이 데이터에 남아있다면,
2를 8번 곱할 필요가 없이 2의 7제곱한 값에다 * 2 라는 연산만 해주면된다.

이런식으로 2의 제곱을 불러와봤다.
총 5번의 계산을 했고, 이번엔 2의 6제곱을 구해보라고 해볼거다.

보다시피 자기는 계산 딱 한번했다고 나온다.
귀엽지않은가?

문제풀이로 dp를 많이 접할거다.
핵심은 데이터를 어떤방식으로 할당하면서 문제를 해결해나갈지 중점에 달려있다.
이름은 dynamic programing이지만 그다지 다이나믹하지않다는게 함정이다
memoziation으로도 많이불린다.

비교적 다른 예제들보다 간단한 예제를 직접 만들어보았다.
개념을 알때는 쉽게접해야하는법..
하지만 코딩테스트 문제들은 이렇게 귀엽지않다..ㅎ