1. ์ ๋ณด (information)๋?ํ๋ฅ : ๊ฐ๋ฅํ ๋ชจ๋ ์ํฉ์์ ์ด๋ค ์ด๋ฒคํธ๊ฐ ๋ฐ์ํ๋ ๋น๋์ ์๋ฅผ ๋ค์ด ๋ง์ผ 99๊ฐ์ ํ๋์ข
์ด์ 1๊ฐ์ ๋นจ๊ฐ์ข
์ด๊ฐ ์๋ค๊ณ ๊ฐ์ ํด๋ณด์. ๋ง์ผ, ํ๋์ข
์ด๊ฐ ๋์ค๋ฉด ๋๋ผ์ง ์์ ๊ฒ์ด๊ณ ๋นจ๊ฐ์ข
์ด๊ฐ ๋์ค๋ฉด ๋๋ ๊ฒ์ด๋ค. ํ๋ ์ข
์ด๊ฐ ๋์ฌ ํ๋ฅ ์ 0.99๋ก ๋๊ณ , ๋นจ๊ฐ ์ข
์ด๊ฐ ๋์ฌ ํ๋ฅ ์ 0.01๋ก ๋ฎ๊ธฐ ๋๋ฌธ์ด๋ค. ์ฆ ํ๋ฅ ์ด๋์ผ๋ฉด ๊ทธ ์ฌ๊ฑด์ด ๋ฐ์ํด๋ ๊ทธ ์ฌ๊ฑด์ด ๋ฐ์ํด๋ ๋๋ผ์ง ์๊ณ , ํ๋ฅ ์ด ๋ฎ์ผ๋ฉด ๊ทธ ์ฌ๊ฑด์ด ๋ฐ์ํ์ ๋ ๋๋ผ๊ฒ ๋๋ค.ํ๋ฅ ๊ณผ ๋๋์ ์๋ก ๋ฐ๋น๋ก์ ๊ฐ๋
์ด๋ค. ๊ทธ๋์ ๋๋์ ์ํ์ ์ผ๋ก ํํํ์๋ฉด, ํ๋ฅ ์ p(x)๋ผ๊ณ ํ ๊ฒฝ์ฐ ๋๋์ ํ๋ฅ ์ ์ญ์์ธ, 1 / p(x)๋ก ํํํ ์ ์๋ค. ์ค์ ์ ๋ณด์ด๋ก ์์ ํํํ๋ ๋๋์ ๊ณต์์ log(1/p(x)) ์ด๋ค. ๋ฐ๋ผ์ ..
์ ์ฒด ๊ธ
๊พธ์คํจ๐์ด์ด๋๋ฆผ์ค์ฟจ4๊ธฐ ๊ณผ์ ์ ์๊ฐํ๋ฉด์ 1์ฐจ ๋ชจ์ ๋ํ๋ก ์งํ๋ ๋์ถ์ ์ฑ๋ฌด ๋ถ์ดํ ์ฌ๋ถ ์์ธก ๋ชจ๋ธ์ ๊ฐ๋ฐํ ๊ณผ์ ์
๋๋ค. ์ ์ฒ๋ฆฌ(Pre-Processing)์ฐ์ ๊ฐ์ธ์ ์ผ๋ก ๋จธ์ ๋ฌ๋ ๊ฐ์ ๊ฒฝ์ฐ์๋ ๋ชจ๋ธ์ด ์ฑ๋ฌด๋ถ์ดํ ์ฌ๋ถ๋ฅผ ์ ์์ธกํ ์ ์๊ฒ ๋ฐ์ดํฐ์ ํน์ง์ ์ ์ก์์ฃผ๋ ๊ฒ์ด ์ค์ํ๋ค๊ณ ์๊ฐํฉ๋๋ค. ๊ทธ๋์ ๋ฐ์ด์ฝ์ด๋ ์บ๊ธ์ ๋ณด๋ฉด ํ์๋ณ์ ์์ฑ ๋๋ log ๋ณํ ๋ฑ์ผ๋ก ๋ชจ๋ธ์ด ์ฑ๋ฌด๋ถ์ดํ ์ฌ๋ถ๋ฅผ ์์ธกํ๋ ๋ฐ ์์ด ๋์์ ์ค๋ค๊ณ ํ๋จํ๋๋ฐ์. ์ด๋ฒ ๋ฐ์ดํฐ ๊ฐ์ ๊ฒฝ์ฐ์๋ ๊ธ์ต๊ณผ ๊ด๋ จ๋ ๋ฐ์ดํฐ ์์ง๋ง... ์ ๋ ๊ธ์ต๊ณผ ๊ด๋ จํ ์ง์๊ณผ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋จผ ์ฌ๋์ด๋ผ ์ต๋ํ search ํด๋ณด๊ฑฐ๋ ์ ์ฌํ ๋ํ๋ฅผ ์ฐพ์๋ดค๋ ๊ฑฐ ๊ฐ๋ค์. ๐ํ์๋ณ์ ์์ฑ feature ๋ณ๋ก ํ๋์ฉ ์๊ฐํ๋ฅผ ์งํํ์ ๋ ๋ฐ์ดํฐ์ ํน์ง๋ค์ด ์ ๋ณด์ด์ง ์์์ต๋๋ค..
์ด๋ถ ํ์ ์๊ณ ๋ฆฌ์ฆ์์ฐจํ์ : ๋ฆฌ์คํธ ์์ ์๋ ํน์ ํ ๋ฐ์ดํฐ๋ฅผ ์ฐพ๊ธฐ ์ํด ์์์ ๋ถํฐ ๋ฐ์ดํฐ๋ฅผ ํ๋์ฉ ํ์ธํ๋ ๋ฐฉ๋ฒ ์ด์งํ์ : ์ ๋ ฌ๋์ด ์๋ ๋ฆฌ์คํธ์์ ํ์ ๋ฒ์๋ฅผ ์ ๋ฐ์ฉ ์ขํ๊ฐ๋ฉฐ ๋ฐ์ดํฐ๋ฅผ ํ์ํ๋ ๋ฐฉ๋ฒ์ด์ง ํ์์ ์์์ , ๋์ , ์ค๊ฐ์ ์ ์ด์ฉํ์ฌ ํ์๋ฒ์๋ฅผ ์ค์ ํฉ๋๋ค. ๋จ๊ณ๋ง๋ค ํ์๋ฒ์๋ฅผ 2๋ก ๋๋๋ ๊ฒ๊ณผ ๋์ผํ๋ฏ๋ก ์ฐ์ฐํ์๋ $log_2 N$์ ๋น๋กํฉ๋๋ค. ๋ค์ ๋งํด, ์ด์ง ํ์์ ํ์๋ฒ์๋ฅผ ์ ๋ฐ์ฉ ์ค์ด๋ฉฐ, ์๊ฐ ๋ณต์ก๋๋ $O(log_2 N)$ ์ ๋ณด์ฅํฉ๋๋ค. ์ด์งํ์ ์์ค์ฝ๋ : ์ฌ๊ท์ ๊ตฌํ def binary_search(arr , target , start , end) : if start > end : return None mid = (start + end) // 2 ..
ํ์ด์ฌ์์ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ์ด๊น๊ฐ์ ์ง์ ํ๋ ๋ฐฉ๋ฒ์ ๋ํด ์์๋ณด์ 1. sys ๋ชจ๋ ์ฌ์ฉํ์ฌ ์์คํ
์ด ๊ฐ์ฅ ๋์ ๊ฐ๊ณผ ๊ฐ์ฅ ๋ฎ์ ๊ฐ์ ์ง์ mx = sys.maxsizemn = -sys.maxsize 2. float ์ด์ฉํด ๋ฌดํ๋ ๊ฐ์ ์ง์ mx = float('inf')mn = float('-inf') ๐ก์ฃผ์! ์ข์ง ์์ ๋ฐฉ๋ฒ mx = 999999 ํ์ด์ฌ์ ์ซ์ํ์ ์์ ์ ๋ฐ๋๋ฅผ ์ง์ํ๋ฉฐ ์ฌ์ค์ ๋ฌดํ๋์ ๊ฐ์ ์ง์ ํ ์ ์๋ค. ์๋ฌด๋ฆฌ ํฐ ์๋ผ ํ ์ง๋ผ๋ ์ผ๋ง๋ ์ง ๋ ํฐ ์๊ฐ ์ง์ ๋ ์ ์์ผ๋ฏ๋ก, ์ด๋ฐ ์์ผ๋ก ์ต์๊ฐ ๋ณ์์ ์์์ ๊ฐ์ ์ด๊น๊ฐ์ผ๋ก ์ง์ ํ๋ ๊ฒ์ ์ง์ํด์ผ ํ๋ค.