๋ถ„ํ• ์ •๋ณต(Divide & Conquer)

๋ถ„ํ• ์ •๋ณต(Divide & Conquer)์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ๋‘˜ ์ด์ƒ์˜ ๋ถ€๋ถ„ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆˆ ๋’ค, ๊ฐ ๋ฌธ์ œ์— ๋Œ€ํ•œ ๋‹ต์„ ์žฌ๊ท€ ํ˜ธ์ถœ์„ ์ด์šฉํ•ด ๊ณ„์‚ฐํ•˜๊ณ , ๊ฐ ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ๋‹ต์œผ๋กœ ๋ถ€ํ„ฐ ์ „์ฒด ๋ฌธ์ œ์˜ ๋‹ต์„ ๊ณ„์‚ฐํ•ด ๋‚ธ๋‹ค. ๋ถ„ํ•  ์ •๋ณต์˜ ์žฅ์ ์€ ๋งŽ์€ ๊ฒฝ์šฐ ๊ฐ™์€ ์ž‘์—…์„ ๋” ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•ด ์ค€๋‹ค.


๋ถ„ํ•  ์ •๋ณต์˜ ๊ตฌ์„ฑ์š”์†Œ

  • Divide : ๋” ์ž‘์€ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆˆ๋‹ค.
  • Merge : ๋‚˜๋ˆˆ ๋ฌธ์ œ์—์„œ ๊ตฌํ•œ ๋‹ต์„ ๋ณ‘ํ•ฉํ•ด ์›๋ž˜ ๋‹ต์„ ๊ตฌํ•œ๋‹ค.
  • Base Case: ๋” ์ด์ƒ ๋ถ„ํ•  ํ•˜์ง€ ์•Š๊ณ , ๊ณง์žฅ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ.

์˜ˆ์ œ: ์ˆ˜์—ด์˜ ๋น ๋ฅธ ํ•ฉ

1๋ถ€ํ„ฐ n๊นŒ์ง€์˜ ํ•ฉ์„ n๊ฐœ์˜ ์กฐ๊ฐ์œผ๋กœ ๋‚˜๋ˆˆ๋’ค, ์ด๋“ค์„ ๋ฐ˜์œผ๋กœ ์ž˜๋ผ n/2๊ฐœ์˜ ์กฐ๊ฐ๋“ค๋กœ ๋งŒ๋“ค์–ด์ง„ ๋ถ€๋ถ„ ๋ฌธ์ œ๋ฅผ ๋‘๊ฐœ ๋งŒ๋“ ๋‹ค. (ํŽธ์˜์ƒ n์ด ์ง์ˆ˜๋ผ๊ณ  ๊ฐ€์ •)

fastSum(n)
= 1 + 2 + ... + n
= (1 + 2 + ... + n/2) + ((n/2 + 1) + ... + n)
= fastSum(n/2) + ((n/2 + 1) + ... + n)

์ฒซ๋ฒˆ์งธ ๋ฌธ์ œ๋Š” fastSum(n/2) ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋‘๋ฒˆ์งธ ๋ถ€๋ถ„ ๋ฌธ์ œ๋Š” ๊ทธ๋ ‡์ง€ ์•Š๋‹ค. ๋ฌธ์ œ๋ฅผ ์žฌ๊ท€์ ์œผ๋กœ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” ๊ฐ ๋ถ€๋ถ„ ๋ฌธ์ œ๋ฅผ 1๋ถ€ํ„ฐ n๊นŒ์ง€์˜ ํ•ฉ ๊ผด๋กœ ํ‘œํ˜„ํ•ด์•ผ ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ๋‘๋ฒˆ์งธ ๋ถ€๋ถ„ ๋ฌธ์ œ๋ฅผ fastSum(x)๋ฅผ ํฌํ•จํ•˜๋Š” ํ˜•ํƒœ๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค.

= fastSum(n/2) + ((1 + n/2) + (2 + n/2) + ... + (n/2 + n/2))
= fastSum(n/2) + (n/2 * n/2) + fastSum(n/2)

์ด๋Ÿฌํ•œ ์•„์ด๋””์–ด๋ฅผ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™๋‹ค. ๋งŒ์•ฝ n์ด ํ™€์ˆ˜์ธ ๊ฒฝ์šฐ์—๋Š” ์ง์ˆ˜์ธ n-1๊นŒ์ง€์˜ ํ•ฉ์„ ์žฌ๊ท€ ํ˜ธ์ถœ๋กœ ๊ณ„์‚ฐํ•˜๊ณ  n์„ ๋”ํ•ด ๋‹ต์„ ๊ตฌํ•˜๋ฉด ๋œ๋‹ค.

// 1+2+...+n์„ ๋ฐ˜ํ™˜
const fastSum = (n:number):number => {
    if(n === 1) return 1; // Base Case
    if(n % 2) return fastSum(n-1) + n; // n์ด ํ™€์ˆ˜์ธ ๊ฒฝ์šฐ
    return 2 * fastSum(n/2) + (n/2)*(n/2);
}

์‹œ๊ฐ„๋ณต์žก๋„ ๋ถ„์„

fastSum()์€ ํ˜ธ์ถœ๋  ๋•Œ๋งˆ๋‹ค ์ตœ์†Œํ•œ ๋‘ ๋ฒˆ์— ํ•œ ๋ฒˆ ๊ผด๋กœ n์ด ์ ˆ๋ฐ˜์œผ๋กœ ์ค„์–ด๋“ ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹คํ–‰์‹œ๊ฐ„์€ O(logn)์ด๋‹ค.