백준 알고리즘 썸네일형 리스트형 Dynamic Programming 4: 배낭 문제 (백준 7579, 2629번 파이썬) Dynamic programming 개념을 설명할 때 피보나치 수열 말고도 가장 흔하게 언급되는 예시가 배낭 문제(knapsack problem)이다. 어느 정도 난이도가 있는 배낭 문제는 DP로 푸는 게 대부분이다. 배낭 문제를 처음 접해본 사람은 올바른 풀이를 떠올리기 정말 어렵다. 그러나 배낭 문제는 결국 사소한 문제 설정에서 차이가 있을 뿐 비슷한 유형의 문제를 풀다보면 동일한 패턴을 발견하게 된다. 결국 배낭 문제는 풀이 방식이 비슷하기 때문에 아예 풀이를 외울 정도까지 익숙해지는 게 좋다고 생각한다. 배낭 문제에 속하는 예시 몇 가지를 아래에서 살펴보자. 백준 7579번: 앱 문제 설정은 앞서 살펴본 11066번(파일 합치기)와 11049번(행렬 곱셈 순서)와는 다르다. 이전 문제는 어떤 연속.. 2023. 3. 29. 15:35 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 다음
