๋ถํ ์ ๋ณต(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)
์ด๋ค.