๐Ÿงฌ ์ด๋ถ„ํƒ์ƒ‰

๐Ÿช C:onยท2021๋…„ 9์›” 10์ผ
0

์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ชฉ๋ก ๋ณด๊ธฐ
6/6

์ด๋ถ„ํƒ์ƒ‰์€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ๋œ ๋ฐฐ์—ด์—์„œ ๋น ๋ฅด๊ฒŒ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์‹œ๊ฐ„๋ณต์žก๋„ : O(logN)
ํ•„์š”ํ•œ ๊ฒƒ : ํƒ€๊ฒŸ, ์‹œ์ž‘, ๋, ์ค‘๊ฐ„

ํŒŒ์ด์ฌ ๊ตฌํ˜„

def ์ด์ง„ํƒ์ƒ‰(ํƒ€๊ฒŸ, ๋ฆฌ์ŠคํŠธ): # ์ฐพ๋Š” ๊ฐ’์ด ๋ช‡๋ฒˆ์งธ ์›์†Œ์— ์žˆ๋Š” ์ง€ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜
	# ์ดˆ๊ธฐ์„ธํŒ…
    ๋ฆฌ์ŠคํŠธ.sort()
    ์‹œ์ž‘ = 0
    ๋ = len(arr)-1
    
    while ์‹œ์ž‘<=๋: # ๋ชจ์ˆœ์ด ์—†์œผ๋ฉด ๊ณ„์†
    	์ค‘๊ฐ„ = (์‹œ์ž‘+๋)//2
        ํ˜„์žฌ๊ฐ’ = ๋ฆฌ์ŠคํŠธ[์ค‘๊ฐ„]
        
        if ํ˜„์žฌ๊ฐ’ == ํƒ€๊ฒŸ:
        	return ์ค‘๊ฐ„
        elif ํ˜„์žฌ๊ฐ’ < ํƒ€๊ฒŸ:
        	์‹œ์ž‘ = ์ค‘๊ฐ„+1
        elif ํ˜„์žฌ๊ฐ’ > ํƒ€๊ฒŸ:
        	๋ = ์ค‘๊ฐ„ -1
	
    return none

์ดํ•ด๊ฐ€ ์‰ฝ๋„๋ก ๋ณ€์ˆ˜๋Š” ํ•œ๊ธ€๋กœ ์ž‘์„ฑํ–ˆ๋‹ค.

while ์•ˆ์˜ ๋‚ด์šฉ์€ ๊ณ„์†ํ•ด์„œ [์ค‘๊ฐ„]์— ํ•ด๋‹นํ•˜๋Š” ์›์†Œ๊ฐ€ ํƒ€๊ฒŸ๊ณผ ๊ฐ™์•„์งˆ ๋•Œ ๊นŒ์ง€ ๊ณ„์† ๋ฐ˜๋ณตํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

bisect ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ

์ด๋ถ„ํƒ์ƒ‰์„ ์ง์ ‘ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ์•„๋‹Œ, ์ด๋ถ„ํƒ์ƒ‰์„ ์‚ฌ์šฉํ•ด์„œ ํšจ์œจ์„ฑ์„ ๋†’์—ฌ์•ผ ํ•˜๋Š” ๋ฌธ์ œ์—์„œ๋Š” bisect๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ์œ ๋ฆฌํ•˜๋‹ค.

์ฒ˜์Œ์—๋Š” ์ด๋ถ„ํƒ์ƒ‰์ด ์ค‘์š”ํ•˜๋‹ค๋Š” ์ƒ๊ฐ์ด ์—†์—ˆ๋‹ค.

์ด๋ถ„ํƒ์ƒ‰์ด ์—†๋”๋ผ๋„ ํ’€์ด๋Š” ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์—.

ํ•˜์ง€๋งŒ ํšจ์œจ์„ฑ์„ ํ…Œ์ŠคํŠธ ํ•œ๋‹ค๋ฉด bisect๋ฅผ ๋ชฐ๋ผ์„œ๋Š” ์•ˆ๋œ๋‹ค.

ํ™œ์šฉ์˜ˆ์‹œ

[33, 99, 77, 70, 89, 90, 100]

๋‹ค์Œ๊ณผ ๊ฐ™์ด ์„ฑ์ ์ด ์žˆ๊ณ 

90์ ์ด์ƒ, 80์ ์ด์ƒ, 70์ ์ด์ƒ, 60์ ์ด์ƒ, ๋‚˜๋จธ์ง€๋กœ ์„ฑ์ ์„ ๋‚˜๋ˆˆ๋‹ค๋ฉด ์ด๋ถ„ํƒ์ƒ‰์œผ๋กœ ๊ฐ„๋‹จํ•˜๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค.

bisect.bisect

์œ„ ์˜ˆ์‹œ์—์„œ ๋ฆฌ์ŠคํŠธ์— for๋ฌธ์„ ๋Œ๋ ธ๋‹ค๊ณ  ๊ฐ€์ •ํ–ˆ์„ ๋•Œ, ํ˜„์žฌ ์›์†Œ๊ฐ€ 77์ด๋ผ๋ฉด
bisect.bisect([60, 70, 80, 90], 77)
์„ ํ•˜๋ฉด 77์ด ์ •๋ ฌ๋˜์–ด ์‚ฝ์ž…๋  ์ธ๋ฑ์Šค์ธ 2 ๊ฐ€ ๋ฐ˜ํ™˜๋œ๋‹ค.

bisect.bisect_left

bisect์—์„œ ํ•œ๋‹จ๊ณ„ ๋” ์—…๊ทธ๋ ˆ์ด๋“œ ๋œ ๋ฒ„์ „์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ๋œ๋‹ค.

์›๋ž˜๋Š” ํ•™์ ์˜ ๊ธฐ์ค€์ด ์–ด๋–ค ์ ์ˆ˜ ์ด์ƒ์ด๋ผ๋ฉด ์ด์—ˆ์ง€๋งŒ ๋งŒ์•ฝ ์–ด๋–ค ์ ์ˆ˜ ์ดˆ๊ณผ๋ผ๋ฉด์œผ๋กœ ์กฐ๊ฑด์ด ๋ฐ”๋€๋‹ค๋ฉด bisect_left๋ฅผ ์จ์•ผํ•œ๋‹ค.

์™œ๋ƒํ•˜๋ฉด ์›์†Œ์™€ ํƒ€๊ฒŸ์ด ๊ฐ™์€ ๊ฒฝ์šฐ,

์˜ˆ๋ฅผ ๋“ค์–ด
bisect.bisect([60, 70, 80, 90], 70)๋Š” 70์˜ ๋‹ค์Œ ์ธ๋ฑ์Šค์ธ 2๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋ฏ€๋กœ ๋” ๋†’์€ ํ•™์ ์„ ๋ฐ›์ง€๋งŒ,

bisect.bisect_left([60, 70, 80, 90], 70)๋Š” 70์˜ ์™ผ์ชฝ ์ธ๋ฑ์Šค์ธ 1์„ ๋ฐ˜ํ™˜ํ•˜์—ฌ ํ•œ๋‹จ๊ณ„ ๋‚ฎ์€ ํ•™์ ์„ ์ค„ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๋˜ํ•œ ํƒ€๊ฒŸ์ด ์‹ค์ œ ๊ทธ ๊ฐ’์„ ์ฐพ๋Š” ๋ฌธ์ œ์ผ ๊ฒฝ์šฐ์—๋„ ์ •๋‹ต์ธ ์ธ๋ฑ์Šค๋ฅผ ๋ฝ‘๊ธฐ ์œ„ํ•ด์„œ๋Š” bisect_left๋ฅผ ์‚ฌ์šฉํ•ด์•ผํ•œ๋‹ค.

0๊ฐœ์˜ ๋Œ“๊ธ€