코딩테스트

골드 3해당 문제는 백준에서 Dynamic Programming을 사용해서 푸는 문제입니다.이 문제를 정리하는 이유는 DP를 사용하기 위한 조건을 찾아내지 못하였기 때문입니다.DP를 사용하기 위한 조건은 다음과 같습니다.1\. Overlapping Subproblems

와일드 카드 해당 문제는 종만북에서도 언급되어 있다는 문제이고, 제가 현재 보고 있는 책에서도 나와있는 문제입니다. 기본 방식으로는 완전탐색을 사용해서 문제를 푸는데 그렇게 했을 경우 시간복잡도가 굉장히 높게 나옵니다.

DP중에서도 대표적인 문제로 꼽히는 문제가 있는데, 타일 채우기, 계단 오르기, 배낭 채우기등이 있습니다.그 중 하나인 배낭 채우기(Knapsack Problem)을 알아보겠습니다.