์ดํƒœํ™
ํ™'story
์ดํƒœํ™
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (171)
    • TW (39)
    • AI (47)
      • ์ž์—ฐ์–ด ์ฒ˜๋ฆฌ (10)
      • Kaggle (2)
      • Machine Learning (26)
      • Computer Vision (0)
      • Deep Learning (0)
      • ROS2 (7)
    • Computer Science (29)
      • Data Structure (0)
      • Algorithm (18)
      • Computer Architecture (5)
      • SOLID (0)
      • System Programing (6)
    • LOLPAGO (10)
      • ํ”„๋ก ํŠธ์—”๋“œ (10)
      • ๋ฐฑ์—”๋“œ (0)
    • BAEKJOON (2)
    • React (5)
    • ์–ธ์–ด (8)
      • C++ (8)
    • GIT (0)
    • MOGAKCO (19)
    • ๋ฏธ๊ตญ ์—ฌํ–‰๊ธฐ (3)
    • etc. (7)
      • Blog (2)
      • ์ฝœ๋ผํ†ค (2)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • computerscience
  • ๋”ฅ๋Ÿฌ๋‹
  • ๊ฒฝ์‚ฌํ•˜๊ฐ•๋ฒ•
  • algorithm
  • baekjoon
  • Ai
  • LOLPAGO
  • tw
  • ROS2
  • ๋ฐฑ์ค€
  • NLP
  • ๋จธ์‹ ๋Ÿฌ๋‹
  • ๊ธฐ๊ณ„ํ•™์Šต
  • C++
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • react
  • ML
  • pytorch
  • computer architecture
  • kaggle

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

hELLO ยท Designed By ์ •์ƒ์šฐ.
์ดํƒœํ™

ํ™'story

[Algorithm] Dynamic Programming(1) - Warm Up
Computer Science/Algorithm

[Algorithm] Dynamic Programming(1) - Warm Up

2022. 11. 15. 10:53

๐Ÿค”Dynamic Programming

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์ด๋ž€ ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘์€๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ฒƒ์„ ๋งํ•ฉ๋‹ˆ๋‹ค.

 

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•˜๋Š” ๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

์ด๋ฒˆ ์‹œ๊ฐ„์—๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์ด ์–ด๋–ค ๊ฒƒ์ธ๊ฐ€์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

 

 

 

 

 

 

 

๐Ÿ”Ž  ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด

์ปดํ“จํ„ฐ๋ฅผ ๋ฐฐ์šด ์‚ฌ๋žŒ์ด๋ผ๋ฉด ํ•œ ๋ฒˆ์ฏค ํ’€์–ด๋ดค์„ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. (ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ์ž˜ ๋ชจ๋ฅด์‹œ๋Š” ๋ถ„์€ ํ•ด๋‹น ๋งํฌ๋ฅผ ์ฐธ๊ณ ํ•˜์‹œ๊ธธ ๋ฐ”๋ž๋‹ˆ๋‹ค.)

 

ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์€ Recursion์„ ์ด์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๐Ÿ‘‰ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ์ˆ˜๋„์ฝ”๋“œ

๋”๋ณด๊ธฐ
fib(n):
	if(n == 0)
    	return 0
    if(n == 1)
    	return 1
    return fib(n-1) + fib(n-2)

 

 

 

 

ํ•ด๋‹น ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” subproblem์˜ ์ •์˜๋ฅผ ํ†ตํ•ด ํ•ด๊ฒฐ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

Subproblem ์ •์˜

$T(n)$์„ ์œ„์˜ $fib(n)$์˜ ๋‹ต์„ ์–ป์„ ๋•Œ ๊นŒ์ง€ ํ•„์š”ํ•œ ์ด addition์˜ ํšŸ์ˆ˜๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋ ‡๋‹ค๋ฉด ์•„๋ž˜์™€ ๊ฐ™์€ recurrence relation์„ ์–ป์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

$$T(n) = T(n-1) + T(n-2) + 1,\; T(0) = T(1) = 0$$

 

ํ•ด๋‹น recurrennce relation์„ ํ•ด๊ฒฐํ•˜๋ฉด $T(n) ~ 1.618^n$์„ ์–ป์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๋งค์šฐ ๋А๋ฆฐ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

์ด๋Š” ์•„๋ž˜์˜ recursion tree๋ฅผ ํ†ตํ•ด ์ด์œ ๋ฅผ ํ™•์ธ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

recursion tree์—์„œ $F_3$์„ ํ™•์ธํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

์žฌ๊ท€์  ํ˜ธ์ถœ์„ ์ง„ํ–‰ํ•˜๋ฉด์„œ $F_3$๊ฐ€ ์ด 5๋ฒˆ ํ˜ธ์ถœ๋˜๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

์ฆ‰, ๊ฐ™์€ ํ•จ์ˆ˜๋ฅผ ์žฌ๊ท€๋ฅผ ์ง„ํ–‰ํ•˜๋Š” ๋™์•ˆ ๋ฐ˜๋ณตํ•ด์„œ ํ˜ธ์ถœํ•ด์•ผ ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋А๋ฆฐ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

 

์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์žฌ๊ท€ ํ˜ธ์ถœ์„ ์ง„ํ–‰ํ•˜๋ฉฐ ๊ฒฐ๊ณผ๋ฌผ์ด ๋‚˜์˜ฌ ๋•Œ๋งˆ๋‹ค ์ €์žฅํ•œ ๋’ค, ์ดํ›„์— ๊ฐ™์€ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด ์ €์žฅํ–ˆ๋˜ ๊ฒฐ๊ณผ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

 

 

๐Ÿ‘‰ ์ €์žฅ์„ ์ด์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•œ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด ์ˆ˜๋„์ฝ”๋“œ

๋”๋ณด๊ธฐ
global F[0..n] = {0, 1, null, ... null};
Fib(n):
	if (n == 0)
		return 0
	if (n == 1)
		return 1
	if F[n] == null
		F[n] = Fib(n-1) + Fib(n-2)
	return F[n]

 

 

 

์ด์™€ ๊ฐ™์ด ์žฌ๊ท€ํ•จ์ˆ˜์˜ ์ค‘๊ฐ„ ๊ฒฐ๊ณผ๋ฅผ ์ €์žฅํ•˜๋Š” ๊ธฐ๋ฒ•์„ memoization์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

๋˜ํ•œ recursion๊ณผ memoization์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐ๋ฒ•์„ dynamic programming์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

ํ•ด๋‹น ์ˆ˜๋„์ฝ”๋“œ์˜ time complexity๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

F[n]์˜ ๊ฐ’์ด null์ผ ๋•Œ๋งŒ ๋ง์…ˆ์„ ํ•œ ๋ฒˆ ์ˆ˜ํ–‰ํ•˜๋ฉด ํ•ด๋‹น ๊ฐ’์ด ๊ฒฐ์ •๋˜๋ฏ€๋กœ ์ด n๋ฒˆ์˜ ๋ง์…ˆ์„ ์ง„ํ–‰ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

์ €์žฅ ๋˜ํ•œ ์ด n๋ฒˆ ์ง„ํ–‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด time complexity๋Š” $O(n)$์ด ๋ฉ๋‹ˆ๋‹ค.

 

 

์ด๋ฅผ recrsion tree์™€ ์ €์žฅ๋œ ๋ฐฐ์—ด๋กœ ํ™•์ธํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

๐Ÿ”Ž Dynamic Programming์˜ ์ˆœ์„œ

Dynamic Programming์„ ํ†ตํ•ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์•„๋ž˜์˜ ์ˆœ์„œ๋ฅผ ๊ฑฐ์น˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

 

 

 

Dynamic programming ์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•

1. ๋ฌธ์ œ๋ฅผ ์ •ํ™•ํ•˜๊ฒŒ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.
2. ์ •์˜๋œ ๋ฌธ์ œ์— ๋Œ€ํ•œ subproblem ์„ ์ •์˜ํ•œ ๋’ค (์•ž ์˜ˆ์‹œ์—์„œ๋Š” $subproblem = F_n’ \,(n’ < n)$ ๊ตฌํ•˜๊ธฐ๊ฐ€ subproblem), subproblem ์„ ์ด์šฉํ•œ recurrence relation ์„ ์„ธ์›๋‹ˆ๋‹ค.
3. Memoizaion ์„ ์ด์šฉํ•˜์—ฌ recurrence relation ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.
  - ์ค‘๊ฐ„ ๊ฒฐ๊ณผ๋ฌผ๋“ค์„ ์ €์žฅํ•  data structure๋ฅผ ๊ณ ๋ฆ…๋‹ˆ๋‹ค. (๋ณดํ†ต n ์ฐจ์› array ์‚ฌ์šฉ.)
  - Subproblem ๋“ค ๊ฐ„์˜ dependency๋ฅผ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. (์˜ˆ : $F_n$ ์„ ๊ตฌํ•˜๋ ค๋ฉด ์–ด๋–ค subproblem์˜ ๋‹ต๋“ค์„ ๊ณ„์‚ฐํ•ด ๋†“์•„์•ผ ํ•˜๋Š”๊ฐ€?) 
  - Dependency ์— ๊ธฐ๋ฐ˜ํ•˜์—ฌ subproblem ๋“ค์˜ ๋‹ต์„ ๊ตฌํ•˜๋Š” ์ˆœ์„œ๋ฅผ ์ •ํ•ฉ๋‹ˆ๋‹ค..
4. Time complexity๋ฅผ ๋ถ„์„ํ•˜๊ณ  ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ž‘์„ฑํ•ฉ๋‹ˆ๋‹ค.

 

 

 

 

 

๋‹ค์Œ ํฌ์ŠคํŒ…์—์„œ๋Š” ์—ฌ๋Ÿฌ๊ฐ€์ง€ ์˜ˆ์‹œ๋ฅผ ํ†ตํ•ด DP๋ฅผ ๋” ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

๐Ÿ”Ž Reference

https://galid1.tistory.com/507

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ - Dynamic Programming(๋™์ ํ”„๋กœ๊ทธ๋ž˜๋ฐ)์ด๋ž€?

Dynamic Programming(๋™์ ๊ณ„ํš๋ฒ•) ์ด๋ž€ 1. Dynamic Programming(๋™์ ๊ณ„ํš๋ฒ•)์ด๋ž€?ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘์€๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ‘ธ๋Š” ๋ฌธ์ œ๋ฅผ ์ผ์ปซ๋Š” ๋ง์ž…๋‹ˆ๋‹ค. ๋™์  ๊ณ„ํš๋ฒ•์ด๋ž€ ๋ง ๋•Œ๋ฌธ์— ์–ด๋–ค ๋ถ€๋ถ„์—์„œ ๋™์ ์œผ๋กœ ํ”„๋กœ๊ทธ๋ž˜๋ฐ

galid1.tistory.com

 

'Computer Science > Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[Algorithm] Dynamic Programming(3) - Edit Distance(ํŽธ์ง‘๊ฑฐ๋ฆฌ)  (0) 2022.11.19
[Algorithm] Dynamic Programming(2) - LIS(Longest Increasing Subsequence)  (0) 2022.11.17
[Algorithm] ๋ถ„ํ• ์ •๋ณต(4) - Selection  (0) 2022.10.20
[Algorithm] ๋ถ„ํ• ์ •๋ณต(3) - Matrix Multiplication  (0) 2022.10.20
[Algorithm] ๊ทธ๋ž˜ํ”„ ์•Œ๊ณ ๋ฆฌ์ฆ˜(3) - DFS(2), Biconnected Graph  (0) 2022.10.13
    'Computer Science/Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [Algorithm] Dynamic Programming(3) - Edit Distance(ํŽธ์ง‘๊ฑฐ๋ฆฌ)
    • [Algorithm] Dynamic Programming(2) - LIS(Longest Increasing Subsequence)
    • [Algorithm] ๋ถ„ํ• ์ •๋ณต(4) - Selection
    • [Algorithm] ๋ถ„ํ• ์ •๋ณต(3) - Matrix Multiplication
    ์ดํƒœํ™
    ์ดํƒœํ™
    ๊ณต๋ถ€ํ•˜์ž ํƒœํ™์•„

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”