본문 바로가기

Algorithm/문제 해결법1

DP- 동적 계획법 - DP란?DP는 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미한다. 알고리즘의 분류로 넣긴 했으면 이는 사실 방법론이라고 하는 게 더 맞는 것 같다. 이름의 뜻이 뭔가 깊은 의미가 담겨 있어 보이지만, 그냥 멋있어서 지은 이름이므로 이름과 해당 방법에 연관이 있다는 생각은 버리는 것이 좋다. - 왜 쓰나요?결론부터 말하자면 최적화다. 후에 설명될 Momozation 기법을 사용하여 처음 값을 보관해놓고 이를 활용하는 방식이기 때문에 같은 연산을 여러 번 반복할 필요가 없어 최적화에 용이하다. - 언제 쓰나요?DP를 적용해보기 위해서는 2가지 조건이 필요하다.1. 겹치는 소문제작은 문제로 나누었을 때, 중복되는 부분이 없이 각 소문제의 결과를 활용할 수 없다면 DP를 적용하기 어렵다.2... 2023. 8. 15.

이전 1 다음

티스토리툴바