์ „์ฒด ๊ธ€

๊พธ์ค€ํ•จ๐Ÿ€
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  ํŒŒ์ด์ฌ์˜ ์ˆซ์žํ˜•์€ ์ž„์˜ ์ •๋ฐ€๋„๋ฅผ ์ง€์›ํ•˜๋ฉฐ ์‚ฌ์‹ค์ƒ ๋ฌดํ•œ๋Œ€์˜ ๊ฐ’์„ ์ง€์ •ํ•  ์ˆ˜ ์žˆ๋‹ค. ์•„๋ฌด๋ฆฌ ํฐ ์ˆ˜๋ผ ํ• ์ง€๋ผ๋„ ์–ผ๋งˆ๋“ ์ง€ ๋” ํฐ ์ˆ˜๊ฐ€ ์ง€์ •๋  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋Ÿฐ ์‹์œผ๋กœ ์ตœ์†Ÿ๊ฐ’ ๋ณ€์ˆ˜์— ์ž„์˜์˜ ๊ฐ’์„ ์ดˆ๊นƒ๊ฐ’์œผ๋กœ ์ง€์ •ํ•˜๋Š” ๊ฒƒ์„ ์ง€์–‘ํ•ด์•ผ ํ•œ๋‹ค.
zzoming_00
ZZOMING'S TECH BLOG