ํด์๋?๊ฐ๋
: ํด์ ํจ์๋ฅผ ์ฌ์ฉํ์ฌ ํค๋ฅผ ๊ฐ์ ๋งคํํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐํด์ ํจ์๋ ๋น ๋ฅธ ์กฐํ๋ฅผ ์ํด ํค๋ฅผ ๋ณํ๋ ๊ฐ(์ฃผ๋ก ์ธ๋ฑ์ค)์ผ๋ก ๋ณํํ์ฌ ๋ฐ์ดํฐ๋ฅผ ํจ์ฌ ๋น ๋ฅด๊ฒ ๊ฒ์ํ ์ ์๊ฒ ํด์ค๋ค.์ฐ์ ์ธ๋ฑ์ค๋ฅผ ์ฌ์ฉํ๋ ๊ธฐ์กด ๋ฐฐ์ด๊ณผ ๋ฌ๋ฆฌ ํด์๋ ํค๋ฅผ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ๋ฅผ ํ์ํน์ง๋จ๋ฐฉํฅ ์ก์ธ์ค: ํค๋ฅผ ์ฌ์ฉํ์ฌ ๊ฐ์ ์ฐพ์ ์๋ ์์ง๋ง ๊ฐ์์ ํค๋ฅผ ์ฐพ์ ์๋ ์๋ค.์์ ์๊ฐ ์กฐํ(O(1)): ํด์ ํจ์๋ ํค์์ ์ง์ ์ธ๋ฑ์ค๋ฅผ ๊ณ์ฐํ๋ฏ๋ก ์ ์ฒด ๋ฐ์ดํฐ ์งํฉ์ ๊ฒ์ํ ํ์ ์์ด ๋น ๋ฅด๊ฒ ๊ฒ์ ๊ฐ๋ฅ๋ณํ ํ์: ํด์ํจ์๋ฅผ ํตํด ํค๋ฅผ ์ธ๋ฑ์ค๋ก ๋ณํํด์ผ ๊ฐ์ ํจ์จ์ ์ผ๋ก ์ก์ธ์คํ ์ ์๋ค.ํด์๋ฅผ ์ฌ์ฉํ์ง ์์ผ๋ฉด ํญ๋ชฉ์ ์ฐพ๊ธฐ ์ํด ๋ฐ์ดํฐ ์ ์ฒด ๊ฒ์์ ์ํํด์ผ ํ๋ฏ๋ก ํจ์จ์ฑ์ด ํจ์ฌ ๋จ์ด์ง๋ค. ํด์ ํ
์ด๋ธ ๋๋ ๋ฒํทํด์ฑ์์ 'ํด์ ํ
์ด๋ธ' ๋๋ ..
๐ฏ์๊ณ ๋ฆฌ์ฆ
ํ์ด์ฌ์ ๊ธฐ๋ณธ์ ์ผ๋ก ์คํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ๊ณตํ์ง ์์ง๋ง, ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํด ์คํ์ ๊ตฌํํ ์ ์๋ค.์คํ์ LIFO(Last In, First Out) ๋ฐฉ์์ผ๋ก ๋์ํ๋ฉฐ, ๋ง์ง๋ง์ ์ถ๊ฐ๋ ํญ๋ชฉ์ด ๊ฐ์ฅ ๋จผ์ ์ ๊ฑฐ๋๋ ๊ตฌ์กฐํ์ด์ฌ ๋ฆฌ์คํธ์ ๋ช ๊ฐ์ง ๋ฉ์๋๋ฅผ ์ฌ์ฉํ๋ฉด ์คํ์ ๊ธฐ๋ณธ ์ฐ์ฐ์ ๊ตฌํํ ์ ์๋ค. 1.์คํ ์ฐ์ฐpush: ์คํ์ ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ๋ ์ฐ์ฐstack = []stack.append(10) # ์คํ์ 10 ์ถ๊ฐstack.append(20) # ์คํ์ 20 ์ถ๊ฐprint(stack) # ์ถ๋ ฅ: [10, 20] pop: ์คํ์์ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ถ๊ฐ๋ ๋ฐ์ดํฐ๋ฅผ ์ ๊ฑฐํ๊ณ ๋ฐํํ๋ ์ฐ์ฐpopped_element = stack.pop() # ์คํ์์ ๊ฐ์ฅ ์์ ์๋ 20์ ์ ๊ฑฐํ๊ณ ๋ฐํprint(popped_..
1์ฐจ์๋ฐฐ์ด#3๊ฐ์ง ๋ฐฉ๋ฒarr = [0] * 6arr = list(range(6))arr= [0 for _ in range(6)]์ด๋ ๊ฒ ๋ง๋ค ์ ์๋ค.arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]print(arr[2][3]) #12arr = [[i]*4 for i in range(3)] # [[0,0,0,0],[1,1,1,1],[2,2,2,2]]์ค์ ๋ก๋ ์ค๋ฅธ์ชฝ ์ฒ๋ผ ์ ์ฅ๋๋ค. ๋ฐฐ์ด ์ ํ์ ๊ณ ๋ คํ ์ ํ ๋นํ ์ ์๋ ๋ฉ๋ชจ๋ฆฌ ํฌ๊ธฐ๋ฅผ ํ์ธ์ค๊ฐ์ ๋ฐ์ดํฐ ์ฝ์
์ด ๋ง์์ง ํ์ธ ํ์ด์ฌ์์๋ ๋ฆฌ์คํธ๋ก ๋ฐฐ์ด ํํ ๋ฆฌ์คํธ ๊ธฐ๋ฒ๋ฆฌ์คํธ ์์ฑ๋ฆฌ์คํธ์ ๋ฐ์ดํฐ ์ถ๊ฐappend() ๋ฉ์๋: ๋ฆฌ์คํธ ๋์ ์๋ก์ด ๋ฐ์ดํฐ ์ถ๊ฐ+ ์ฐ์ฐ์: ๋ ๋ฆฌ์คํธ๋ฅผ ํฉ์ณ์ ์๋ก์ด ๋ฆฌ์คํธ ๋ง๋ ๋ค.insert() ๋ฉ์๋: ํน์ ์์น์..
https://product.kyobobook.co.kr/detail/S000210881884 ์ฝ๋ฉ ํ
์คํธ ํฉ๊ฒฉ์ ๋๊ธฐ: ํ์ด์ฌ ํธ | ๋ฐ๊ฒฝ๋ก - ๊ต๋ณด๋ฌธ๊ณ ์ฝ๋ฉ ํ
์คํธ ํฉ๊ฒฉ์ ๋๊ธฐ: ํ์ด์ฌ ํธ | โ
์ฝ๋ฉ ํ
์คํธ ํฉ๊ฒฉ์๊ฐ ๋๋ ๊ฐ์ฅ ํ์คํ ๋ฐฉ๋ฒ! โ
ํ๋ก๊ทธ๋๋จธ์ค ์ ๊ณต, ์ ๋ฌธ๊ฐ๊ฐ ๋ชจ์ฌ ์์ ํ ๋น์ถ 100๋ฌธ์ ๋ก ์ฒ ์ ํ๊ฒ ๋๋นํ์ธ์์ ์
์ฌ์ ์ฝ๋ฉ ํ
์คํธproduct.kyobobook.co.kr์ด ์ฑ
์ ๊ฐ์ง๊ณ , ์ฝํ
๋ฅผ ์ค๋นํด๋ณด๊ณ ์ ํ๋ค. ๋ฐฐ์ด๋ถํฐ ๊ทธ๋ฆฌ๋๊น์ง 12๋จ์์ด๋, ํ๋ฃจ์ ํ๋จ์ ๋๋ธ๋ค๋ ๋ง์ธ๋๋ก ์ฐจ๊ทผ์ฐจ๊ทผ ์ ๋ฆฌํด๋ณด๊ณ ์ ํ๋ค.๋ชจ๋ ๋ฌธ์ ๋ฅผ 12์ผ์์ ๋ค ํ๊ธด ์ด๋ ค์ฐ๋1ํ๋
์ ์๊ณ ์๋ ๊ฐ๋
๋ค์ ์ ๋ฆฌํ๊ณ ๊ธฐ๋ณธ์ ์ธ ๋ฌธ์ ๋ค์ ํ์ด๋ณด์2ํ๋
์ ๋ชจ๋ ๋ฌธ์ ๋ฅผ ๋ด์์ผ๋ก ํธ๋ ๊ฒ์ ์ค์ ์ผ๋ก ํ์ด๋ณด์3ํ๋
์ ์๊ฐ๋ณต์ก๋์ ํ์ด ..
DP๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ 2๊ฐ์ง๊ฐ ์กด์ฌํ๋ค. Top-downBottom-up๊ตฌํ์ฌ๊ท๋ฐ๋ณต๋ฌธ์ ์ฅ๋ฐฉ์๋ฉ๋ชจ์ด์ ์ด์
ํ๋ทธ๋ ์ด์
Memoization - ํ์ํ ๋ถ๋ถ ๋ฌธ์ ๋ค๋ง ๊ตฌํ๊ธฐ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ํ ๋ฒ ๊ตฌํ์ผ๋ฉด ๋ ๊ตฌํ์ง ์๋๋ก (์ค๋ณต์ฐ์ฐ ์๋๋ก) cache์ ์ ์ฅํด๋๊ณ ๋ค์์ ๊ฐ๋ค ์ฐ๊ธฐ Tabulation - ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ๋ฏธ๋ฆฌ ๋ค ๊ตฌํด๋๋ฉด ํธํ๋ค.ํ
์ด๋ธ์ ์ฑ์๊ฐ๋ค → ํ๋ทธ๋ ์ด์
๋ฌธ์ ๋ฅผ ์ชผ๊ฐ์ ์์ ๋ฌธ์ ๋ถํฐ ๊ตฌํด๊ฐ๋ฉฐ ์๋ ๋ฌธ์ ์ ๋ต์ ๊ตฌํ๋ ๋ฐฉ์์ด๋ค.ํต์ฌ์ ์ ํ์์ ์ฐพ๊ณ , ํ
์ด๋ธ๋ง ์ ์ ์ํ๋ฉด ํ๋ฆฐ๋ค. (์ ํ์ ์ฐพ๊ธฐ๊ฐ ์ฝ์ง ์๋ค๋๊ฒ ๋ฌธ์ ใ
ใ
) ์ด์ ๋ฌธ์ ๋ค์ ํ์ด๋ณด์. ๋ฌธ์ ํ์ดhttps://koreatstm.tistory.com/148https://koreatstm.tistory.com/149https:/..
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 ..