Back to : ds-alg-note
Contents

Up & Down ๊ฒŒ์ž„์„ ํ•ด ๋ณด์…จ๋‚˜์š”? 1๋ถ€ํ„ฐ 1000๊นŒ์ง€์˜ ์ˆ˜ ์ค‘ ํ•˜๋‚˜๋ฅผ, 10๋ฒˆ ์ •๋„๋ฉด ๋งž์ถœ ์ˆ˜ ์žˆ๋‹ค๋Š” ์‚ฌ์‹ค์„ ์•Œ๊ณ  ๊ณ„์‹œ๋‚˜์š”? ์•„๋งˆ๋„, ๋ชจ๋‘๊ฐ€ ์ ˆ๋ฐ˜์”ฉ ์ž˜๋ผ์„œ ํ™•์ธํ•˜๋Š” ์ „๋žต์„ ์‚ฌ์šฉํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ์ „๋žต์„ ์šฐ๋ฆฌ๋Š” Binary Search ๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.
$N$ ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์ด ์ •๋ ฌ๋˜์–ด ์žˆ์Œ์„ ์•ˆ๋‹ค๋ฉด, ์ด Up & Down ์ „๋žต์„ ์ด์šฉํ•˜์—ฌ, ์šฐ๋ฆฌ๋Š” ํ•œ๋ฒˆ ์งˆ๋ฌธํ•  ๋•Œ๋งˆ๋‹ค ์ ˆ๋ฐ˜์”ฉ ๋ฌธ์ œ์˜ ํฌ๊ธฐ๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 10๊ฐœ์งœ๋ฆฌ ๋ฐฐ์—ด์˜ 5๋ฒˆ์„ ์—ด์–ด ๋ดค๋Š”๋ฐ ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” ๊ฐ’๋ณด๋‹ค ํฌ๋‹ค๋ฉด, 1๋ฒˆ๋ถ€ํ„ฐ 4๋ฒˆ ์‚ฌ์ด์— ์›ํ•˜๋Š” ๊ฐ’์ด ์žˆ์Œ์„ ์•„๋‹ˆ๊นŒ 2๋ฒˆ์ด๋‚˜ 3๋ฒˆ์„ ๋ฌผ์–ด๋ณด๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, $\order{\log n}$ ์‹œ๊ฐ„์— ์ •๋ ฌ๋œ ๋ฐฐ์—ด์—์„œ ํŠน์ •ํ•œ ๊ฐ’์„ ์ฐพ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ •๋ง ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค! Programming Practice๋“ค์„ ํ’€๋ฉด์„œ ํ™•์ธํ•ด ๋ณด์„ธ์š” :)

Binary Search๋ฅผ ํ™•์ธํ•˜์—ฌ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์งˆ๋ฌธ์— ๋น ๋ฅด๊ฒŒ ๋‹ตํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
์–ด๋–ค ํ•จ์ˆ˜ $f : \R \to \R$๊ฐ€ ๋‹จ์กฐ ์ฆ๊ฐ€ํ•˜๋Š” ์—ฐ์† ํ•จ์ˆ˜์ผ ๋•Œ, $f(x) = k$ ์ธ $x$๋ฅผ ์ฐพ์•„๋ผ.
์ •ํ™•ํžˆ ๋งํ•˜์ž๋ฉด, ์ด ์งˆ๋ฌธ์— ์ •ํ™•ํ•˜๊ฒŒ ๋‹ตํ•  ํ•„์š”๊นŒ์ง€๋Š” ์—†๊ณ , ์ถฉ๋ถ„ํžˆ ๊ฐ€๊นŒ์šด $x$๋ฅผ ์ฐพ์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด์ œ, $f$๊ฐ€ ๋‹จ์กฐ์ฆ๊ฐ€ํ•œ๋‹ค๋Š” ์„ฑ์งˆ์„ ์ด์šฉํ•˜์—ฌ, ์ถฉ๋ถ„ํžˆ ์ž‘์€ ์ˆ˜์™€ ์ถฉ๋ถ„ํžˆ ํฐ ์ˆ˜๋กœ ์–‘์ชฝ ๋๊ฐ’์„ ์žก์•„ ๋†“๊ณ , ๊ทธ ์‚ฌ์ด๋ฅผ ๊ตฌ๊ฐ„์œผ๋กœ ์ด๋ถ„ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด, $2^{1/3}$ ์„ ๊ณ„์‚ฐํ•ด์•ผ ํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์ด๋•Œ, ์šฐ๋ฆฌ๋Š” ๋‹ต์ด ๋˜๋Š” $x$๊ฐ€ $x^3 = 2$ ๋ฅผ ๋งŒ์กฑํ•˜๋ฉฐ, ์ด ๊ฐ’์ด $0$๊ณผ $2$ ์‚ฌ์ด์— ์žˆ์Œ์„ ์••๋‹ˆ๋‹ค. ์ด ๊ตฌ๊ฐ„์˜ ์ค‘๊ฐ„์ธ $1$์„ ์ด์šฉํ•˜์—ฌ, $1^3 = 1 < 2$ ์ด๋ฏ€๋กœ, ๋‹ต์ด $1$๊ณผ $2$ ์‚ฌ์ด์ž„์„ ์••๋‹ˆ๋‹ค. ์ด์ œ, $1.5^3 > 2$ ์ด๋ฏ€๋กœ, ๋‹ต์ด 1๊ณผ $1.5$ ์‚ฌ์ด์ž„์„ ์••๋‹ˆ๋‹ค. ์ด์ œ $1.25$๋ฅผ ์‹œ๋„ํ•˜๊ณ ...
์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ Parametric Search๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค (์‚ฌ์‹ค์€, ์ด ๋‹จ์–ด๋Š” ๋” ์ผ๋ฐ˜์ ์ธ ์ƒํ™ฉ์—์„œ ์“ฐ๋Š” ๋ง์ž…๋‹ˆ๋‹ค. ๊ตณ์ด ๋งํ•˜์ž๋ฉด Bisection search ์ •๋„๊ฐ€ ์ •ํ™•ํ•  ๊ฒƒ ๊ฐ™์€๋ฐ, ์šฐ๋ฆฌ๊ฐ€ ๊ด€์‹ฌ์žˆ๋Š” Parametric Search๊ฐ€ ์ด์ชฝ์ด ๋Œ€๋ถ€๋ถ„์ด๋ผ์„œ ๊ทธ๋Ÿฐ ๊ฒƒ ๊ฐ™๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค). Parametric Search๋Š” Binary Search์˜ ์ผ๋ฐ˜ํ™”์ด๋ฉด์„œ, ์ •๋ง ๋งŽ์€ ๊ฒƒ๋“ค์„ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์•ž์œผ๋กœ ๋Œ€ํšŒ ์ค€๋น„๋‚˜ ๊ณต๋ถ€๋ฅผ ๋” ํ•˜๋‹ค ๋ณด๋ฉด, ์ด ์•„์ด๋””์–ด๋ฅผ ์ด์šฉํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ์ •๋ง ๋งŽ์ด ๋งŒ๋‚˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
Parametric๊ณผ Binary ๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ์•Š๊ณ  Binary Search๋ฅผ ์ด์šฉํ•œ๋‹ค๊ณ  ๋งํ•˜๋Š” ์‚ฌ๋žŒ๋„ ๋งŽ์ด ์žˆ๊ณ , ์‚ฌ์‹ค ์ด๊ฑธ ๊ตณ์ด ๊ตฌ๋ถ„ํ•  ํ•„์š”๊ฐ€ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•˜์ง€๋Š” ์•Š์Šต๋‹ˆ๋‹ค. Binary๋ผ๊ณ  ์“ฐ๋”๋ผ๋„ ๋งฅ๋ฝ์— ๋”ฐ๋ผ ์ดํ•ดํ•ด ์ฃผ์„ธ์š”.

* ์ด subsection์„ skipํ•ด๋„ ๋’ค ๋‚ด์šฉ์— ์˜ํ–ฅ์ด ์—†์Šต๋‹ˆ๋‹ค.
์–ด๋–ค ํ•จ์ˆ˜ $f : \R \to \R$๊ฐ€ ๋ณผ๋กํ•จ์ˆ˜๋ผ๊ณ  ํ•  ๋•Œ, $f(x)$ ์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ๋Š” ๋ฌธ์ œ๋ฅผ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ๋งŒ์•ฝ $f$๊ฐ€ ๋ฏธ๋ถ„ ๊ฐ€๋Šฅํ•œ ํ•จ์ˆ˜๋ผ๋ฉด, $f$์˜ ๋„ํ•จ์ˆ˜๋ฅผ ์ƒ๊ฐํ–ˆ์„ ๋•Œ, $fโ€™(x) = 0$์ด ๋˜๋Š” $x$๋ฅผ Binary Search๋กœ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์šฐ๋ฆฌ๊ฐ€ ์ƒ๊ฐํ•˜๋Š” ํ•จ์ˆ˜๊ฐ€, โ€˜๋Œ€์ถฉ ๋ณผ๋กํ•˜๊ฒŒ ์ƒ๊ธฐ๊ธด ํ–ˆ์ง€๋งŒโ€™ ๋ฏธ๋ถ„์ด ๊ฐ€๋Šฅํ•˜์ง„ ์•Š์„ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๊ฒฝ์šฐ์—, $\log$ ์‹œ๊ฐ„์— ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ๋‹จ, ์ด ํ•จ์ˆ˜ $f$๊ฐ€ ํ‰ํ‰ํ•œ ๊ตฌ๊ฐ„์„ ๊ฐ–์ง€ ์•Š๋Š”๋‹ค๊ณ  ํ•ฉ์‹œ๋‹ค.

  • ์ถฉ๋ถ„ํžˆ ์ž‘์€ $L$๊ณผ ํฐ $R$์„ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

  • $[L, R]$์˜ ์‚ผ๋“ฑ๋ถ„์ ์ธ $p, q$๋ฅผ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

  • ์ผ๋ฐ˜์„ฑ์„ ์žƒ์ง€ ์•Š๊ณ , $f(p) > f(q)$ ๋ผ๊ณ  ๊ฐ€์ •ํ•ฉ์‹œ๋‹ค. ์ด๋•Œ, ๋งŒ์•ฝ ์ตœ์†Ÿ๊ฐ’์ด $[L, p]$์— ์žˆ๊ณ , ๊ทธ ์ตœ์†Œ์ ์ด $x = t$๋ผ๋ฉด, ํ•จ์ˆ˜๊ฐ€ ์ ์–ด๋„ $t$์—์„œ $p$๊นŒ์ง€ ์‚ฌ์ด์—์„œ ์ฆ๊ฐ€ํ•˜๋Š” ๊ตฌ๊ฐ„์ด ์žˆ๊ณ , ๋‹ค์‹œ $q$๊นŒ์ง€ ๊ฐ์†Œํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋Š” $f$์˜ ๋ณผ๋ก์„ฑ๊ณผ ๋ชจ์ˆœ์ด๋ฏ€๋กœ, ์ตœ์†Ÿ๊ฐ’์ด $[p, R]$ ์‚ฌ์ด์— ์žˆ์Šต๋‹ˆ๋‹ค.

  • ์šฐ๋ฆฌ๊ฐ€ ๋ณด๋Š” ๊ตฌ๊ฐ„์˜ ๊ธธ์ด๊ฐ€ $\frac{2}{3}$์œผ๋กœ ์ค„์–ด๋“ค์—ˆ์Šต๋‹ˆ๋‹ค!

์ด์ œ, ์ƒ๊ฐํ•ด ๋ณด๋ฉด ๋งค๋ฒˆ $2/3$์œผ๋กœ ๊ตฌ๊ฐ„์„ ์ค„์ด๋Š” ๊ฒƒ์ด๋ฏ€๋กœ, $\log_{3/2} n$ ์‹œ๊ฐ„์— ($n$์€ ์šฐ๋ฆฌ๊ฐ€ ํ•„์š”ํ•œ ์ •๋ฐ€๋„์™€, ๊ตฌ๊ฐ„ ๊ธธ์ด์˜ ๋น„์œจ์ž…๋‹ˆ๋‹ค. ๊ฐ„๋‹จํžˆ ๋งํ•ด, $[0, 10]$ ์‚ฌ์ด์—์„œ $0.001$ ์ˆ˜์ค€์˜ ์ •๋ฐ€๋„๋ฅผ ์–ป๋Š” ๊ฒƒ์€ 1๋งŒ ์นธ ์ค‘ ํ•˜๋‚˜๋ฅผ ์ฐพ๋Š” ๋Š๋‚Œ์œผ๋กœ ์ ‘๊ทผํ•˜๋ฉด ๋œ๋‹ค๋Š” ์–˜๊ธฐ์ž…๋‹ˆ๋‹ค) ๋‹ต์„ ์–ป์„ ์ˆ˜ ์žˆ๊ณ , Asymptoticํ•˜๊ฒŒ๋Š” ๋กœ๊ทธ์˜ ๋ฐ‘์€ ๋ฌด์˜๋ฏธํ•˜๋ฏ€๋กœ $\log$ ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ฉ๋‹ˆ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ Ternary Search, ์‚ผ๋ถ„ ํƒ์ƒ‰์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.

์ด๋ถ„ ํƒ์ƒ‰์ด๋‚˜ ์‚ผ๋ถ„ ํƒ์ƒ‰์€ ๊ทธ ์ž์ฒด๋กœ๋„ ๋งค์šฐ ์˜๋ฏธ์žˆ์ง€๋งŒ, ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฒฐํ•ฉ๋˜์—ˆ์„ ๋•Œ ๊ทธ ์œ ์šฉ์„ฑ์ด ๋”์šฑ ๋ถ€๊ฐ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ฒ˜์Œ ์ ‘ํ–ˆ์„ ๋•Œ ์ƒ๊ฐํ•ด๋‚ด๊ธฐ ์–ด๋ ต๊ธฐ ๋•Œ๋ฌธ์—, ๋งŽ์€ ์—ฐ์Šต์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.