Back to : ds-alg-note

* ์˜ค๋Š˜์€ ํŠน๋ณ„ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐฐ์šฐ๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ, โ€˜๋ฐฉ๋ฒ•๋ก โ€™ ์— ๊ฐ€๊น๊ธฐ ๋•Œ๋ฌธ์—, Section๊ณผ Additional์˜ ๊ตฌ๋ถ„์ด ๋ณ„๋กœ ์—†๊ณ  ๋ชจ๋‘ ์†Œ๋ฌธ์ œ๋“ค๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์—ฌ๊ธฐ ๋‚˜์˜จ ๋ชจ๋“  ์†Œ๋ฌธ์ œ๋ฅผ ๊ณ ๋ฏผํ•ด ๋ณด๊ธธ ๊ถŒํ•ฉ๋‹ˆ๋‹ค.

Divide and Conquer

์–ด๋–ค ๋ฌธ์ œ๋“ค์€ ๋ฌธ์ œ ์ž์ฒด๊ฐ€ ์žฌ๊ท€์ ์ž…๋‹ˆ๋‹ค. ์ฆ‰, ์–ด๋–ค ์ปค๋‹ค๋ž€ ๋ฌธ์ œ X๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด, X๋ฅผ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์ž‘์€ ๋ฌธ์ œ $x_1, x_2, \dots x_k$๋กœ ๋‚˜๋ˆˆ ๋‹ค์Œ, ๊ฐ๊ฐ์„ ํ’€๊ณ , ํ•ฉ์น  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ์ƒ๊ฐํ•ด ๋ณด์ž๋ฉด, ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์“ฐ๋Š” ๊ฒƒ์ด ์ž์—ฐ์Šค๋Ÿฌ์šด ๋ฌธ์ œ๋“ค์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋Ÿฌํ•œ ๋ฌธ์ œ๋“ค์— ๋Œ€ํ•ด, Divide and Conquer (๋ถ„ํ•  ์ •๋ณต) ์ด๋ผ๋Š” ๊ธฐ๋ฒ•์ด ๋งค์šฐ ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค.
์ง€๊ธˆ๊นŒ์ง€ ์—ฌ๋Ÿฌ๋ถ„์€ ๋ถ„ํ•  ์ •๋ณต์„ ์“ฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ƒ๋‹นํžˆ ๋งŽ์ด ๋งŒ๋‚˜ ๋ณด์•˜๊ธฐ ๋•Œ๋ฌธ์—, ๋ถ„ํ•  ์ •๋ณต์ด๋ผ๋Š” ๋ง์ด ์ต์ˆ™ํ•˜์ง€ ์•Š๋”๋ผ๋„ ์ƒ๊ฐํ•˜๋Š” ๋ฐฉ๋ฒ• ์ž์ฒด๋Š” ๊ทธ๋ ‡๊ฒŒ ๋‚ฏ์„ค์ง€ ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์–ด๋ ต์ง€๋งŒ, ์ž‘์€ ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ํ•ฉ์น˜๋Š” ๊ฒŒ ๋” ์‰ฌ์šธ ์ˆ˜๋„ ์žˆ๋‹ค๋ฉด, ๋ถ„ํ•  ์ •๋ณต์„ ์ƒ๊ฐํ•ด ๋ณผ ์ˆ˜ ์žˆ๊ฒ ์Šต๋‹ˆ๋‹ค.

Merge Sort

๋ณ‘ํ•ฉ ์ •๋ ฌ (Merge Sort) ๋Š” ๋Œ€ํ‘œ์ ์ธ ๋ถ„ํ•  ์ •๋ณต ๊ธฐ๋ฒ•์ž…๋‹ˆ๋‹ค. ์•ž์„œ ๋งํ•œ ๋ถ„ํ•  ์ •๋ณต์„ ์“ฐ๋Š” ์ด์œ ๊ฐ€ ๊ฐ€์žฅ ์ž˜ ๋‚˜ํƒ€๋‚ฉ๋‹ˆ๋‹ค. $n$ ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์„ ์ •๋ ฌํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค, $n/2$ ํฌ๊ธฐ์˜ ๋ฐฐ์—ด 2๊ฐœ๋ฅผ ์ •๋ ฌํ•˜๊ณ , ๋‘ ์ •๋ ฌ๋œ ๋ฐฐ์—ด์„ ์ •๋ ฌ์„ฑ์„ ์œ ์ง€ํ•˜๋ฉด์„œ ํ•ฉ์น˜๋Š” ๊ฒƒ์ด ๋” ๋น ๋ฅด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
์•„๋ž˜ ์˜ˆ์‹œ์™€ Additional (1), (2) ๋ชจ๋‘ ๋ถ„ํ•  ์ •๋ณต์„ ์ด์šฉํ•˜๋Š” ํ›Œ๋ฅญํ•œ ์˜ˆ์‹œ์ž…๋‹ˆ๋‹ค.

๋น ๋ฅธ ๊ฑฐ๋“ญ ์ œ๊ณฑ

Divide and Conquer๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋‹ค๋ฅธ ์˜ˆ์‹œ๋ฅผ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์ด๋ฒˆ์˜ ๋ชฉํ‘œ๋Š”, ์–ด๋–ค ์ˆ˜ $x$์˜ $y$์ œ๊ณฑ์„ ๊ณ„์‚ฐํ•˜๋Š” ์ผ์ž…๋‹ˆ๋‹ค. ์ƒ์‹์ ์œผ๋กœ, ๊ณฑ์…ˆ์„ $y$ ๋ฒˆ ํ•˜๋Š” ์ผ์ด๋ฏ€๋กœ, $O(y)$์— ํ•˜๋Š” ๊ฒƒ์ด ์ž์—ฐ์Šค๋Ÿฌ์›Œ ๋ณด์ž…๋‹ˆ๋‹ค.
์•”ํ˜ธํ•™, ํŠนํžˆ RSA ์•”ํ˜ธ ์ฒด๊ณ„์—์„œ๋Š” $x^y \pmod{p}$๋ฅผ ๊ณ„์‚ฐํ•  ์ผ์ด ๋งค์šฐ ๋งŽ์€๋ฐ, $y$๊ฐ€ ๊ฑฐ๋Œ€ํ•œ ์ˆ˜์ธ ๊ฒฝ์šฐ๋„ ๋งŽ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ $10,702,103$์˜ $2,718,281,828$ ์ œ๊ณฑ ๊ฐ™์€ ๊ฒƒ์„ ๊ณ„์‚ฐํ•˜๋ ค๊ณ  ํ•œ๋‹ค๋ฉด, ์–ด๋–จ๊นŒ์š”? ์ด๋•Œ ์šฐ๋ฆฌ๋Š” โ€˜exponentiation by squaringโ€™ ์ด๋ผ๋Š” ๋ฐฉ๋ฒ•์„ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝ $x^y$์—์„œ $y$๊ฐ€ ํ™€์ˆ˜๋ผ๋ฉด, $x^{y-1} \times x$๋กœ ์‹์„ ์ •๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ $y$๊ฐ€ ์ง์ˆ˜๋ผ๋ฉด, $(x^{y/2})^2$ ๋กœ ์ •๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์ด $\order{\log y}$ ์— ์ œ๊ณฑ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค๋Š” ์‚ฌ์‹ค์„ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค.

Dynamic Programming

Memoization : Top Down DP

๋ถ„ํ•  ์ •๋ณต์€ ์ •๋ง ๊ฐ•๋ ฅํ•œ ๋„๊ตฌ์ž…๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด๋„ ๋ถ„ํ•  ์ •๋ณต์œผ๋กœ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. fib(n)์„ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•ด, fib(n-1) ๊ณผ fib(n-2)๋ฅผ ํ˜ธ์ถœํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ด ๋ฐฉ๋ฒ•์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์ฒ˜์ฐธํ•ฉ๋‹ˆ๋‹ค. ํ˜ธ์ถœ๋˜๋Š” ๊ณผ์ •์„ ๋ณด๋ฉด, $f(n)$ ์€ ํ•œ ๋ฒˆ ํ˜ธ์ถœํ•˜๋”๋ผ๋„, $f(1)$ ์ด๋‚˜ $f(2)$ ๊ฐ™์€ ํ•จ์ˆ˜๋“ค์„ ์ˆ˜์—†์ด ๋งŽ์ด ํ˜ธ์ถœํ•˜๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์ด๋Ÿฐ ์ค‘๋ณต๋˜๋Š” ๊ณผ์ •์„, ์•ฝ๊ฐ„์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ด์šฉํ•˜์—ฌ, ํ•œ๋ฒˆ๋งŒ ๊ณ„์‚ฐํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.
์ด๋ฅผ ์œ„ํ•ด ์‚ฌ์šฉํ•˜๋Š” ๊ธฐ๋ฒ•์ด Memoization์ž…๋‹ˆ๋‹ค.1 ๋ฏธ๋ฆฌ ๋ฐฐ์—ด fib[]์—, ๋งค๋ฒˆ ํ˜ธ์ถœ๋  ๋•Œ๋งˆ๋‹ค ๋‚ด๊ฐ€ ๊ณ„์‚ฐํ•œ ๊ฐ’์„ ์ ์–ด ๋†“์Šต๋‹ˆ๋‹ค. ๋งค๋ฒˆ ํ•จ์ˆ˜๊ฐ€ ํ˜ธ์ถœ๋  ๋•Œ๋งˆ๋‹ค, ํ˜น์‹œ ์ด ๊ฐ’์ด ๋‚ด๊ฐ€ ๋ณธ ์  ์žˆ๋Š” ๊ฐ’์ธ์ง€ ๋ฉ”๋ชจ์ง€๋ฅผ ํ™•์ธํ•˜๊ณ , ๋ฉ”๋ชจ์ง€์— ์ ํžŒ ๊ฐ’์€ ๋‹ค์‹œ ๊ณ„์‚ฐํ•˜๋Š” ๋Œ€์‹ , ๋ฉ”๋ชจ์ง€๋ฅผ ๋ณด๊ณ  ๋ฐ”๋กœ ๋‹ตํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.
ํ•จ์ˆ˜ ํ˜ธ์ถœ์˜ ์ˆœ์„œ๋ฅผ ๋ณด๋ฉด, ํฐ ๊ฐ’๋“ค (TOP) ์ด ๋จผ์ € ํ˜ธ์ถœ๋˜๊ณ , ๊ทธ ๊ณผ์ •์—์„œ ์ž‘์€ ๊ฐ’๋“ค (DOWN)์˜ ๊ฐ’๋“ค์˜ ๊ณ„์‚ฐ์ด ํ•„์š”ํ•จ์„ ๋ˆˆ์น˜์ฑˆ ๋‹ค์Œ, ๋‚ด๋ ค๊ฐ€๋ฉด์„œ ์ด ๊ฐ’๋“ค์„ ๊ณ„์‚ฐํ•˜๊ณ  ๋‹ค์‹œ ์˜ฌ๋ผ์˜ค๋ฉด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๊ณผ์ •์„ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ณผ์ •์„ TOP-DOWN ๋ฐฉ์‹์˜ Dynamic Programming ์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.

Bottom Up DP

๋ฌผ๋ก , ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ๊ณ„์‚ฐํ•˜๊ธฐ ์œ„ํ•ด ๊ผญ ์ €๋Ÿฐ ๋ฐฉ์‹์„ ์“ธ ํ•„์š”๋Š” ์—†์Šต๋‹ˆ๋‹ค. ์ž‘์€ ๊ฐ’๋“ค์„ ์ด์šฉํ•ด์„œ ํฐ ๊ฐ’์„ ๊ณ„์‚ฐํ•  ์ˆ˜๋งŒ ์žˆ๋‹ค๋ฉด, ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ฐ„๋‹จํ•˜๊ฒŒ ์ฝ”๋”ฉํ•ด๋„ ๋ฉ๋‹ˆ๋‹ค.

for (int i = 2; i<=n; i++)
    fib[i] = fib[i-1] + fib[i-2]

์ด ๋ฐฉ๋ฒ•์€, ๊ณ„์‚ฐ ์ˆœ์„œ๋ฅผ ๋ณผ ๋•Œ, ์ž‘์€ ๊ฐ’๋“ค์„ ๋จผ์ € ๊ณ„์‚ฐํ•ด๋†“๊ณ  ๊ทธ๊ฑธ ์ด์šฉํ•ด์„œ ์œ„๋กœ ์˜ฌ๋ผ๊ฐ€๋ฉฐ ๊ณ„์‚ฐํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ Bottom-UP ๋ฐฉ์‹์˜ Dynamic Programming์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.
Top-Down๊ณผ Bottom-Up ์ค‘ ๋ฌด์—‡์ด ๋” ๊ตฌํ˜„ํ•˜๊ธฐ ํŽธํ•˜๊ณ , ์–ด๋Š์ชฝ์ด ์œ ๋ฆฌํ•œ์ง€๋Š” ๊ทธ๋•Œ๊ทธ๋•Œ ๋‹ค๋ฅด๊ธฐ ๋•Œ๋ฌธ์—, ์ƒํ™ฉ์— ๋”ฐ๋ผ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ค‘์š”ํ•œ ๊ฒƒ์€ ๋‹ค์Œ์˜ ์›์น™์ž…๋‹ˆ๋‹ค.

  • Optimal Substructure : ํฐ ๋ฌธ์ œ $f(X)$๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด, $f(Y)$ such that $Y < X$์˜ ๋‹ต์„ ์ด์šฉํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.2 ์ฆ‰, ์ž‘์€ ๋ฌธ์ œ์˜ ๋‹ต์ด ํ•ญ์ƒ ๋” ํฐ ๋ฌธ์ œ์˜ ๋‹ต์„ ์ œ๊ณตํ•˜๋Š”๋ฐ ๋„์›€์ด ๋˜๋Š” ๊ฒฝ์šฐ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์ด ์กฐ๊ฑด์€ Divide and Conquer๊ณผ Dynamic Programming ๋ชจ๋‘์— ์ ์šฉ๋ฉ๋‹ˆ๋‹ค.

  • Overlapping Subproblem : ์œ„ Overlapping Substructure๋ฅผ ์ ์šฉํ•จ์— ์žˆ์–ด์„œ, ๊ฒน์น˜๋Š” ๋ฌธ์ œ๋ฅผ ์—ฌ๋Ÿฌ๋ฒˆ ํ’€์–ด์•ผ ํ•ด์„œ ์ด๋ฅผ ์ตœ์ ํ™”ํ•˜๊ณ  ์‹ถ์€ ๊ฒฝ์šฐ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. Fibonacci๊ฐ€ ๋Œ€ํ‘œ์ ์ž…๋‹ˆ๋‹ค. ์ด ์›์น™์€ Dynamic Programming์˜ ๊ธฐ๋ณธ ์›๋ฆฌ์ž…๋‹ˆ๋‹ค.

DP ์˜ˆ์‹œ : 2์ฐจ์› ๊ฒฝ๋กœ ๋ฌธ์ œ

์–‘์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ $n \times n$ ํ–‰๋ ฌ์ด ์ฃผ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, ์šฐ๋ฆฌ๋Š” $(1, 1)$ ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ, $(n, n)$ ์œ„์น˜๊นŒ์ง€ ์ด๋™ํ•˜๋˜, ์•„๋ž˜์ชฝ ๋˜๋Š” ์˜ค๋ฅธ์ชฝ์œผ๋กœ๋งŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋™ํ•˜๋Š” ๊ณผ์ •์—์„œ, ํ–‰๋ ฌ์˜ ๋ฐฉ๋ฌธํ•œ ์นธ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆซ์ž๋“ค์„ ๋”ํ•œ ๊ฐ’์ด ์ด ๊ฒฝ๋กœ์˜ ์ตœ์ข… ์ ์ˆ˜์ž…๋‹ˆ๋‹ค. ์ ์ˆ˜๋ฅผ ์ตœ๋Œ€ํ™”ํ•˜๋Š” ์ด๋™ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์•„ ๋ด…์‹œ๋‹ค.
Optimal Substructure๋ฅผ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์–ด๋–ค ์นธ $(i, j)$ ์— ๋„์ฐฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, $(i-1, j)$ ๋˜๋Š” $(i, j-1)$ ์—์„œ ์™€์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, $(i-1, j)$ ๊นŒ์ง€ ์–ด๋–ป๊ฒŒ ์™”๋Š”์ง€๋Š” ๋ณ„๋กœ ๊ด€์‹ฌ์ด ์—†์ง€๋งŒ, ์ด ์‹œ์ ๊นŒ์ง€ ์˜จ ์ ์ˆ˜๊ฐ€ ์ตœ๋Œ€๊ฐ€ ๋˜๋ฉด ์ข‹์„ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ฆ‰, ๊ฒฝ๋กœ์™€ ๋ฌด๊ด€ํ•˜๊ฒŒ ์ผ๋‹จ ์–ด๋–ป๊ฒŒ๋“  ์ตœ์„ ์„ ๋‹คํ•ด $(i-1, j)$ ๋˜๋Š” $(i, j-1)$ ๊นŒ์ง€ ์™”๋‹ค๋ฉด, ๊ทธ ๊ฒฝ๋กœ๋“ค์—์„œ ํ•œ์นธ์„ ์—ฐ์žฅํ•˜์—ฌ $(i, j)$ ์— ์˜ค๋Š” ์ตœ์  ๊ฒฝ๋กœ๊ฐ€ ๋‚˜ํƒ€๋‚˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์ฆ‰, ๋‹ค์Œ๊ณผ ๊ฐ™์€ DP๋ฅผ ๊ตฌ์ƒํ•ฉ๋‹ˆ๋‹ค. \(C_{ij} = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0\\ \max({C_{i-1, j}, C_{i, j-1}}) + M_{ij} & \text{otherwise} \end{cases}\) ๋งŒ์•ฝ $C_{44}$๋ฅผ ๊ณ„์‚ฐํ•˜๋ ค๊ณ  ํ•œ๋‹ค๋ฉด, $C_{34}$์™€ $C_{43}$ ์„ ๊ณ„์‚ฐํ•ด์•ผํ•˜๊ณ , ๊ทธ๋Ÿฌ๋ฉด $C_{33}, C_{24}, C_{33}, C_{42}$ ๋ฅผ ๊ณ„์‚ฐํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋ฒŒ์จ $C_{33}$ ์„ ๋‘๋ฒˆ ๊ณ„์‚ฐํ–ˆ์Šต๋‹ˆ๋‹ค! Overlapping Substructure๊ฐ€ ๋ณด์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ ์ตœ์ ํ™”ํ•˜์—ฌ ๊ณ„์‚ฐํ•ด๋„ ์ข‹๊ณ , ์•„๋ž˜์™€ ๊ฐ™์ด Bottom-Up DP๋ฅผ ์ƒ๊ฐํ•ด๋„ ๋ฉ๋‹ˆ๋‹ค.

for (int i = 1; i<=n; i++)
    for (int j = 1; j<=n; j++)
        C[i][j] = M[i][j] + max(C[i-1][j], C[i][j-1]);

์ด๋ ‡๊ฒŒ ํ•˜๋ฉด Dynamic Programming์„ ์ด์šฉ, $O(n^2)$ ์— ๊ณ„์‚ฐํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
๋ฐฉ๊ธˆ ๋ณธ ๊ฒƒ์ฒ˜๋Ÿผ, 2์ฐจ์› ๊ทธ๋ฆฌ๋“œ ์œ„์—์„œ๋„ ํ•ฉ๋ฆฌ์ ์ธ DP ์ˆœ์„œ๋ฅผ ์ค„ ์ˆ˜ ์žˆ์œผ๋ฉด (์™ผ์ชฝ ์œ„๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜) ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์ด์™ธ์—๋„ DP๋Š” ์ •๋ง ๋‹ค์–‘ํ•œ ํ˜•ํƒœ๋กœ ๋“ฑ์žฅํ•˜๊ณ , ์œ ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋งŽ์€ ์—ฐ์Šต์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

์ถ”์ฒœ๋ฌธ์ œ : ์•„๋ž˜ (3), (4), (5) ์ดํ›„์—๋„ ๋” ํ’€์–ด๋ณด๊ณ  ์‹ถ๋‹ค๋ฉด, BOJ ๊ธฐ์ค€ 1005, 11066, 9251๋ฒˆ์„ ํ™•์ธํ•ด ๋ณด์„ธ์š”.

Additional Topics / Problems

  1. Karatsuba Algorithm ์šฐ๋ฆฌ๊ฐ€ ๊ณฑ์…ˆ์€ $O(1)$์— ์ˆ˜ํ–‰๋œ๋‹ค๊ณ  ๋ฏฟ์—ˆ์ง€๋งŒ, ์‚ฌ์‹ค ์ƒ๊ฐํ•ด ๋ณด๋ฉด ์ƒ์‹์ ์œผ๋กœ ๊ทธ๋Ÿด ๋ฆฌ๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค. 10์–ต ์ž๋ฆฌ ์ˆ˜๋ฅผ ๊ณฑํ•˜๋Š” ์ผ๊ณผ $3 \times 5$๋ฅผ ํ•˜๋Š” ์ผ์ด ๊ฐ™์€ ์‹œ๊ฐ„์— ์ˆ˜ํ–‰๋  ๋ฆฌ๋Š” ์—†๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์ผ์ƒ์ ์œผ๋กœ ์‚ฌ์šฉํ•˜๋Š” ์ˆ˜์˜ ๋ฒ”์œ„์—์„œ, ํŠนํžˆ C++์˜ int ๋‚˜ long long ๋ฒ”์œ„์—์„œ ๊ณฑ์…ˆ์ด ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ์ƒ์ˆ˜ ๋น„์Šทํ•œ ์‹œ๊ฐ„์— ์ˆ˜ํ–‰๋˜๊ธฐ ๋•Œ๋ฌธ์— ์šฐ๋ฆฌ๋Š” ์•ž์œผ๋กœ๋„ $O(1)$์— ๊ธฐ๋ณธ ์‚ฌ์น™์—ฐ์‚ฐ์ด ์ž‘๋™ํ•œ๋‹ค๋Š” ๋ฏฟ์Œ์„ ๊ฐ–๊ณ  ๋งํ•˜๊ฒ ์ง€๋งŒ, ์—ฌ๊ธฐ์„œ๋Š” ์ž ๊น๋งŒ ์ด ๋ถ€๋ถ„์„ ์˜์‹ฌํ•ด ๋ด…์‹œ๋‹ค. ๋‹ค์Œ ํ๋ฆ„์„ ๋”ฐ๋ผ๊ฐ€๋ฉฐ, Karatsuba์˜ ์•„์ด๋””์–ด์™€, ์ด ์•„์ด๋””์–ด๋ฅผ ์ฒ˜์Œ ๋“ค์—ˆ๋˜ ์œ ๋ช…ํ•œ ์ˆ˜ํ•™์ž Kolmogorov3๊ฐ€ ๋ฐ›์•˜๋˜ ์ถฉ๊ฒฉ์„ ๋Š๊ปด๋ด…์‹œ๋‹ค.

    (1) ์ดˆ๋“ฑํ•™๊ต์—์„œ ๋ฐฐ์šด ๋ฐฉ๋ฒ•๋Œ€๋กœ $139 \times 312$๋ฅผ ๊ณ„์‚ฐํ•ด ๋ณด๊ณ , ์ด ๋ฐฉ๋ฒ•์„ ๊ทธ๋Œ€๋กœ ์ปดํ“จํ„ฐ๋กœ ๊ตฌํ˜„ํ•ด ๋‚ธ๋‹ค๋ฉด $n$์ž๋ฆฌ ์ˆ˜๋ฅผ ๊ณฑ์…ˆํ•˜๋Š”๋ฐ ์–ด๋Š์ •๋„์˜ ์‹œ๊ฐ„์ด ๋“ค์ง€ ์˜ˆ์ธกํ•ด ๋ณด์„ธ์š”.

    (2) ์ดํ•˜, $x, y$๋Š” $B$์ง„๋ฒ•์˜ $n$์ž๋ฆฌ ์ˆ˜๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค. ๋จผ์ €, ์ ๋‹นํ•œ $m < n$์„ ๊ณจ๋ผ, $x = x_1 B^m + x_0$, $y = y_1 B^m + y_0$ ์ด๋ผ๊ณ  ์”์‹œ๋‹ค. $m$์„ $n$์˜ ์ ˆ๋ฐ˜์ด ๋˜๊ฒŒ ๊ณ ๋ฅด๋ฉด ๋ฉ๋‹ˆ๋‹ค.4

    (3) ์ด์ œ, $xy$ ๊ฐ€ $(x_1 B^m + x_0) (y_1 B^m + y_0)$ ์ด๋ฏ€๋กœ, $x_1y_1 B^{2m} + (x_1y_0 + x_0y_1)B^m + x_0y_0$์œผ๋กœ ๋‚˜ํƒ€๋‚ฉ๋‹ˆ๋‹ค. $x_1y_1, x_0y_0$์€ ๊ทธ๋Œ€๋กœ ๊ณ„์‚ฐํ•˜๊ณ , ๊ฐ€์šด๋ฐ ํ•ญ์„ ๊ณ„์‚ฐํ•˜๋Š” ๋Œ€์‹ , $(x_1 + x_0) (y_1 + y_0)$์„ ๊ณ„์‚ฐํ•˜๊ณ  ์•ž ๋‘๊ฐœ๋ฅผ ๋นผ๋ฉด ๊ฐ™์€ ํ•ญ์„ ์–ป์Šต๋‹ˆ๋‹ค.

    (4) ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ฆ๋ช…ํ•˜์„ธ์š”. Week 1์˜ Master Theorem.

  2. ($\star$)Closest Pair Problem : BOJ 2261
    ๋‹ค์Œ ๋ฌธ์ œ๋ฅผ ๊ณ ๋ฏผํ•˜๊ณ  ํ•ด๊ฒฐํ•ด ๋ด…์‹œ๋‹ค. $\R^2$ ์ƒ์˜ ์  $n$๊ฐœ์— ๋Œ€ํ•˜์—ฌ, ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋‘ ์  ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. ์กฐ๊ธˆ ๋” ์ˆ˜ํ•™์ ์œผ๋กœ๋Š”, $l = \min_{i, j} d(p_i, p_j)$ ์„ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ํ๋ฆ„์„ ๋”ฐ๋ผ๊ฐ€๋ฉฐ, ๋ถ„ํ•  ์ •๋ณต์ด ์–ผ๋งˆ๋‚˜ ๊ฐ•๋ ฅํ•œ ํˆด์ธ์ง€ ๋‹ค์‹œํ•œ๋ฒˆ ๋Š๊ปด๋ด…์‹œ๋‹ค.

    (1) ์ž๋ช…ํ•œ โ€˜์‰ฌ์šด ์•Œ๊ณ ๋ฆฌ์ฆ˜โ€™ ์€ $O(n^2)$ ์ž…๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์ด ๋ฌธ์ œ์— ๋Œ€ํ•ด $O(n \log^2 n)$, ๋‚˜์•„๊ฐ€ $O(n \log n)$ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ƒ๊ฐํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

    (2) ๋จผ์ €, Divide and Conquer๋ฅผ ์ƒ๊ฐํ•˜๊ธฐ ์œ„ํ•ด, $x$์ถ•์„ ๊ธฐ์ค€์œผ๋กœ ๋ฐ˜์œผ๋กœ ์ž๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค.

    (3) ๊ทธ๋Ÿฌ๋ฉด, [๋‘ ์ ์ด ์™ผ์ชฝ์— ์žˆ๋Š” ๊ฒฝ์šฐ], [๋‘ ์ ์ด ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” ๊ฒฝ์šฐ], [์–‘์ชฝ์—์„œ ํ•˜๋‚˜์”ฉ ๋ฝ‘๋Š” ๊ฒฝ์šฐ] ๋ฅผ ๊ฐ๊ฐ ํ’€๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์ด ์‹œ๊ฐ„ ๋ณต์žก๋„์— ์ „ํ˜€ ๋ฐœ์ „์ด ์—†์Œ์„ ๋ณด์ด์„ธ์š”.

    (4) ๊ทธ๋Ÿฌ๋‚˜, [์–‘์ชฝ] ์ผ€์ด์Šค๋ฅผ ์ •๋ง ๋ชจ๋‘ ํ™•์ธํ•ด์•ผ ํ• ๊นŒ์š”? ์–‡์€ Strip๋งŒ ๋ณด๋ฉด ์ถฉ๋ถ„ํ•จ์„ ๊ด€์ฐฐํ•˜์„ธ์š”.

    (5) Challenge ์–‘์ชฝ ์ผ€์ด์Šค์—์„œ, Strip ์•ˆ์˜ ์  $p_i$์— ๋Œ€ํ•ด, ์ตœ๋Œ€ 7๋ฒˆ์˜ ๋น„๊ต๋กœ ์ถฉ๋ถ„ํ•จ์„ ๋ณด์ด์„ธ์š”.

    (6) ์ด ๋ฐฉ๋ฒ•์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ฆ๋ช…ํ•˜๊ณ , ์–ด๋–ป๊ฒŒ ๋” ์ค„์ผ์ง€ ์ƒ๊ฐํ•ด ๋ณด์„ธ์š”.

  3. ํ–‰๋ ฌ ๊ณฑ์…ˆ ์ˆœ์„œ : BOJ 11049
    BOJ 11049๋ฒˆ์„ ๋ณด๊ณ , ์ด ๋ฌธ์ œ๋ฅผ ์–ด๋–ป๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค.

    (1) ๋‹จ์ˆœํ•˜๊ฒŒ๋Š” ํ’€ ๋ฐฉ๋ฒ•์ด ์ž˜ ๋– ์˜ค๋ฅด์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ํ•˜๋‚˜ ๊ฐ€๋Šฅํ•œ ๋ฐฉ๋ฒ•์€ ๋ชจ๋“  ๊ฐ€๋Šฅํ•œ ํ–‰๋ ฌ ๊ณฑ์…ˆ ์ˆœ์„œ๋ฅผ Naiveํ•˜๊ฒŒ ๋‚˜์—ดํ•˜๊ณ  ํ™•์ธํ•˜๋Š” ๊ฒƒ์ธ๋ฐ, ์ด ๋ฐฉ๋ฒ•์—์„œ ํ™•์ธํ•ด์•ผ ํ•  ๊ณฑ์…ˆ ์ˆœ์„œ๊ฐ€ ๋ช‡ ๊ฐ€์ง€์ผ๊นŒ์š”? ์ด๊ฑธ ๊ณ„์‚ฐํ•˜๋Š” ๋ฌธ์ œ๋Š” ์ƒ๋‹นํžˆ ์–ด๋ ต์Šต๋‹ˆ๋‹ค. ์–ธ์  ๊ฐ€ ์ˆ˜ํ•™ ์„ธ์…˜์„ ํ•˜๊ฒŒ ๋˜๋ฉด ์ƒ๊ฐํ•ด ๋ณด๊ธฐ๋กœ ํ•ฉ์‹œ๋‹ค.

    (2) ๋งˆ์ง€๋ง‰ ๊ณฑ์…ˆ์˜ ์œ„์น˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค.
    ๋งˆ์ง€๋ง‰ ๊ณฑ์…ˆ์˜ ์œ„์น˜๊ฐ€ $(A_1 A_2 \dots A_k)$์™€ $(A_{k+1} A_{k+2} \dots A_n)$ ์„ ๊ณฑํ•˜๋Š” ๊ฒƒ์ผ ๋•Œ...

    (3) DP[i][j] = i๋ฒˆ์งธ๋ถ€ํ„ฐ j๋ฒˆ์งธ๊นŒ์ง€์˜ ํ–‰๋ ฌ์„ ์ตœ๋Œ€ํ•œ ์ž˜ ๊ณฑํ–ˆ์„ ๋•Œ์˜ ์ตœ์†Œ ๋น„์šฉ ์ด๋ผ๊ณ  ์ •์˜ํ•ฉ์‹œ๋‹ค. ์ ํ™”์‹์„ ์„ธ์›Œ ๋ณด๊ณ , ๊ทธ ์ ํ™”์‹์„ ์–ด๋–ป๊ฒŒ ๋นจ๋ฆฌ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์„์ง€ ๊ณ ๋ฏผํ•ด ๋ณด์„ธ์š”.

  4. Knapsack Problem : BOJ 12865
    ์ด ๋ฌธ์ œ๋Š” ๋งค์šฐ ์œ ๋ช…ํ•œ 0-1 Knapsack์ด๋ผ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๊ฐ ๋ฌผํ’ˆ๋งˆ๋‹ค $w_i$์˜ ๋ฌด๊ฒŒ์™€ $v_i$์˜ ๊ฐ€์น˜๊ฐ€ ์žˆ๊ณ , ๊ฐ€๋ฐฉ์— ๋ฌด๊ฒŒ๊ฐ€ $W$ ์ดํ•˜๊ฐ€ ๋˜๊ฒŒ ๋„ฃ์–ด์•ผ ํ•  ๋•Œ ๊ฐ€์น˜๋ฅผ ์ตœ๋Œ€ํ™”ํ•˜์„ธ์š”.

    (1) Heuristic์€ ๋งค์šฐ ์ค‘์š”ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ผ๋ถ€์ด์ง€๋งŒ ์ด ๋ฌธ์ œ์—์„œ ๋จนํžˆ์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ํ˜น์‹œ Naiveํ•˜๊ฒŒ $v_i / w_i$ ๊ฐ€ ์ตœ๋Œ€์ธ๊ฒƒ๋ถ€ํ„ฐ ๋ฐ€์–ด๋„ฃ๋Š”๋‹ค๋Š” ์ƒ๊ฐ์„ ํ•˜์…จ๋‚˜์š”? ๊ฐ€๋ฐฉ์— 2์˜ ๋ฌด๊ฒŒ๋งŒ ๋„ฃ์„ ์ˆ˜ ์žˆ๊ณ , ๋ฌด๊ฒŒ๊ฐ€ 1, ๊ฐ€์น˜๊ฐ€ 5์ธ ๋ฌผ๊ฑด๊ณผ ๋ฌด๊ฒŒ๊ฐ€ 2, ๊ฐ€์น˜๊ฐ€ 6์ธ ๋ฌผ๊ฑด์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด ๋ณด์„ธ์š”.

    (2) DP ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ•˜๋Š” ์ข‹์€ ๋ฐฉ๋ฒ•์€, DP ํ…Œ์ด๋ธ”์„ ๋จผ์ € ๊ตฌ์ƒํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. DP[i][j] ๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•  ๋•Œ... ๋ผ๊ณ  ์‹œ์ž‘ํ•ฉ์‹œ๋‹ค. ์–ด๋–ป๊ฒŒ ์ •์˜ํ•ด์•ผ ํ• ๊นŒ์š”? ํžŒํŠธ : DP ์นธ์ˆ˜๋ฅผ $N \times W$ ๋กœ ์‹œ๋„ํ•ด ๋ด…์‹œ๋‹ค.

  5. DP on data structures : BOJ 15681
    ๊ณ ์ •๊ด€๋…์„ ๋ฒ„๋ฆฌ๋ฉด ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฃจํŠธ ์žˆ๋Š” ํŠธ๋ฆฌ์—์„œ, ๋…ธ๋“œ $x$์— ๋Œ€ํ•ด, ๊ทธ ๋…ธ๋“œ๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒํŠธ๋ฆฌ์˜ ์ •์ ์˜ ์ˆ˜๋ฅผ ๋น ๋ฅด๊ฒŒ ๋‹ตํ•˜๋ ค๋ฉด ์–ด๋–ป๊ฒŒ ํ• ๊นŒ์š”?

    • ์ด ๋ฌธ์ œ๋Š” ์ฟผ๋ฆฌํ˜• ๋ฌธ์ œ ๋ผ๊ณ  ๋ถ€๋ฅด๋Š” ํ˜•ํƒœ์ธ๋ฐ, โ€œ์ฟผ๋ฆฌโ€ ๋ผ๊ณ  ๋ถˆ๋ฆฌ๋Š” โ€œ์งˆ๋ฌธโ€์ด $Q$๊ฐœ ์ฃผ์–ด์ง€๊ณ  ์ด ์ฟผ๋ฆฌ๋“ค์— ๋‹ตํ•ด์•ผ ํ•˜๋Š” ์ƒํ™ฉ์ž…๋‹ˆ๋‹ค. ์ž๋ฃŒ๊ตฌ์กฐ์— ๋Œ€ํ•ด ์–˜๊ธฐํ•  ๋•Œ, OO์— ๋Œ€ํ•œ ์ฟผ๋ฆฌ๋ฅผ ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ ๋ผ๋Š” ์‹์œผ๋กœ ์ดํ•ดํ•œ ๊ธฐ์–ต์ด ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

    • ์ฟผ๋ฆฌ๊ฐ€ ๋“ค์–ด์˜ฌ ๋•Œ๋งˆ๋‹ค ํŠธ๋ฆฌ๋ฅผ ๋Œ์•„๋ณด๋ฉด์„œ ๋Œ€๋‹ตํ•˜๋ฉด, ํ•œ ์ฟผ๋ฆฌ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐ $O(n)$ ์‹œ๊ฐ„์ด ๋“ค๊ณ  (๋ฃจํŠธ๋งŒ ๊ณ„์† ๋ฌผ์–ด๋ณผ ์ˆ˜๋„ ์žˆ์œผ๋‹ˆ๊นŒ), ์ „์ฒด $O(qn)$ ์‹œ๊ฐ„์ด ๋“ ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค. ๋‹น์—ฐํžˆ ์ด ๋ณต์žก๋„๋Š” ์šฉ๋‚ฉํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

    • ์ฟผ๋ฆฌ๋‹น $O(1)$ ์— ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด, ๋ฏธ๋ฆฌ ์‹œ๊ฐ„์„ ์ข€ ์จ์„œ ์ „์ฒ˜๋ฆฌ (Preprocessing) ํ•˜๊ณ , ์ฟผ๋ฆฌ๊ฐ€ ๋“ค์–ด์˜ค๋ฉด ๊ทธ๋•Œ๊ทธ๋•Œ ๋‹ตํ•ด์ฃผ๋ฉด ์–ด๋–จ๊นŒ์š”? ์ฆ‰, $O(n + q)$ ์— ํ•ด๊ฒฐํ•˜๊ฒ ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค.

  1. โ€˜๊ธฐ์–ตํ•˜๋‹คโ€™ ๋ผ๋Š” ๋œป์˜ memorization์ด ์•„๋‹™๋‹ˆ๋‹ค. โ€˜๋ฉ”๋ชจํ•˜๋‹คโ€™ ๋ผ๊ณ  ๋ฐ›์•„๋“ค์—ฌ ์ฃผ์„ธ์š”ย โ†ฉ

  2. ์ด๋ ‡๊ฒŒ ์จ๋†“๊ธฐ๋Š” ํ–ˆ์ง€๋งŒ $X, Y$๊ฐ€ ์ˆ˜์ผ ๋•Œ๋งŒ ์‚ฌ์šฉ๊ฐ€๋Šฅํ•œ ๊ฒƒ์€ ์•„๋‹™๋‹ˆ๋‹ค. ํ•ฉ๋ฆฌ์ ์ธ Order๋ฅผ ์ค„ ์ˆ˜ ์žˆ์œผ๋ฉด ๋˜๊ฒ ์ฃ ?ย โ†ฉ

  3. Andrey Kolmogorov. ์ฃผ๋กœ ํ™•๋ฅ ๋ก ์„ ์—ฐ๊ตฌํ–ˆ์ง€๋งŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—๋„ ์ƒ๋‹นํžˆ ๋งŽ์€ ๊ด€์‹ฌ์„ ๊ฐ€์กŒ๋˜ ์ˆ˜ํ•™์ž์ž…๋‹ˆ๋‹คย โ†ฉ

  4. ์•„์ง โ€œ$n$์ด ํ™€์ˆ˜๋ฉด ์–ด๋–ป๊ฒŒ ํ•˜์ง€โ€ ๋ผ๋Š” ๊ณ ๋ฏผ์ด ๋“ ๋‹ค๋ฉด, Big-O Notation์— ๋Œ€ํ•œ โ€œ์ฒ ํ•™โ€ ์ด ๋ถ€์กฑํ•œ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ใ…Žใ…Žย โ†ฉ