파이썬 알고리즘 썸네일형 리스트형 Dynamic Programming 4: 배낭 문제 (백준 7579, 2629번 파이썬) Dynamic programming 개념을 설명할 때 피보나치 수열 말고도 가장 흔하게 언급되는 예시가 배낭 문제(knapsack problem)이다. 어느 정도 난이도가 있는 배낭 문제는 DP로 푸는 게 대부분이다. 배낭 문제를 처음 접해본 사람은 올바른 풀이를 떠올리기 정말 어렵다. 그러나 배낭 문제는 결국 사소한 문제 설정에서 차이가 있을 뿐 비슷한 유형의 문제를 풀다보면 동일한 패턴을 발견하게 된다. 결국 배낭 문제는 풀이 방식이 비슷하기 때문에 아예 풀이를 외울 정도까지 익숙해지는 게 좋다고 생각한다. 배낭 문제에 속하는 예시 몇 가지를 아래에서 살펴보자. 백준 7579번: 앱 문제 설정은 앞서 살펴본 11066번(파일 합치기)와 11049번(행렬 곱셈 순서)와는 다르다. 이전 문제는 어떤 연속.. 2023. 3. 29. 15:35 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 2: 재귀(top-down) vs. DP(bottom-up) (백준 11066, 1520, 1937번 파이썬) Dynamic Programming(DP) 개념을 처음 소개할 때 빠지지 않고 등장하는 게 피보나치 수열이다. 설명 글을 요악하면 다음과 같다. 1) 피보나치 수열을 재귀함수를 이용해 구한다. 2) 재귀함수로 구할 때 중복된 계산이 발생한다. 어차피 같은 답을 내놓는 연산을 여러 번 반복하니 불필요하고 비효율적이다. 3) 불필요한 연산을 방지하기 위해 memoization, 즉 DP 개념을 도입한다. 여기에 핵심이 있다. 우리는 같은 DP 문제에 대해 재귀로 풀 수도 있고, DP로도 풀 수 있다. 이유는 애초에 DP 문제가 다음 성질을 지니기 때문이다. 1) 큰 문제(마지막 항, f(n), 구하고자 하는 답, 현재 상태)를 작은 문제(초기값, 이전 상태, 직전 단계)에 의존하는 관계식으로 표현할 수 있다.. 2023. 3. 28. 15:42 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 다음
