โ๊ณต๋ถํ๊ฒ ๋ ๊ณ๊ธฐ
โก๏ธ ๋ค์์ฃผ ์๊ณ ๋ฆฌ์ฆ ์คํฐ๋ ์ฃผ์ ์ธ DP ์ ๋ํด์ ์์ต
โ๏ธ๊ณต๋ถํ ๋ด์ฉ
1๏ธโฃ Dynamic Programming ์ด๋?
โก๏ธ ๋์์ธ ํจ๋ฌ๋ค์ ์ค ํ๋๋ก ์กํ ๋ฌธ์ ๋ฅผ ์ฌ๋ฌ ๊ฐ์ ์์ ๋ถ๋ถ ๋ฌธ์ ๋ก ๋๋์ด ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด๋ค.
โก๏ธ Dynamic ์ '๊ธฐ์ตํ๊ธฐ' & Programming ์ '๋๋๊ธฐ' ์ ๋ ์๊ฐํ๋๊ฒ ์ข๋ค.
โก๏ธ ๋์ ๊ณํ๋ฒ์ ํต์ฌ์ธ Memorization(DP ๊ตฌํ ๋ฐฉ๋ฒ ์ค ํ๋) ์ ์ด์ฉํด ๋น ๋ฅธ ์๋๋ก ์ต์ ์ ํด๋ฅผ ์ฐพ์๋ด๋ ๊ฒ์ด ๋ชฉํ์ด๋ค.
2๏ธโฃ DP ๋ฌธ์ ๊ฐ ์ฑ๋ฆฝํ ์กฐ๊ฑด
โก๏ธ DP ๋ฌธ์ ๊ฐ ์ฑ๋ฆฝํ๊ธฐ ์ํด์๋ ํฌ๊ฒ 2๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผํ๋ค.
โ ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ (Optional Substructure)
โก๏ธ ์์ ๋ฌธ์ ๋ฅผ ํ์ ๋ฌธ์ ๋ก ๋๋ ์ ์์ผ๋ฉฐ, ํ์ ๋ฌธ์ ์ ๋ต์ ๋ชจ์์ ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
โก ์ค๋ณต๋๋ ๋ถ๋ถ ๋ฌธ์ (Overlapping Subproblem)
โก๏ธ ๋์ผํ ์์ ๋ฌธ์ ๋ฅผ ๋ฐ๋ณต์ ์ผ๋ก ํด๊ฒฐํด์ผํ๋ค. (๋จ ๊ฐ์ ๋ฌธ์ ๋ ๊ตฌํ ๋๋ง๋ค ์ ๋ต์ด ๊ฐ๋ค.)
3๏ธโฃ ๋ฌธ์ ์์ (ํผ๋ณด๋์น)
โก๏ธ DP ๋ฅผ ์ดํดํ๊ธฐ ์ํด ๊ฐ์ฅ ์ข์ ๋ฌธ์ ๋ ํผ๋ณด๋์น ์์ด์ด๋ค.
public class Simple {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
// ๋จ์ ์ฌ๊ท
static int fibo(int x) {
if( x ==1 || x==2) return 1;
return fibo(x-1) + fibo(x-2);
}
}

โก๏ธ โ f(6) ์ ํฐ ๋ฌธ์ ๊ฐ ๊ณ์ ์ชผ๊ฐ์ ธ ์์์ง๊ณ , โก f(3) ์ f(2) ๋ฑ์ด ๊ณ์ํด์ ๋ฐ๋ณต๋๋ฏ๋ก DP ์กฐ๊ฑด์ ๋ชจ๋ ํ์ธํ๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
4๏ธโฃ DP ๊ตฌํ ๋ฐฉ์
โก๏ธ DP ๊ตฌํ ๋ฐฉ์์๋ ํฌ๊ฒ Top-down (ํํฅ์) ๊ณผ Donw-top (์ํฅ์) ์ด ์๋ค.
โ Top-down (ํํฅ์)
โก๏ธ ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ํ์ ๋ฌธ์ ๋ฅผ ์ฌ๊ท์ ์ผ๋ก ํธ์ถํ ๋ค์, ์์ ๋ฌธ์ ์์ ํด๊ฒฐํ ๊ฐ์ ์ ์ฅ ๋ฐ ๊ธฐ์ต (Memorization) ํ๋ค. ์ดํ ์ฌ๋ผ๊ฐ๋ฉด์ ํด๋น ๊ฐ๋ค์ ์ฌํ์ฉํ๋ฉด์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค.
โก๏ธ ๊ตฌ์กฐ์ ์ผ๋ก๋ ์ดํดํ๊ธฐ ์ฝ์ง๋ง, ์ฌ๊ท ํธ์ถ์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ Stack Overflow ์ ๋ฌธ์ ๊ฐ ๋ฐ์ํ ์ ์๋ค.
public class Topdown {
// Memorization ์ ์ํ ๋ฐฐ์ด ์์ฑ
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
// Top-down
static int fibo(int x) {
if( x ==1 || x==2) return 1;
// (1) ์ด๋ฏธ ํด๊ฒฐํ ๋ฌธ์ ๋ฉด ์ฌํ์ฉ
if(dp[x] != 0) return dp[x];
// (2) ํด๊ฒฐ๋์ง ์์ ๋ฌธ์ ๋ฉด ์ฌ๊ท ํธ์ถํ์ฌ ๊ฐ ์ ์ฅ
dp[x] = fibo(x-1) + fibo(x-2);
return dp[x];
}
}
โก Donw-top (์ํฅ์)
โก๏ธ ์ ํ์ ์ธ DP ์ ํํ๋ก, ๊ฐ์ฅ ์์ ๋ฌธ์ ๋ถํฐ ์์ํ์ฌ ๊ฐ์ ์ ์ฅํ๊ณ ์ด ๊ฐ๋ค์ ๊ธฐ๋ฐ์ผ๋ก ๋ค์ ๋ฌธ์ ๋ฅผ ์์ฐจ์ ์ผ๋ก ํด๊ฒฐํ๋ ๋ฐฉ์.
โก๏ธ ๊ตฌ์กฐ ํน์ฑ์ ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ๋ค.
public class Bottomup {
// ๊ฐ์ ์ ์ฅํ๊ธฐ ์ํ ๋ฐฐ์ด ์์ฑ
static int[] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
dp = new int[n+1];
System.out.println(fibo(n));
}
// Bottom-up
static int fibo(int x) {
dp[1] =1;
dp[2] =1;
// ๋ฐ๋ก ๋ฐ๋ก ๊ฐ์ ์ ์ฅ & ์ฌ์ฉ
for(int i=3; i<x+1; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[x];
}
}
โ๏ธ ์ ์ฉ ์์ผ๋ณธ ์์
๐ง ์ถ๊ฐ๋ก ๊ถ๊ธํ ์
1๏ธโฃ ๋ถํ ์ ๋ณต๊ณผ ๋ค๋ฅธ ์
โก๏ธ ๋ถํ ์ ๋ณต์ ๋ฌธ์ ๋ฅผ ๋ถํ ํ์ ๋ ๊ฒน์น๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ์ง ์์ง๋ง, DP ๋ ๊ฒน์น๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ค. ๊ฒน์น๋ ๋ฌธ์ ๋ฅผ ๊ณ์ ํ๊ฒ๋๋ฉด ๋นํจ์จ์ ์ด๋ฏ๋ก Memorization ๊ธฐ๋ฒ์ ํตํด ๋ฌธ์ ๋ฅผ ๋ฐ๋ก ์ ์ฅํด๋์๋ค๊ฐ ๊ฒน์น๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ฉด ๋ฐ๋ก ๊ฐ์ ์ฌ์ฉํ๋ค.

โก๏ธ ํ์ ๋ฌธ์ ๊ฐ ๋ ๋ฆฝ์ ์ด์ง ์๊ณ ์ค๋ณต์ด ๋๋ ๊ฒฝ์ฐ์๋ DP ๊ฐ ๋ ๋์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ง, ๋ถํ ์ ๋ณต ๋ฌธ์ ์์๋ ํ์ ๋ฌธ์ ๋ ๋ ๋ฆฝ์ ์ผ๋ก ๊ตฌ์ฑ๋์ด์๊ธฐ ๋๋ฌธ์ ๋ฐ๋ณต์ ์ผ๋ก ๊ณ์ฐ์ด ๋์ง ์๋๋ค.
๐ ์ฐธ๊ณ
[์๊ณ ๋ฆฌ์ฆ] ๋์ ๊ณํ๋ฒ DP (Dynamic Programming) ์ ๋ฆฌ (Java)
๋์ ๊ณํ๋ฒ Dynamic Programming ๋์ ๊ณํ๋ฒ์ ํ๋ก๊ทธ๋๋ฐ ๋ํ ๋ฌธ์ ์ ๊ฐ์ฅ ์์ฃผ ์ถํํ๋ ๋์์ธ ํจ๋ฌ๋ค์ ์ค ํ๋๋ก, ์ด๋ฆ๋ง ๊ฐ์ง๊ณ ๋ ๋ฌด์์ ์๋ฏธํ๋์ง ์ ์ ์ ์๊ธฐ ๋๋ฌธ์ ๊ฐ์ฅ ๋ง์ ์คํด๋ฅผ
loosie.tistory.com
[Java]๋์ ๊ณํ๋ฒ(Dynamic Programming)
*๋์ ๊ณํ๋ฒ(Dynamic Programming) ->๋์ ๊ณํ๋ฒ์ด๋ ํน์ ๋ฒ์๊น์ง์ ์ต์ ํด(์์ ๋ฌธ์ )๋ฅผ ๊ตฌํ๊ธฐ ์ํ์ฌ ๋ค๋ฅธ ๋ฒ์๊น์ง์ ์ต์ ํด(ํ์ ๋ฌธ์ )๋ฅผ ์ด์ฉํ์ฌ ํจ์จ์ ์ผ๋ก ํด๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ ์ค๊ณ ๊ธฐ
sskl660.tistory.com
'Algorithm ๐ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| ์ด๋ถ ํ์ ๐ (Binary Search) (0) | 2023.04.17 |
|---|---|
| ๊ทธ๋ํ๐ (Graph) (0) | 2023.03.21 |
| ๊น์ด ์ฐ์ ํ์ (DFS) & ๋๋น ์ฐ์ ํ์ (BFS ) (0) | 2023.01.15 |
| [๐จ ์ปค๋ฎค๋ฌ๋/7๊ธฐ/Java] ] ๊ฐ์ฅ ํฐ ์ (Bubble Sort) (0) | 2022.11.02 |
| [๐จ ์ปค๋ฎค๋ฌ๋/7๊ธฐ/Java] ๊ธฐ์ง๊ตญ ์ค์น (Greedy Algorithm) (0) | 2022.10.26 |