동적 프로그래밍Intermediate

0/1 배낭 문제

주어진 무게와 가치를 가진 아이템을 선택하여 무게 제한 내에서 총 가치를 최대화하는 고전적인 동적 프로그래밍 문제입니다. 각 아이템은 한 번만 선택할 수 있습니다(0/1). 자원 할당, 포트폴리오 최적화, 화물 적재 등의 응용이 있습니다.

#dynamic-programming#optimization#combinatorial#np-complete

Complexity Analysis

Time (Average)

O(n × W)

Expected case performance

Space

O(n × W)

Memory requirements

Time (Best)

O(n × W)

Best case performance

Time (Worst)

O(n × W)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 16•Section 16.2

Items (weight:value, comma-separated)

Capacity (1-100)

Example Problems:

How it works

• 0/1 Knapsack: maximize value within capacity limit
• Dynamic programming approach
• O(n × W) time, O(n × W) space complexity
• Each item can be taken once or not at all
• Formula: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in 동적 프로그래밍

행렬 체인 곱셈

Advanced

행렬 체인의 최적 괄호화를 찾아 스칼라 곱셈 횟수를 최소화합니다. CLRS 15장의 대표적인 동적 프로그래밍 문제입니다.

O(n³)

O(n²)

dynamic-programmingoptimization

Start Learning

피보나치 (동적 프로그래밍)

Beginner

중복 계산을 피하기 위해 동적 프로그래밍을 사용하여 피보나치 수를 효율적으로 계산합니다. 지수 시간 재귀 솔루션을 선형 시간 알고리즘으로 변환하는 메모이제이션의 힘을 보여줍니다. 동적 프로그래밍 개념에 대한 고전적인 소개입니다.

O(n)

dynamic-programmingmemoization

Start Learning

최장 공통 부분 수열 (LCS)

Intermediate

두 시퀀스에 동일한 순서로 존재하는 가장 긴 부분 수열을 찾습니다. 동적 프로그래밍을 사용하여 솔루션 테이블을 구축합니다. DNA 서열 정렬, 파일 차이 도구(diff), 표절 감지 등의 응용 프로그램이 있습니다.

O(m × n)

dynamic-programmingstrings

Start Learning

Back to 동적 프로그래밍