Algorithm Vision
동적 ν”„λ‘œκ·Έλž˜λ°Intermediate

동전 κ΅ν™˜ 문제

λͺ©ν‘œ κΈˆμ•‘μ„ λ§Œλ“œλŠ” 데 ν•„μš”ν•œ μ΅œμ†Œ 동전 개수λ₯Ό μ°ΎλŠ” 고전적인 DP λ¬Έμ œμž…λ‹ˆλ‹€. 더 μž‘μ€ κΈˆμ•‘μœΌλ‘œλΆ€ν„° μ†”λ£¨μ…˜μ„ κ΅¬μΆ•ν•˜μ—¬ 졜적 λΆ€λΆ„ ꡬ쑰λ₯Ό λ³΄μ—¬μ€λ‹ˆλ‹€. 화폐 μ‹œμŠ€ν…œ, μžλ™ 판맀기, μžμ› ν• λ‹Ήμ˜ μ‹€μš©μ  μ‘μš©μ΄ μžˆμŠ΅λ‹ˆλ‹€. λ³€ν˜•μœΌλ‘œλŠ” κ±°μŠ€λ¦„λˆμ„ λ§Œλ“œλŠ” λͺ¨λ“  κ°€λŠ₯ν•œ λ°©λ²•μ˜ 수λ₯Ό μ„ΈλŠ” 것이 μžˆμŠ΅λ‹ˆλ‹€.

#dynamic-programming#optimization#unbounded-knapsack

Complexity Analysis

Time (Average)

O(amount Γ— coins)

Expected case performance

Space

O(amount)

Memory requirements

Time (Best)

O(amount Γ— coins)

Best case performance

Time (Worst)

O(amount Γ— coins)

Worst case performance

Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← β†’ StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
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)
O(n)
dynamic-programmingmemoization
Start Learning

졜μž₯ 곡톡 λΆ€λΆ„ μˆ˜μ—΄ (LCS)

Intermediate

두 μ‹œν€€μŠ€μ— λ™μΌν•œ μˆœμ„œλ‘œ μ‘΄μž¬ν•˜λŠ” κ°€μž₯ κΈ΄ λΆ€λΆ„ μˆ˜μ—΄μ„ μ°ΎμŠ΅λ‹ˆλ‹€. 동적 ν”„λ‘œκ·Έλž˜λ°μ„ μ‚¬μš©ν•˜μ—¬ μ†”λ£¨μ…˜ ν…Œμ΄λΈ”μ„ κ΅¬μΆ•ν•©λ‹ˆλ‹€. DNA μ„œμ—΄ μ •λ ¬, 파일 차이 도ꡬ(diff), ν‘œμ ˆ 감지 λ“±μ˜ μ‘μš© ν”„λ‘œκ·Έλž¨μ΄ μžˆμŠ΅λ‹ˆλ‹€.

O(m Γ— n)
O(m Γ— n)
dynamic-programmingstrings
Start Learning
Back to 동적 ν”„λ‘œκ·Έλž˜λ°
Coin Change Problem - Algorithm Vision