-
[Python] ์์ด๊ณผ ๋์ ๊ณํ๋ฒ์๋ฃ๊ตฌ์กฐ 2022. 10. 4. 20:40
๐ ๋ฌธ์ : ์ ๋ ฅ ๊ธธ์ด n์ผ ๋ n ์ดํ์ ์์ ๋ํด์ ๋ชจ๋ ์์ด์ ๊ฒฝ์ฐ๋ฅผ ๋์ดํด๋ณด์์ค.
def combinations(s): if len(s) < 2: return s res = [] for i,c in enumerate(s): res.append(c) for j in combinations(s[:i]+s[i+1:1]): res.append(c+j) return res
์ฝ๋ ๋ถ์ :
์์ด์ ๋ฌธ์ ๋ฅผ ์ฌ๊ทํจ์๋ก ํ์ด๋ธ ์ฝ๋์ด๋ค.
์ฌ๊ทํจ์ํ๋๊น ๋ ์ค๋ฅธ ๊ฒ์ด ๋์ ๊ณํ๋ฒ์ด๊ธฐ ๋๋ฌธ์ ๋์ ๊ณํ๋ฒ์ ๋ํด ๊ณต๋ถํ๋๋ก ํ๊ฒ ๋ค.
๋์ ๊ณํ๋ฒ ์ด๋ ๋ณต์กํ ๋ฌธ์ ๋ฅผ ๊ฐ๋จํ ์ฌ๋ฌ ํ์ ๋ฌธ์ ๋ค๋ก ๋๋ ์ ํธ๋ ๊ฒ์ผ๋ก ํ์ ๋ฌธ์ ๊ฐ ์๋ก ์ข ์์ฑ์ ๊ฐ์ง ๋ ์ฌ์ฉ๋๋ค.
(Divide and Conquer๊ณผ ๋งค์ฐ ์ ์ฌํ๋ค)
๋์ ๊ณํ๋ฒ์ ๋ชจ๋ ํ์ ๋ฌธ์ ๋ฅผ ํ๊ณ ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํด ๋๋ฉด์ ๋ค์ ๋จ๊ณ์ ๋ฌธ์ ๋ฅผ ํธ๋๋ฐ ์ฌ์ฉํ๋ค.
-> ๋ฌธ์ ๋ฅผ ๋ค์ ํ์ง ์๊ณ table์ ์ ์ฅ๋ ๊ฐ์ ์ด์ฉํ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๊ฐ ์ค์ด๋ ๋ค!
๊ทธ๋ฆฌ๊ณ ๋ง์ง๋ง์ผ๋ก ๋์ ๊ณํ๋ฒ์ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๋ฐ์ ธ ๋ณด๊ธฐ ๋๋ฌธ์ ํญ์ optimalํ solution์ ์ป๋๋ค.
์ด์ฒ๋ผ ๋์ ๊ณํ๋ฒ์ ํ์ฉํ๋ฉด ๋ ๊ฐ๋จํ๊ฒ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
๊ทธ๋ ๋ค๋ฉด ๋์ ๊ณํ๋ฒ์ด ๋ญ์ง ๋ ์์ธํ ์์๋ณด๊ฒ ๋ค!
๋์ ๊ณํ๋ฒ
์์ ๊ฐ๋ตํ๊ฒ ์ค๋ช ํ ๊ฒ์ฒ๋ผ ๋์ ๊ณํ๋ฒ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ ์ ํ๊ฒ ์ฌ์ฉํด ์ํ ์๊ฐ์ ๋จ์ถ์ํค๋ ๋ฐฉ๋ฒ์ด๋ค.
๋์ ๊ณํ๋ฒ์ ๋ณดํต ๋๊ฐ์ง ๋ฐฉ์ (ํ๋ค์ด๊ณผ ๋ณดํ ์ )์ผ๋ก ๊ตฌํํ๋ค.
๋์ ๊ณํ๋ฒ์ ๋ฌธ์ ๊ฐ ์๋ ์กฐ๊ฑด์ ๋ง์กฑํ ๋ ์ฌ์ฉํ ์ ์๋ค.
1. ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ(Optimal Substructure)
: ํฐ ๋ฌธ์ ๋ฅผ ์์ ๋ฌธ์ ๋ก ๋๋ ์ ์์ผ๋ฉฐ ์์ ๋ฌธ์ ๋ค์ ๋ต์ ๋ชจ์ ํฐ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
2. ์ค๋ณต๋๋ ๋ถ๋ถ ๋ฌธ์ (Overlapping Subproblem)
: ๋์ผํ ์์ ๋ฌธ์ ๋ฅผ ๋ฐ๋ณต์ ์ผ๋ก ํด๊ฒฐํด์ผ ํ๋ค.
(1) ํผ๋ณด๋์น ์์ด
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ f(n)์ด๋ผ๊ณ ํ ๋, 4๋ฒ์งธ ํผ๋ณด๋์น ์ f(4)๋ฅผ ๊ตฌํ๋ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ๋ค.
f(4) = f(3) + f(2) = f(2) + f(1) + f(2)
์ด๋ฌํ ์ ํ์์ ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํด ๊ฐ๋จํ๊ฒ ํ ์ ์๋ค. ์ด๋ ์์ด์ ๋ฐฐ์ด์ด๋ ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํด ํํํ๋ค.
def fibo(x): if x==1 or x==2: return 1 return fibo(x-1) + fibo(x-2)
-> ์ฌ๊ท ํจ์๊ฐ ๋ฌดํ๋ฃจํ๋ฅผ ๋์ง ์๊ณ ํน์ ์ง์ ์์ ๋ฉ์ถ ์ ์๋๋ก ํ๋ ๊ฒ์ด ํต์ฌ!!
ํ์ง๋ง ๋จ์ ์ฌ๊ท ํจ์๋ก ํผ๋ณด๋์น ์์ด์ ํด๊ฒฐํ๋ฉด ์ง์ ์๊ฐ ๋ณต์ก๋(O(2^n))๋ฅผ ์ง๋๊ฒ ๋๋ค. (์ค๋ณต๋๋ f๊ฐ์ด ์ฌ๋ฌ๋ฒ ๋ค์ ๊ณ์ฐ๋ ์ ์๊ธฐ ๋๋ฌธ)
-> ์ด ๊ฒฝ์ฐ n์ด ์กฐ๊ธ๋ง ์ปค์ง๋๋ผ๋ ์ฐ์ฐ๋์ด ๊ธ๊ฒฉํ๊ฒ ์ฆ๊ฐํ๋ค.
-> ๋ฐ๋ผ์ ๋ณ๋์ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ฐ๋ฆฌ๊ฐ ํด๊ฒฐํ f๊ฐ์ ์ ์ฅํด์ผ ์ค๋ณตํด์ ๊ณ์ฐํ์ง ์๊ฒ ๋๋ค.
๊ทธ๋ ๋ค๋ฉด ํผ๋ณด๋์น๋ฅผ ๋์ ๊ณํ๋ฒ์ ์ฌ์ฉํด ํ์ด๋ณด์!!
๋จผ์ ๋์ ๊ณํ๋ฒ์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ๋ค์ ํ๋ฒ์ฉ ์ค๋ช ํ๊ณ ๋์ด๊ฐ๊ฒ ๋ค.
โ Memoization
๋ฉ๋ชจ์ด์ ์ด์ ์ ๋์ ๊ณํ๋ฒ์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ ์ค ํ๋์ด๋ค.
ํ๋ฒ ๊ณ์ฐํ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ๋ฉ๋ชจํ๊ธฐ ๋๋ฌธ์ ๊ฐ์ ๋ฌธ์ ๋ฅผ ๋ค์ ํธ์ถํ ๊ฒฝ์ฐ ๋ฉ๋ชจํ๋ ๊ฒฐ๊ณผ๋ฅผ ๊ทธ๋๋ก ๊ฐ์ ธ์จ๋ค.
โ ํ๋ค์ด (ํํฅ์)
ํฐ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์์ ๋ฌธ์ ๋ค์ ์ฌ๊ท์ ์ผ๋ก ํธ์ถํ๋ฉฐ (๊ตฌํ ๊ณผ์ ์์ ์ฌ๊ทํจ์๋ฅผ ์ด์ฉํ๋ค.) ์์ ๋ฌธ์ ๋ค์ด ๋ชจ๋ ํด๊ฒฐ๋์์ ๋ ์ค์ ๋ก ํฐ ๋ฌธ์ ์ ๋ํ ๋ต๊น์ง ์ป์ ์ ์๋๋ก ์ฝ๋๋ฅผ ์์ฑํ๋ค.
์ด๋ ๋ฉ๋ชจ์ด์ ์ด์ ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
โ ๋ณดํ ์ (์ํฅ์)
์๋์ชฝ์์๋ถํฐ ์์ ๋ฌธ์ ๋ฅผ ํ๋์ฉ ํด๊ฒฐํ๋ฉฐ ๋จผ์ ๊ณ์ฐํ๋ ๋ฌธ์ ๋ค์ ๊ฐ์ ํ์ฉํด ๊ทธ ๋ค์์ ๋ฌธ์ ๋ค๊น์ง ํ์ฉํ๋ค.
๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํด์ ๊ตฌํ
- ๋ณดํต ๋์ ๊ณํ๋ฒ์ผ๋ก ๋ง์ด ํ์ฉํ๋ ๋ฐฉ์์ ๋ณดํ ์ ๋ฐฉ์์ด๋ค.
# ํ๋ฒ ๊ณ์ฐํ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ๋ชจ์ด์ ์ด์ ํ๊ธฐ ์ํ ๋ฆฌ์คํธ์ ์ด๊ธฐํ d = [0]*100 # ์ด 100๊ฐ์ ์์๋ฅผ ๊ฐ์ง๋ ํ๋์ ๋ฆฌ์คํธ ์ด๊ธฐํ # ํ๋ค์ด ๋์ ๊ณํ๋ฒ def fibo(x): 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]
์ ํ๋ค์ด ์ฝ๋๋ฅผ ๋ณด๋ฉด ๊ธฐ์กด์ ์ ํ์์ ์ด์ฉํด์ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฒ์ ๊ฐ์ง๋ง, d๋ผ๋ ๋ฆฌ์คํธ๋ฅผ ์์ฑํ๋ฉด์ ๋ฉ๋ชจ์ด์ ์ด์ ์ ํด์ค ๊ฒ์ ๋ณผ ์ ์๋ค!!
# ๋ณดํ ์ ๋ฐฉ์์ ๋์ ๊ณํ๋ฒ ์ฝ๋ # ์์ ๊ณ์ฐ๋ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ๊ธฐ ์ํด DP ํ ์ด๋ธ ์ด๊ธฐํ d = [0]*100 # ์ฒซ ๋ฒ์งธ ํผ๋ณด๋์น ์์ ๋ ๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1 d[1]=1 d[2]=1 #ํผ๋ณด๋์น ํจ์ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๊ตฌํ for i in range(3,n+1): d[i] = d[i-1]+d[i-2] print(d[n])
๋ณดํ ์ ๋ฐฉ์์ ์ฌ๊ทํจ์๊ฐ ์๋๋ผ ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ ์ ํ์์์ ์ฐ์ด๋ ์ข ๋ฃ์กฐ๊ฑด์ ์ฌ์ฉํ๋ ๊ฒ์ด ์๋๋ผ, ๋ฐ๋ณต๋ฌธ ์์ ์ ์ ๋จผ์ ์ด๊ธฐํํ๋ค. ์์ ๋ฌธ์ ๋ถํฐ ํด๊ฒฐํ ๋ค์, ๊ทธ ์์ ๋ฌธ์ ๋ฅผ ์กฐํฉํด ํฐ ๋ฌธ์ ๋ค์ ์ฐจ๋ก๋ก ํด๊ฒฐํด๋๊ฐ๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
๋ฉ๋ชจ์ด์ ์ด์ ์ ์ด์ฉํ๋ ๊ฒฝ์ฐ, ํผ๋ณด๋์น ์์ด ํจ์์ ์๊ฐ ๋ณต์ก๋๋ O(N)์ด๋ค.
'์๋ฃ๊ตฌ์กฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] DFS , BFS (1) (0) 2022.10.05 [Python] ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ (0) 2022.10.05 ์ฝ๋ฉํ ์คํธ ๊ธฐ์ด (1) 2022.10.05 [Python] ํํ๊ณผ ๋ฆฌ์คํธ (0) 2022.10.04 [Python] ๋ฌธ์์ด ๋ฉ์๋ (0) 2022.09.29