DP๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ 2๊ฐ์ง๊ฐ ์กด์ฌํ๋ค. Top-downBottom-up๊ตฌํ์ฌ๊ท๋ฐ๋ณต๋ฌธ์ ์ฅ๋ฐฉ์๋ฉ๋ชจ์ด์ ์ด์
ํ๋ทธ๋ ์ด์
Memoization - ํ์ํ ๋ถ๋ถ ๋ฌธ์ ๋ค๋ง ๊ตฌํ๊ธฐ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ํ ๋ฒ ๊ตฌํ์ผ๋ฉด ๋ ๊ตฌํ์ง ์๋๋ก (์ค๋ณต์ฐ์ฐ ์๋๋ก) cache์ ์ ์ฅํด๋๊ณ ๋ค์์ ๊ฐ๋ค ์ฐ๊ธฐ Tabulation - ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ๋ฏธ๋ฆฌ ๋ค ๊ตฌํด๋๋ฉด ํธํ๋ค.ํ
์ด๋ธ์ ์ฑ์๊ฐ๋ค → ํ๋ทธ๋ ์ด์
๋ฌธ์ ๋ฅผ ์ชผ๊ฐ์ ์์ ๋ฌธ์ ๋ถํฐ ๊ตฌํด๊ฐ๋ฉฐ ์๋ ๋ฌธ์ ์ ๋ต์ ๊ตฌํ๋ ๋ฐฉ์์ด๋ค.ํต์ฌ์ ์ ํ์์ ์ฐพ๊ณ , ํ
์ด๋ธ๋ง ์ ์ ์ํ๋ฉด ํ๋ฆฐ๋ค. (์ ํ์ ์ฐพ๊ธฐ๊ฐ ์ฝ์ง ์๋ค๋๊ฒ ๋ฌธ์ ใ
ใ
) ์ด์ ๋ฌธ์ ๋ค์ ํ์ด๋ณด์. ๋ฌธ์ ํ์ดhttps://koreatstm.tistory.com/148https://koreatstm.tistory.com/149https:/..
๐ฏ์๊ณ ๋ฆฌ์ฆ/BOJ
https://www.acmicpc.net/problem/10844๊ท์น์ ๋จผ์ ์ฐพ์๋ณด์๋ณธ์ธ์ A4์ฉ์ง์ ๊ทธ๋ ค๊ฐ๋ฉฐ ๊ท์น์ ์ฐพ์๋ณด์๋ค.์ธ๋ฑ์ค๋ฅผ 0๋ถํฐํด์ ์
๋ ฅ์ด ์ต๋ 100์ด๊ธฐ์, 100ํ 10์ด๋ก ๋ง๋ค์ด๋ณธ๋ค๋ฉด, ์๋ ์ฌ์ง๊ณผ ๊ฐ์ด ๋์จ๋ค.์จ๋ณด๋ ๊ท์น์ด ๋ณด์ธ๋ค.1ํ์ ๋ชจ๋ ๊ฐ์ด 1์ด๊ณ , 2ํ๋ถํฐ๋ ํน๋ณํ ๊ท์น์ด ์๊ธด๋ค.ํ์ดํ๋ก ํ์ํด ๋์๋ฏ 0์ด์ ๊ฐ์ ์ด์ ํ์ 1์ด์ ๊ฐ์ด๊ณ ,9์ด์ ๊ฐ์ ์ด์ ํ์ 8์ด์ ๊ฐ์์ ์ ์ ์๋ค.๋ํ ๊ฐ์ด๋ฐ ๊ฐ๋ค์ ์๋ฅผ๋ค์ด 3ํ 3์ด์ด๋ผ๊ณ ํ๋ฉด, ๊ทธ ๊ฐ์ 2ํ2์ด๊ณผ 2ํ4์ด์ ๊ฐ์ ํฉ์์ ์ ์ ์๋ค.์ด์ ํ๋ทธ๋ ์ด์
์ผ๋ก ํ์ด๋ณด์ n=int(input())cache = [[0]* 10 for _ in range(101)]for i in range(1,101): for j i..
https://www.acmicpc.net/problem/11726๊ท์น์ ๋จผ์ ์ฐพ์๋ณด์๋ณธ์ธ์ A4์ฉ์ง์ ๊ทธ๋ ค๊ฐ๋ฉฐ ๊ท์น์ ์ฐพ์๋ณด์๋ค.์ฆ, ์ ์ ํ์๋ ๋ด์ฉ๊ณผ ๊ฐ์ ๋ฐฉ์์ด๋ค.https://koreatstm.tistory.com/148 [๋ฐฑ์ค/Python] 2748:ํผ๋ณด๋์น ์ 2https://www.acmicpc.net/problem/2748n=int(input())def func(n): if n==0: return 0 if n==1: return 1 else: return func(n-1)+func(n-2)print(func(n))์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.์บ์ฑ์ ์ํด์ ์ค๋๊ฑธ๋ฆฌ๊ณ , ์๊ฐ๋ณต์ก๋๋ ์์ฒญ ๋๊ธฐ์ ์๊ฐ์ด๊ณผ๊ฐkoreatstm.tistory.com์ด์ฒ๋ผ f(n) = f(n-1) + f(n-2)์ ๊ท์น์ด๋ค.์ด์ ..
https://www.acmicpc.net/problem/11051์ด๊ธฐ์ฝ๋n, k = map(int,input().split())def fun(n,k): if k==n or k==0: return 1 else: return fun(n-1,k-1)+fun(n-1,k)print(fun(n,k)%10007)์๊ฐ์ด๊ณผ๋๋ค์ฌ๊ท(๋ฉ๋ชจ์ด์ ์ด์
)import sysn, k = map(int,input().split())sys.setrecursionlimit(10**7)cache = [[0]*1001 for _ in range(1001)]def fun(n,k): if cache[n][k]: # 0์ด ์๋ ์๋ผ๋ฉด return cache[n][k] if k==n ..
https://www.acmicpc.net/problem/2748n=int(input())def func(n): if n==0: return 0 if n==1: return 1 else: return func(n-1)+func(n-2)print(func(n))์๊ฐ์ด๊ณผ๊ฐ ๋๋ค.์บ์ฑ์ ์ํด์ ์ค๋๊ฑธ๋ฆฌ๊ณ , ์๊ฐ๋ณต์ก๋๋ ์์ฒญ ๋๊ธฐ์ ์๊ฐ์ด๊ณผ๊ฐ ๋๋ ๊ฒ์ด๋ค,์ฐ๋ฆฌ๋ ์ค๊ฐ์ ์ฅ์ธ ์บ์ฑ์ ์ฌ์ฉํด์ผํ๋ค.ํ๋ทธ๋ ์ด์
n=int(input())cache = [0] * 100for i in range(100): if i==0: cache[i]= 0 if i==1: cache[i]= 1 else: cache[i]= cache[..
https://www.acmicpc.net/problem/11399 11399๋ฒ: ATM ์ฒซ์งธ ์ค์ ์ฌ๋์ ์ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ๊ฐ ์ฌ๋์ด ๋์ ์ธ์ถํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ Pi๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ Pi ≤ 1,000) www.acmicpc.net [Code] n=int(input()) sums=0 arr=list(map(int, input().split())) for i in range(n): for j in range(i+1,n): if arr[i]>arr[j]: arr[i],arr[j]= arr[j],arr[i] for i in range(1,n+1): sums += sum(arr[0:i]) print(sums)
์ฝ์
์ ๋ ฌ์ ์ด๋ฏธ ์ ๋ ฌ๋ ๋ฐ์ดํฐ ๋ฒ์์ ์ ๋ ฌ๋์ง ์์ ๋ฐ์ดํฐ๋ฅผ ์ ์ ํ ์์น์ ์ฝ์
์์ผ ์ ๋ ฌํ๋ ๋ฐฉ์์ด๋ค. ์๊ฐ ๋ณต์ก๋๋ O(n^2) ํต์ฌ ์ ํ ๋ฐ์ดํฐ๋ฅผ ํ์ฌ ์ ๋ ฌ๋ ๋ฐ์ดํฐ ๋ฒ์ ๋ด์์ ์ ์ ํ ์์น์ ์ฝ์
ํ๋ ๊ฒ์ด ์ฝ์
์ ๋ ฌ์ ํต์ฌ์ด๋ค. ์ฝ์
์ ๋ ฌ์ ์ํ ๋ฐฉ์ 1. ํ์ฌ index์ ์๋ ๋ฐ์ดํฐ ๊ฐ์ ์ ํํ๋ค. 2. ํ์ฌ ์ ํํ ๋ฐ์ดํฐ๊ฐ ์ ๋ ฌ๋ ๋ฐ์ดํฐ ๋ฒ์์ ์ฝ์
๋ ์์น๋ฅผ ํ์ํ๋ค. 3. ์ฝ์
์์น๋ถํฐ index์ ์๋ ์์น๊น์ง shift ์ฐ์ฐ์ ์ํํ๋ค. 4. ์ฝ์
์์น์ ํ์ฌ ์ ํํ ๋ฐ์ดํฐ๋ฅผ ์ฝ์
ํ๊ณ index++ ์ฐ์ฐ์ ์ํํ๋ค. 5. ์ ์ฒด ๋ฐ์ดํฐ์ ํฌ๊ธฐ๋งํผ index๊ฐ ์ปค์ง ๋๊น์ง, ์ฆ ์ ํํ ๋ฐ์ดํฐ๊ฐ ์์ ๋๊น์ง ๋ฐ๋ณตํ๋ค. ์ถ๊ฐ์ ์ผ๋ก ์ด์งํ์์ ์ฌ์ฉํ๋ฉด ์๊ฐ ๋ณต์ก๋๋ฅผ ์ค์ผ ์ ์๋ค.
์ ํ ์ ๋ ฌ์ ๋์ ๋ฐ์ดํฐ์์ ์ต๋๋ ์ต์ ๋ฐ์ดํฐ๋ฅผ ๋ฐ์ดํฐ๊ฐ ๋์ด๋ ์์ผ๋ก ์ฐพ์๊ฐ๋ฉฐ ์ ํํ๋ ๋ฐฉ๋ฒ. ์๊ฐ ๋ณต์ก๋ O(n^2)์ผ๋ก ๋๋ฆฐ ํธ ํต์ฌ ์ต์๊ฐ or ์ต๋๊ฐ ์ฐพ๊ณ , ๋จ์ ์ ๋ ฌ ๋ถ๋ถ์ ๊ฐ์ฅ ์์ ์๋ ๋ฐ์ดํฐ์ swap ํ๋ ๊ฒ ์ ํ ์ ๋ ฌ ๊ณผ์ 1. ๋จ์ ์ ๋ ฌ ๋ถ๋ถ์์ ์ต์๊ฐ ๋๋ ์ต๋๊ฐ์ ์ฐพ๋๋ค. 2. ๋จ์ ์ ๋ ฌ ๋ถ๋ถ์์ ๊ฐ์ฅ ์์ ์๋ ๋ฐ์ดํฐ์ ์ ํ๋ ๋ฐ์ดํฐ๋ฅผ swapํ๋ค. 3. ๊ฐ์ฅ ์์ ์๋ ๋ฐ์ดํฐ์ ์์น๋ฅผ ๋ณ๊ฒฝํด(index++) ๋จ์ ๋ถ๋ถ์ ๋ฒ์๋ฅผ ์ถ์ํ๋ค. 4. ์ ์ฒด ๋ฐ์ดํฐ ํฌ๊ธฐ๋งํผ index๊ฐ ์ปค์ง ๋๊น์ง, ์ฆ ๋จ์ ์ ๋ ฌ ๋ถ๋ถ์ด ์์ ๋๊น์ง ๋ฐ๋ณตํ๋ค. ์๊ฐ๋ณต์ก๋๊ฐ O(n^2)์ธ ์ด์ ๋ฅผ ์๊ฐํด๋ณด์. ๋ฐ์ดํฐ์ ๊ฐ์๊ฐ n๊ฐ ์ผ๋, ์ฒซ ๋ฒ์งธ ๋ฃจํ์์ ๋น๊ตํ์๋ 1~ n-1๋ฒ์ผ๋ก n-1๋ฒ ๋ ๋ฒ์งธ ๋ฃจ..