๋คํญ์๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ๋ป ์ต์
์ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋์ ์ํ์ ๋คํญํจ์์ ๊ผด๋ก ํํํ ์ ์๋ ๋ชจ๋ ์ข
๋ฅ์ ์๊ณ ๋ฆฌ์ฆ ํด๋ฅผ ์ป์๋ค๋ ๊ฒ์ ๊ทธ ํด์ ๋ํ ๊ฒ์ฆ์ด ์ด๋ฏธ ๋๋ฌ๋ค๋ ๊ฒ์ ์๋ฏธ ๋ชจ๋ P-๋ฌธ์ ๋ ์๋ช
ํ NP-๋ฌธ์ P-๋ฌธ์ (Polynomial) - ๋ฌธ์ ์ ๋ํ ํด๋ฅผ ๋์ถํ๋ ๋คํญ์๊ฐ ์๊ณ ๋ฆฌ์ฆ์ด ํ๋ ์ด์ ์กด์ฌํ๋ ๊ฒฝ์ฐ NP-๋ฌธ์ (Non-deterministic Polynomial) - ๋ฌธ์ ์ ๋ํ ํด๋ฅผ ๊ฒ์ฆํ๋ ๋คํญ์๊ฐ ์๊ณ ๋ฆฌ์ฆ์ด ํ๋ ์ด์ ์กด์ฌํ๋ ๊ฒฝ์ฐ NP-๋ฌธ์ ๊ฐ P-๋ฌธ์ ๋ฅผ ํฌํจํจ P-NP ๋ฌธ์ ์ ์ดํด P-๋ฌธ์ ์ NP-๋ฌธ์ ์ ํฌํจ๊ด๊ณ? ์ ์๋ก๋ถํฐ NP๊ฐ ์์์ธ ๊ฒ์ ๋ถ๋ช
, ๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ ์๋ก ๊ฐ์ ๊ฒ์ด๊ฑฐ๋ ๊ฐ์ง ์์ ๊ฒฝ์ฐ NP-๋ํด ๋ฌธ์ ๋ค์์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ X NP ํด๋์ค์ ์ํ๋ ๋ชจ๋ ๋ฌธ์ ๋ฅผ ๋คํญ์๊ฐ..
๐ป ์ปดํจํฐ/๐จ๐ป๐ป ์ฝ๋ฉ
ํ๋ฅ ์ ๊ด์ ์์์ ์์ ํ๋ณ Q. ์์ฐ์ n์ ์
๋ ฅ๋ฐ์์, n์ด ์์์ธ์ง ์๋์ง ํ๋จํ๋ ํ๋ก๊ทธ๋จ์์, ๊ฒฐ์ ๋ก ์ ์๊ณ ๋ฆฌ์ฆ์ ๋์๋๋, ๋ฌด์์ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋
Deterministric Algorithm ๋์ผํ ์
๋ ฅ์ ๋ํ์ฌ, ๋งค๋ฒ ๋์ผํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํํ์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ํ๋ฅ ๊ณผ ๋ฌด์์์ฑ์ด ๊ฐ์
ํ์ง ์์ ex. ์์ฐ์ N์ด ์์์ธ์ง ํ๋ณํ๊ธฐ ์ํด, 2,3,4, - - - ๋ฃจํธN๊น์ง์ ์๋ก ๋๋ ๋ด Randomized Algorithm ํ๋ฅ ๊ณผ ๋ฌด์์์ฑ์ด ๊ฐ์
ํจ์ผ๋ก์จ ๋์ผํ ์
๋ ฅ์ ๋ํด์๋ ๋ค๋ฅธ ๊ฒฐ๊ณผ๊ฐ ๋ํ๋ ์๋ ์๋ ํํ์ ์๊ณ ๋ฆฌ์ฆ ex. Miller-Rabin ์์ ํ๋ณ๋ฒ, Pollard-Rho ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ ์์ธ์๋ถํด ์ค์ผ๋ก ์ ๋ฆฌ๋ก ์ป์ ์ ์๋ ์์์ ํน์ฑ โ Miller-Rabin ์์ ํ๋ณ๋ฒ..
์ฐ๊ด๋ถ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๊ทธ ๊ฐ์ ์ง์ง๋ Support : ์ ์ฒด ์ฌ๋ก ๋๋น, ํด๋น ํญ๋ชฉ์ด ๋ฑ์ฅํ๋ ์ฌ๋ก์ ๋น์จ Apriori Algorithm์์ ์ํํ๋ ๊ธฐ๋ฅ์? ๋น๋ฒํ ๋ฐ์ํ๋ ์ธํธ ํ์ธ ๊ฐ์ง์น๊ธฐ ์ฐ๊ด๋ ๊ท์น ์์ฑ์ ์ฉ์ด ์ ๋ขฐ๋ confidence : A๋ฅผ ํฌํจํ๋ ์ฌ๋ก ์ค, B๊น์ง ํฌํจํ๋ ์ฌ๋ก์ ๋น์จ ๋์ ์ ๋ขฐ๋๋ฅผ ๋ณด์ด๋ ์ฐ๊ด๊ท์น์ ๋ฐ๋์ ์ ์๋ฏธํ ๊น? ํฅ์๋ lift : ์ฐ๊ด๊ท์น AโB์ ๋ํ ์ ๋ขฐ๋๋ฅผ B์ ์ง์ง๋๋ก ๋๋ ๊ฐ ์ ๋ฐฉํฅ, ์ญ๋ฐฉํฅ ๋ชจ๋ ๊ฐ์ ํฅ์๋๋ฅผ ๊ฐ์ง Apriori Algorithm ์ฌ์ ์ ์ง์ ํ ์ต์ ์ง์ง๋๋ณด๋ค ๋์ ์ง์ง๋๋ฅผ ๊ฐ๋ ๋ชจ๋ ์กฐํฉ์ ์์๋ด๊ธฐ ์ํ ๋ฐฉ๋ฒ ์ค ํ๋ ํ์ฅ๊ณผ ๊ฐ์ง ์น๊ธฐ๋ฅผ ๋ฐ๋ณตํจ์ผ๋ก์จ ์์ ํ์๋ณด๋ค ํจ์จ์ ์ผ๋ก ์กฐํฉ๋ค์ ํ์ ํ์ฅ - ํฌ๊ธฐ 1์ ํ๋ณด๊ตฐ๋ค์ ๋ชจ์ ํฌ๊ธฐ 2์..
์งํฉ์ ๋ถํ ๊ณผ ์คํธ๋ง ์ ๊ทธ๋ฃน์ ์์์ ๊ทธ๋ฃน ๋ด ์์์ ์์๋ ์ค์ํ์ง ์์ ์ํฉ ์๋ก ๋ค๋ฅธ ์ด ๊ฐ์ ํ์ ๋ค ๊ทธ๋ฃน์ผ๋ก ๋น ๊ทธ๋ฃน ์์ด ๋๋๋ ๋ฐฉ๋ฒ์? ์ 2์ข
์คํธ๋ง ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ S = list() n = 10 k = 4 for i in range(0, 100): new_list = list() for j in range(0, 100): new_list.append(-1) S.append(new_list) for i in range(1, n+1): for j in range(1, i+1): if (j == 1 or j == i): S[i][j] = 1 else: S[i][j] = S[i-1][j-1] + (j*S[i-1][j]) print(S[n][k]) ์นดํ๋ ์์ ๋ป๊ณผ ๊ทธ ์์ฉ Catalan ..
์ง์ ์ ๋ํ ์ ์ ์ข์ฐ ํ๋ณ Q. ์ธ ์ ์ด ์์ ๋, ๋ ์ ์ ์ฐ๊ฒฐํ ๋ฐ์ง์ ์ ๊ธฐ์ค์ผ๋ก ์ข์ฐ๋ฅผ ํ๋ณํ ์ ์๋๊ฐ? โ ๋ฒกํฐ์ ์ธ์ ์ ์ด์ฉํ ์ง์ ์ ๋ํ ์ ์ ์ข์ฐ ํ๋ณ ๊ฐ๋ฅ def LP(A,B,C): result1 = (A[0]*B[1]) + (B[0]*C[1]) + (C[0]*A[1]) result2 = (B[0]*A[1]) + (C[0]*B[1]) + (A[0]*C[1]) result = result1 - result2 if (result > 0): return 'LEFT' elif (result < 0): return 'RIGHT' else: return 'S' ๋ณผ๋ก ๊ป์ง ๋ฌธ์ ์ ๋ํ ํด๋ฒ ๊ทธ๋ ์ด์ ์ค์บ - ๋ณผ๋ก ๋ค๊ฐํ, ์ค๋ชฉ ๋ค๊ฐํ ๊ตฌ๋ถ ์ฃผ์ด์ง ๋ชจ๋ ์ ๋ค ์ค, ๊ฐ์ฅ ์ผ์ชฝ์ ์ ์ ๊ธฐ์ค์ ์ผ๋ก ์ค์ (..
๋ฐฑํธ๋ํน์ ์ด์ฉํ ํด์ ํ์๊ณผ ๊ทธ ์ค์ ์กฐํฉ ๋ฐ ์์ด ๋ฌธ์ : ์๋ก ๋ค๋ฅธ ์์๋ค์ ๋ชจ๋ ์กฐํฉ์ด๋ ์์ด์ ์์ฑํ ๋ ์ฌ์ฉ๋ฉ๋๋ค. N-Queens ๋ฌธ์ : NรN ์ฒด์คํ ์์ N๊ฐ์ ํธ์ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋ฐฐ์นํ๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋ ์ฌ์ฉ๋ฉ๋๋ค. ์๋์ฟ : ์ฃผ์ด์ง ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์๋์ฟ ๋ณด๋๋ฅผ ์์ฑํ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค. ๊ทธ๋ํ ์์น ๋ฌธ์ : ๊ทธ๋ํ์ ์ ์ ์ ์ต์ํ์ ์์์ผ๋ก ์์น ํ๋ ๋ฐฉ๋ฒ์ ์ฐพ๋ ๋ฌธ์ ํด๊ฒฐ์ ์ฌ์ฉ๋ฉ๋๋ค. ๋ฐฑํธ๋ํน๊ณผ ํจ์จ์ ํด ํ์ Q - ์ฌ์ฏ ๋ช
์ ์ค๋ณต ์์ด ํ ๋ช
์ฉ ๋์ดํ๋ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ? โ 6^6 ์ค, ์ค๋ณต๋์ง ์๋ ๊ฒฝ์ฐ๋ง ์ถ์ถํด ๋์ด vs ์ค๋ณต๋ ์๋ฅผ ์ ์ธํ๋ฉด์ ๋์ด Backtracking ๊ฐ๋ฅํ ๋ชจ๋ ํด๋ฅผ ํ์, ์กฐ๊ฑด์ ์ด๊ธ๋๋ ๊ฒฝ์ฐ ์ด์ ์ผ๋ก ๋์๊ฐ๋ ๊ธฐ๋ฒ ์ด๋ค ์ง์ ์ด ํด์..