๐ ๊ณต๋ถํ๋ ์ง์ง์ํ์นด๋ ์ฒ์์ด์ง?
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_28_๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ๋ณธ๋ฌธ
[์ด๊ฒ์ด ์ฝ๋ฉ ํ ์คํธ๋ค with Python]_28_๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
์ง์ง์ํ์นด 2022. 2. 9. 01:39220209 ์์ฑ
<๋ณธ ๋ธ๋ก๊ทธ๋ ใ์ด๊ฒ์ด ์ทจ์ ์ ์ํ ์ฝ๋ฉ ํ ์คํธ๋คใ ์ youtube๋ฅผ ์ฐธ๊ณ ํด์ ๊ณต๋ถํ๋ฉฐ ์์ฑํ์์ต๋๋ค>
https://www.youtube.com/watch?v=rWbjQphRE9A&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=28
1. ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
: ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ ์ ํ ์ฌ์ฉํ์ฌ ์ํ ์๊ฐ ํจ์จ์ฑ์ ๋น์ฝ์ ์ผ๋ก ํฅ์
: ์ด๋ฏธ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ (์์ ๋ฌธ์ )๋ ๋ณ๋์ ๋ฉ๋ชจ๋ฆฌ ์์ญ์ ์ ์ฅ (๋ค์ ๊ณ์ฐ X)
: ๋ ๊ฐ์ง ํ๋ค์ด(์์์ ์๋, ํํฅ์ ), ๋ณดํ ์ (์๋์์ ์, ์ํฅ์)์ผ๋ก ๊ตฌ์ฑ
: ๋์ ๊ณํ๋ฒ
: ์๋ฃ๊ตฌ์กฐ์์ ๋์ ํ ๋น์ ํ๋ก๊ทธ๋จ์ด ์คํ๋๋ ๋์ค์ ์คํ์ ํ์ํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๋ ๊ธฐ๋ฒ
=> ๋ค์ด๋๋ฏน์ ๋ณ๋ค๋ฅธ ์๋ฏธ ์์ด ์ฌ์ฉ
1. ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ (Optimal Substructure)
: ํฐ ๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ๋๋ ์ ์์ผ๋ฉฐ, ์์ ๋ฌธ์ ์ ๋ต์ ๋ชจ์ ํฐ ๋ฌธ์ ํด๊ฒฐ
2. ์ค๋ณต๋๋ ๋ถ๋ถ ๋ฌธ์ (Overlapping Subproblem)
: ๋์ผํ ์์ ๋ฌธ์ ๋ฅผ ๋ฐ๋ณต์ ์ผ๋ก ํด๊ฒฐ
2. ํผ๋ณด๋์น ์์ด
: ์ ํ์์ด๋ ์ธ์ ํ ํญ๋ค ์ฌ์ด์ ๊ด๊ณ์
: ๋ฐฐ์ด์ด๋ ๋ฆฌ์คํธ ์ด์ฉ
+) ๋จ์ ์ฌ๊ท ํจ์๋ ์ง์ ์๊ฐ ๋ณต์ก๋ ๊ฐ์ง๋ค
: ์ฌ๋ฌ๋ฒ ํธ์ถ, ์ค๋ณต๋๋ ๋ถ๋ถ!!
- python
# ์ฌ๊ท ํจ์ ๊ตฌํ
def fibo(x) :
if x == 1 or x == 2 :
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(6))
- c++
#include <bits/stdc++.h>
using namespace std;
// ํผ๋ณด๋์น ํจ์(Fibonacci Function)์ ์ฌ๊ทํจ์๋ก ๊ตฌํ
int fibo(int x) {
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
int main(void) {
cout << fibo(4) << '\n';
}
- java
import java.util.*;
public class Main {
// ํผ๋ณด๋์น ํจ์(Fibonacci Function)์ ์ฌ๊ทํจ์๋ก ๊ตฌํ
public static int fibo(int x) {
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2);
}
public static void main(String[] args) {
System.out.println(fibo(4));
}
}
3. ํผ๋ณด๋์น ์์ด ์๊ฐ ๋ณต์ก๋
: ์ธํ ํ๊ธฐ๋ฒ - θ(1.618....^N)
: ๋น ์ค ํ๊ธฐ๋ฒ - O(2^N)
4. ๋ฉ๋ชจ์ด์ ์ด์ (Memoization)
: ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ๊ตฌํ ๋ฐฉ๋ฒ
: ํ ๋ฒ ๊ณ์ฐํ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ๋ฉ๋ชจ
: ๊ฐ์ ๋ฌธ์ ๋ค์ ํธ์ถํ๋ฉด, ๋ฉ๋ชจํ ๊ฒฐ๊ณผ ๊ฐ์ ธ์ด
: ๊ฐ ๊ธฐ๋กํ๊ธฐ = ์บ์ฑ (cashing)
: ์ด์ ์ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ฅผ ์ผ์์ ์ผ๋ก ๊ธฐ๋กํด ๋๋ ๋์ ๊ฐ๋
: ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ๊ตญํ๋์ง X
5. ํ๋ค์ด vs ๋ณดํ ์
- ํ๋ค์ด (๋ฉ๋ชจ์ด์ ์ด์ )
: ํํฅ์
- ๋ณดํ ์
: ์ํฅ์
: ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ์ ํ์ ์ธ ํํ
: ๊ฒฐ๊ณผ ์ ์ฅ์ฉ ๋ฆฌ์คํธ๋ DP ํ ์ด๋ธ
+) ํ๋ค์ด ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
- python
# ๋ฉ๋ชจ์ด์ ์ด์ d = [0] * 100 def fibo(x) : if x == 1 or x ==2 : return 1 # ์ด๋ฏธ ๊ณ์ฐ if d[x] !=0 : return d[x] # ์์ง ๊ณ์ฐ x d[x] = fibo(x - 1) + fibo(x - 2) return d[x] print(fibo(99))
- c++
#include <bits/stdc++.h>
using namespace std;
// ํ ๋ฒ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ์ด์ ์ด์
(Memoization)ํ๊ธฐ ์ํ ๋ฐฐ์ด ์ด๊ธฐํ
long long d[100];
// ํผ๋ณด๋์น ํจ์(Fibonacci Function)๋ฅผ ์ฌ๊ทํจ์๋ก ๊ตฌํ (ํ๋ค์ด ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ)
long long fibo(int x) {
// ์ข
๋ฃ ์กฐ๊ฑด(1 ํน์ 2์ผ ๋ 1์ ๋ฐํ)
if (x == 1 || x == 2) {
return 1;
}
// ์ด๋ฏธ ๊ณ์ฐํ ์ ์๋ ๋ฌธ์ ๋ผ๋ฉด ๊ทธ๋๋ก ๋ฐํ
if (d[x] != 0) {
return d[x];
}
// ์์ง ๊ณ์ฐํ์ง ์์ ๋ฌธ์ ๋ผ๋ฉด ์ ํ์์ ๋ฐ๋ผ์ ํผ๋ณด๋์น ๊ฒฐ๊ณผ ๋ฐํ
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
int main(void) {
cout << fibo(50) << '\n';
}
- java
import java.util.*;
public class Main {
// ํ ๋ฒ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ์ด์ ์ด์
(Memoization)ํ๊ธฐ ์ํ ๋ฐฐ์ด ์ด๊ธฐํ
public static long[] d = new long[100];
// ํผ๋ณด๋์น ํจ์(Fibonacci Function)๋ฅผ ์ฌ๊ทํจ์๋ก ๊ตฌํ (ํ๋ค์ด ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ)
public static long fibo(int x) {
// ์ข
๋ฃ ์กฐ๊ฑด(1 ํน์ 2์ผ ๋ 1์ ๋ฐํ)
if (x == 1 || x == 2) {
return 1;
}
// ์ด๋ฏธ ๊ณ์ฐํ ์ ์๋ ๋ฌธ์ ๋ผ๋ฉด ๊ทธ๋๋ก ๋ฐํ
if (d[x] != 0) {
return d[x];
}
// ์์ง ๊ณ์ฐํ์ง ์์ ๋ฌธ์ ๋ผ๋ฉด ์ ํ์์ ๋ฐ๋ผ์ ํผ๋ณด๋์น ๊ฒฐ๊ณผ ๋ฐํ
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
public static void main(String[] args) {
System.out.println(fibo(50));
}
}
+) ๋ณดํ ์ ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
- python
d = [0]*100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1) :
d[i] = d[i-1] + d[i-2]
print(d[n])
- c++
#include <bits/stdc++.h>
using namespace std;
// ์์ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ๊ธฐ ์ํ DP ํ
์ด๋ธ ์ด๊ธฐํ
long long d[100];
int main(void) {
// ์ฒซ ๋ฒ์งธ ํผ๋ณด๋์น ์์ ๋ ๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ณ์ฐ
// ํผ๋ณด๋์น ํจ์(Fibonacci Function) ๋ฐ๋ณต๋ฌธ์ผ๋ก ๊ตฌํ(๋ณดํ
์
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ)
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
cout << d[n] << '\n';
}
- java
import java.util.*;
public class Main {
public static long[] d = new long[100];
public static void main(String[] args) {
// ์ฒซ ๋ฒ์งธ ํผ๋ณด๋์น ์์ ๋ ๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ณ์ฐ
// ํผ๋ณด๋์น ํจ์(Fibonacci Function) ๋ฐ๋ณต๋ฌธ์ผ๋ก ๊ตฌํ(๋ณดํ
์
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ)
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
System.out.println(d[n]);
}
}
+) ํผ๋ณด๋์น ์์ด : ๋ฉ๋ชจ์ด์ ์ด์ ๋์ ๋ถ์
: ์ด๋ฏธ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฅ
: ๋ฉ๋ชจ์ด์ ์ด์ ์ด์ฉํ๋ฉด ํผ๋ณด๋์น ์์ด ์๊ฐ ๋ณต์ก๋๋ O(N)
- python
d = [0] * 100
def fibo(x) :
print("f(" + str(x) + ")", end = " ")
if x == 1 or x == 2 :
return 1
if d[x] != 0 :
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
fibo(6)
6. ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ VS ๋ถํ ์ ๋ณต
: ๋ชจ๋ ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ ๊ฐ์ง ๋ ์ฌ์ฉ
( ํฐ ๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ๋๋๊ณ , ์์ ๋ฌธ์ ์ ๋ต์ ๋ชจ์์ ํฐ ๋ฌธ์ ํด๊ฒฐ)
: ์ฐจ์ด์ ์ ๋ถ๋ถ ๋ฌธ์ ์ ์ค๋ณต
( ๋ค์ด๋๋ฏน์ ๊ฐ ๋ถ๋ถ ๋ฌธ์ ๋ค์ด ์๋ก ์ํฅ ๋ฏธ์น๋ฉฐ ๋ถ๋ถ ๋ฌธ์ ์ค๋ณต)
( ๋ถํ ์ ๋ณต์์๋ ๋์ผํ ๋ถ๋ถ ๋ฌธ์ ๊ฐ ๋ฐ๋ณต์ ๊ณ์ฐ X)
EX) ๋ถํ ์ ๋ณต ์์ ํต ์ ๋ ฌ
: ๊ธฐ์ค ์์ PIVOT ์ด ์๋ฆฌ๋ฅผ ๋ณ๊ฒฝํด์ ์๋ฆฌ ์ก์ผ๋ฉด, ๊ทธ ๊ธฐ์ค ์์์ ์์น๋ ๋ฐ๋์ง ์์
7. ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ์ ๊ทผ
: ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ์ ํ ํ์
: ๊ทธ๋ฆฌ๋, ๊ตฌํ, ์์ ํ์์ธ๊ฐ
: ์ฌ๊ท๋ก ๋นํจ์จ์ ์ธ ์์ ํ์ ํ๋ก๊ทธ๋จ ์์ฑ -> ํ๋ค์ด ๋ฌธ์ ์ฌ์ฉ