๋๋ ๋ํ์์ ์ด๋์ ๋ฐฐ์ ๋ฐ์๋ค. ๋๋ ๊ทธ๊ฒ์ ์ง์ผ๋ก ๊ฐ์ ธ ์์ ๊ทธ๊ฒ์ ํด๊ฒฐํ๊ธฐ ์ํด ์๊ณ ๋ฆฌ์ฆ์ ํ๋ก๊ทธ๋๋ฐํ๋ ค๊ณ ์๋ํ๋ค. ๊ทธ๋ํ์ ๊ด๋ จ์ด ์๊ณ ์ฐ๊ฒฐ๋ ๊ตฌ์ฑ ์์๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ผ๊ณ ์๊ฐํ๋ค.
๊ทธ๋ฐ ๋ค์ ๋ง์์ ๋ค์ด์จ ๊ฐ์ฅ ์ฌ์ํ ๊ฒ์ ๊ฐ์ฌ์๊ฒ ๋ณด์ฌ์ฃผ์์ต๋๋ค. ๊ฐ๋จํ ๊ด์ฐฐ ํ, ๊ทธ๋ ๋ด ์๋ฃจ์ ์ ๋ฐํ์ ๋ณต์ก์ฑ์ด ๋ถ๊ฐํผํ๊ณ ๋ ํจ์จ์ ์ธ ๊ฒ์ ๋ณด์ฌ์ฃผ์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ๊ณ์ฐ ๋ณต์ก์ฑ์ ๋ํด ์ ํ ๋ชจ๋ฅด๋ ํ๋ก๊ทธ๋๋จธ์ ์ ํต์ด ์์ต๋๋ค (์ ๋ ๊ทธ ์ค ํ๋์์ต๋๋ค). ํ๋ก๊ทธ๋๋จธ๊ฐ ๊ณ์ฐ ๋ณต์ก์ฑ์ ๋ํด ์ ํ ๋ชจ๋ฅธ๋ค๋ฉด ๋ฌธ์ ๊ฐ ์์ต๋๊น?
๋ต๋ณ
์, ๊ณ์ฐ ๋ณต์ก์ฑ์ ๋ํด ์๋ ๊ฒ์ด ์ง์งํ ํ๋ก๊ทธ๋๋จธ์๊ฒ๋ ํ์์ ๋๋ค. ๊ฑฐ๋ํ ๋ฐ์ดํฐ ์ธํธ๋ฅผ ๋ค๋ฃจ์ง ์๋ ํ ๋ณต์ก์ฑ์ ๋ชจ๋ฅด๋ ๊ฒ์ด ์ข์ง๋ง ์ฌ๊ฐํ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ ค๋ฉด ํ์ํฉ๋๋ค.
ํน์ ๊ฒฝ์ฐ์ ์ฐ๊ฒฐ๋ ๊ตฌ์ฑ ์์๋ฅผ ์ฐพ๋ ์๋ ์ต๋ ๋ ธ๋์ ๊ทธ๋ํ์์ ์๋ํ์ ์ ์์ต๋๋ค . ๊ทธ๋ฌ๋ 100.000 ๊ฐ์ ๋ ธ๋๋ก ๊ทธ๋ํ๋ฅผ ์๋ํ๋ฉด ๊ฐ์ฌ์ ์๊ณ ๋ฆฌ์ฆ์ด 1 ์ด ์์์ด๋ฅผ ๊ด๋ฆฌํ์ ๊ฒ์ ๋๋ค.ํ์ง๋ง ์๊ณ ๋ฆฌ์ฆ์ (๋ณต์ก๋๊ฐ ์ผ๋ง๋ ๋์์ง์ ๋ฐ๋ผ) 1 ์๊ฐ, 1 ์ผ ๋๋ ์ฌ์ง์ด 1 ์์์ ๊ฐ์ง ๊ฒ์ ๋๋ค.
100100.000
์๊ณ ๋ฆฌ์ฆ ๊ณผ์ ์์ ํ์๋ค์ด ํํ ์ ์ง๋ฅด๋ ์ค์๋ ๋ค์๊ณผ ๊ฐ์ด ๋ฐฐ์ด์ ๋ฐ๋ณตํ๋ ๊ฒ์ ๋๋ค.
while array not empty
examine first element of array
remove first element from array
์ด๊ฒ์ ๊ฐ์ฅ ์๋ฆ๋ค์ด ์ฝ๋๋ ์๋์ง๋ง ๋ณต์กํ ํ๋ก๊ทธ๋จ์์๋ ํ๋ก๊ทธ๋๋จธ๊ฐ ์์ง ๋ชปํ๋ ์ฑ ํ์ ๋ ์ ์์ต๋๋ค. ์,์ด ํ๋ก๊ทธ๋จ์ ๋ฌธ์ ์ ์ ๋ฌด์์ ๋๊น?
์์ ์ ๋ฐ์ดํฐ ์ธํธ์์ ์คํํ๋ค๊ณ ๊ฐ์ ํ์ญ์์ค . ๋ค์ ํ๋ก๊ทธ๋จ๊ณผ ๋น๊ตํ ๋ ์ด์ ํ๋ก๊ทธ๋จ์ 50.000 ๋๋ฆฌ๊ฒ ์คํ๋ฉ๋๋ค .
100.00050.000
while array not empty
examine last element of array
remove last element from array
ํ๋ก๊ทธ๋จ์ ๋ฐฐ ๋น ๋ฅด๊ฒ ์คํํ๋ ๋ฐ ํ์ํ ์ง์์ ๋ณด์ ํ๋ ๊ฒ์ด ํ๋ก๊ทธ๋๋จธ์๊ฒ๋ ์ค์ํ ์ผ ์ด๋ผ๋ ๋ฐ ๋์ํฉ๋๋ค . ๋ ํ๋ก๊ทธ๋จ์ ์ฐจ์ด์ ์ ์ดํดํ๋ ค๋ฉด ๋ณต์ก์ฑ ์ด๋ก ์ ๋ํ ๊ธฐ๋ณธ ์ง์๊ณผ ํ๋ก๊ทธ๋๋ฐ์ค์ธ ์ธ์ด์ ํน์ ์ฌํญ์ ๋ํ ์ง์์ด ํ์ํฉ๋๋ค.
50.000์์ฌ ์ฝ๋ ์ธ์ด์์ โ๋ฐฐ์ด์์ ์์ ์ ๊ฑฐโ๋ ๋ชจ๋ ์์๋ฅผ โโ์ผ์ชฝ์์ ํ ์์น์์ ์ ๊ฑฐ๋๋ ์์์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํฉ๋๋ค. ์ด๋ ๊ฒํ๋ฉด ๋ง์ง๋ง ์์๋ฅผ ์ ๊ฑฐํ๋ ์์ ์ด ๊ฐ๋๋ฏ๋ก ํ๋์ ์์์ ๋ง ์ํธ ์์ฉํ๋ฉด๋ฉ๋๋ค. ์ฒซ ๋ฒ์งธ ์์ ๋ฅผ ์ ๊ฑฐํ๋ ค๋ฉด ์ฒซ ๋ฒ์งธ ์์๋ฅผ ์ ๊ฑฐํ๊ธฐ ์ํด ๋ค๋ฅธ ๋ชจ๋ n โ 1 ์์๋ฅผ ํ ์์น ์ผ์ชฝ์ผ๋ก ์ด๋ํด์ผํ๋ฏ๋ก O ( n ) ์ ๋๋ค.
O(1)O(n)
nโ1
๋ณต์ก์ฑ์ ๋งค์ฐ ๊ธฐ๋ณธ์ ์ธ ์ด๋์ ์ฒซ ๋ฒ์งธ ํ๋ก๊ทธ๋จ์ด ์ํ ํ ๊ฒ์์ ์ฆ๋ช ํ๋ ๊ฒ์ ๋๋ค ๋ ๋ฒ์งธ ํ๋ก๊ทธ๋จ์n ๊ฐ์์์ ๋ง ์ฌ์ฉํ์ง๋ง 2 n2๊ฐ์์์ ์ ๋๋ค. ๋น์ ์ด์ ์ฐ๊ฒฐํ๋ฉดN=100.000๋น์ ์ ํ๋ ๊ฐ์ ํ๋ก๊ทธ๋จ์ด ๋ํญ๋ณด๋ค ํจ์จ์ ์ธ ๋ค๋ฅธ๋ณด๋ค ๋ณผ ์ ์์ต๋๋ค.
12์2์
n=100.000
์ด๊ฒ์ ๋จ์ง ์ฅ๋๊ฐ์ ์์ด์ง๋ง ๋ ํ๋ก๊ทธ๋จ์ ์ฐจ์ด์ ์ ๋งํ๊ธฐ ์ํด์๋ ๋ณต์ก์ฑ์ ๋ํ ๊ธฐ๋ณธ ์ดํด๊ฐ ์ด๋ฏธ ํ์ํฉ๋๋ค. ์ค์ ๋ก์ด ์ค์๊ฐ์๋๋ณด๋ค ๋ณต์กํ ํ๋ก๊ทธ๋จ์ ๋๋ฒ๊น / ์ต์ ํํ๋ ค๊ณ ํ๋ฉด ์ฐพ๊ธฐ์ ๋ ๋ง์ ์ดํด๊ฐ ํ์ํฉ๋๋ค ๋ฒ๊ทธ๊ฐ ์ด๋์ ์๋์ง. ์ด๋ฐ ์์ผ๋ก ๋ฐฐ์ด์์ ์์๋ฅผ ์ ๊ฑฐํ๋ ๊ฒ๊ณผ ๊ฐ์ ์ค์๋ ์ฝ๋์ ์ถ์ํ์ ์ํด ์ ์จ๊ฒจ ์ง ์ ์์ต๋๋ค.
๋ณต์ก์ฑ์ ์ ์ดํดํ๋ฉด ๋ ๊ฐ์ง ์ ๊ทผ ๋ฐฉ์์ ๋น๊ตํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋ ๋์์ด๋ฉ๋๋ค. ์ฐ๊ฒฐ๋ ๊ตฌ์ฑ ์์ ๋ฌธ์ ๋ฅผ ์ค์ค๋ก ํด๊ฒฐํ๊ธฐ์ํ ๋ ๊ฐ์ง ๋ค๋ฅธ ์ ๊ทผ ๋ฐฉ์์ ์๊ฐํด ๋๋ค๊ณ ๊ฐ์ ํด ๋ด ์๋ค. ๊ตฌ์ฑ ์์ ๊ฐ์ ๊ฒฐ์ ํ๋ ค๋ฉด ๋ณต์ก์ฑ์ ์ถ์ ํ๊ณ ๋ ๋์ ๋ฐฉ๋ฒ์ ์ ํํ ์ ์๋ค๋ฉด ๋งค์ฐ ์ ์ฉ ํ ๊ฒ์ ๋๋ค.
๋ต๋ณ
์ด๊ฒ์ Tom van der Zanden์ ๋ต๋ณ์ ๋ํ ๋ฐ๋ฐ์ ๋๋ค .
๋ฌธ์ ๋ ๋๋ถ๋ถ 50.000 ๋ฐฐ ๋๋ฆฌ๋ค๋ ๊ฒ์ ๋๋ค (๋ฌผ๋ก Google์์ ์์ ํ์ง ์๋ ํ).
์์ ์ ๋ง์ดํฌ๋ก ์ด๊ฐ ๊ฑธ๋ฆฌ๊ฑฐ๋ N์ด ํน์ ์๊ณ ๊ฐ (์์ฆ ์ํ๋๋ ์ฝ๋ฉ์ ๋ง์ ๋ถ๋ถ)์ ์ด๊ณผํ์ง ์์ผ๋ฉด ๊ฒฐ์ฝ ์ค์ํ์ง ์์ต๋๋ค. ์ด๋ฌํ ๊ฒฝ์ฐ ๊ณ์ฐ ๋ณต์ก์ฑ์ ์๊ฐํ๋ฉด ์๊ฐ๊ณผ ๋์ ๋ญ๋นํ๊ฒ๋ฉ๋๋ค.
๊ณ์ฐ ๋ณต์ก๋๋ ์ ๋ฌด์ธ๊ฐ๊ฐ ๋๋ฆฌ๊ฒ ์งํ๋๊ฑฐ๋ ํฌ๊ธฐ๊ฐ ์ฌํ๊ฒ ์ ํ ๋ ์ ์๋์ง, ๊ทธ๋ฆฌ๊ณ ๊ทธ๊ฒ์ ๊ฐ์ ํ๋ ๋ฐฉ๋ฒ์ ์ดํดํ๋ ๋๊ตฌ์ด์ง๋ง, ๋๋ถ๋ถ์ ์๊ฐ์ ์์ ํ ์ง๋์น ๊ฒ์ ๋๋ค.
๋๋ 5 ๋ ์ด์ ๋์ ์ ๋ฌธ ํ๋ก๊ทธ๋๋จธ์์ผ๋ฉฐ ๋ฃจํ O (M * N) ๋ด์์ ๋ฃจํ ํ ๋ ๊ณ์ฐ ๋ณต์ก๋์ ๋ํด ์๊ฐํ ํ์๊ฐ ์์์ต๋๋ค. ์๋ํ๋ฉด ํญ์ ์์ ์ด ์ค์ ๋ก ๋น ๋ฅด๊ฑฐ๋ M๊ณผ N์ด ๋๋ฌด ๋น ๋ฅด๊ธฐ ๋๋ฌธ์ ๋๋ค. ์์.
ํ๋ก๊ทธ๋๋ฐ ์์ ์ํ๋ ์ฌ๋์๊ฒ๋ ํจ์ฌ ์ค์ํ๊ณ ์ผ๋ฐ์ ์ผ๋ก ์ฌ์ฉ๋๋ฉฐ ์ดํดํ๊ธฐ ์ด๋ ค์ด ๊ฒ๋ค์ด ์์ต๋๋ค (์ค๋ ๋ฉ ๋ฐ ํ๋กํ์ผ ๋ง์ ์ฑ๋ฅ ์์ญ์์ ์ข์ ์์ ๋๋ค).
๋ฌผ๋ก ๊ณ์ฐ ๋ณต์ก๋๋ฅผ ์ดํดํ์ง ์๊ณ ๋ ๊ฒฐ์ฝ ํ ์์๋ ์ผ์ด ์์ง๋ง (์ : ์ฌ์ ์์ ์๋๊ทธ๋จ ์ฐพ๊ธฐ) ๋๋ถ๋ถ์ ๊ฒฝ์ฐ ํ์ํ์ง ์์ต๋๋ค.
๋ต๋ณ
์ ๋ ์ฝ 30 ๋ ๋์ ๊ณ์ฝ์ ๋ฐ ์ง์์ผ๋ก ์ผํ๋ฉด์ ์ํํธ์จ์ด๋ฅผ ๊ฐ๋ฐํด ์์ผ๋ฉฐ ๊ฝค ์ฑ๊ณต์ ์ด์์ต๋๋ค. ๋์ ์ฒซ ๋ฒ์งธ ์ธ์ด๋ ๊ธฐ๋ณธ ์ด์์ง๋ง ์ ์ ํ์ ์์ ์์์์ ์ ์ ํ ์๋๋ฅผ ๋ด๋๋ก ๊ธฐ๊ณ ์ธ์ด๋ฅผ ๋น ๋ฅด๊ฒ ๊ฐ๋ฅด์ณค์ต๋๋ค. ๋ช ๋ ๋์ ํ๋กํ์ผ ๋ฌ์์ ๋ง์ ์๊ฐ์ ๋ณด๋์ผ๋ฉฐ ๋น ๋ฅด๊ณ ๋ฉ๋ชจ๋ฆฌ ํจ์จ์ ์ธ ์ต์ ํ ์ฝ๋ ์์ฑ์ ๋ํด ๋ง์ ๊ฒ์ ๋ฐฐ์ ์ต๋๋ค.
๋งํ ๊ฒ๋์์ด, ๋๋ ์ค์ค๋ก ๊ฐ๋ฅด์น๋ค. ๋ช ๋ ์ ์ ์ธํฐ๋ทฐ๋ฅผ ์์ํ๊ธฐ ์ ๊น์ง๋ O ํ๊ธฐ๋ฒ์ ์ ํ ์ ์ด ์์ต๋๋ค. ์ธํฐ๋ทฐ ์ค์๋ ์ ๋ฌธ ์์ ์์ ์ ๋ ๋์ค์ง ์์ต๋๋ค. ๊ทธ๋์ ๋๋ ์ธํฐ๋ทฐ์์ ๊ทธ ์ง๋ฌธ์ ๋ค๋ฃจ๊ธฐ ์ํด ๊ธฐ์ด๋ฅผ ๋ฐฐ์์ผํ์ต๋๋ค.
์ ๋ณด๋ฅผ ์ฝ์ ์์๋ ์ฌ์ฆ ๋ฎค์ง์ ์ธ ๊ฒ ๊ฐ์ต๋๋ค. ๋ ์ฌ์ ํ ์ ์ฌ์ํ ์ ์์ต๋๋ค. ๋๋ ํด์ ํ ์ด๋ธ (ํด์ ํ ์ด๋ธ์ด ์ด๋ฏธ ๋ฐ๋ช ๋์๋ค๋ ๊ฒ์ ์๊ธฐ ์ ์ ํด์ ํ ์ด๋ธ์ ๋ฐ๋ช ํ๋ค)๊ณผ ๋ค๋ฅธ ์ค์ํ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ ๋ํด ์๊ณ ์์ผ๋ฉฐ ํ๊ต์์ ๊ฐ๋ฅด์น์ง ์๋ ๋ช ๊ฐ์ง ํธ๋ฆญ์ ์ ์๋ ์์ต๋๋ค. ๊ทธ๋ฌ๋ ๋๋์ด ์ง์ ์์ ์ฑ๊ณตํ๊ธฐ ์ํด์๋ ์ธ๋์ ๊ฐ๊ฑฐ๋ ์ธํฐ๋ทฐ ์ค์ ๋ฌผ์ด๋ณผ ์ง๋ฌธ์ ๋ํ ๋ต์ ๋ฐฐ์์ผํ๋ค๋ ๊ฒ์ด ์ง์ค์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค.
๋ง๋ถ์ฌ์, ๋๋ ๊ฐ์ฅ ์ต๊ทผ์ ํ๋ก ํธ ์๋ ์น ๊ฐ๋ฐ์ ์ญํ ์ ์ํด ์ธํฐ๋ทฐํ์ต๋๋ค. ๊ทธ๋ค์ ๋ต์ด ๊ณ์ฐ์ ๋ณต์ก์ฑ๊ณผ ๋์์ ๋ํ ์ง์์ ํ์๋กํ๋ ์ง๋ฌธ์ ๋์๊ฒ ๋ฌผ์๋ค. ๋๋ 20 ๋ ์ ์ ์ํ์ ๋ํด ๋ค์ ์ ํํ๊ฒ ๋๋ตํ๊ธฐ์ ์ถฉ๋ถํ ์ํ์ ๊ธฐ์ตํ์ง๋ง ์ฝ๊ฐ ํผ๋ ์ค๋ฌ์ ์ต๋๋ค. ํ๋ฐํธ ์๋ ๊ฐ๋ฐ์์ ๋ก๊ทธ๋ฅผ ์ฌ์ฉํ ํ์๊ฐ ์์์ต๋๋ค.
๋น์ ์๊ฒ ํ์ด์ ๋น๋๋ค!
๋ต๋ณ
์ง๋ฌธ์ ๋งค์ฐ ์ฃผ๊ด์ ์ด๋ฏ๋ก ๋ต์ด ๋ฌ๋ ค ์๋ค๊ณ ์๊ฐํฉ๋๋ค .
์๋์ ๋ฐ์ดํฐ๋ก ์์ ํ๋ ๊ฒฝ์ฐ์๋ ๊ทธ๋ค์ง ์ค์ํ์ง ์์ต๋๋ค. ์ด ๊ฒฝ์ฐ ์ผ๋ฐ์ ์ผ๋ก ์ธ์ด์ ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ ๊ฐ์ ๊ฒ์ ์ฌ์ฉํ๋ ๊ฒ์ด ์ข์ต๋๋ค.
๊ทธ๋ฌ๋ ๋ง์ ์์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ๊ฑฐ๋ ๋ค๋ฅธ ์ด์ ๋ก ํ๋ก๊ทธ๋จ์ด ๋น ๋ฅด๋ค๊ณ ์ฃผ์ฅํ๋ ๊ฒฝ์ฐ ๊ณ์ฐ ๋ณต์ก์ฑ์ ์ดํดํด์ผํฉ๋๋ค. ๊ทธ๋ ์ง ์์ผ๋ฉด ์ด๋ป๊ฒ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํด์ผํ๋์ง ๋๋ ์ผ๋ง๋ ๋นจ๋ฆฌ ํด๊ฒฐํ ์ ์๋์ง ์ด๋ป๊ฒ ์ ์ ์์ต๋๊น? ๊ทธ๋ฌ๋ ์ด๋ก ์ ์ดํดํ๋ ๊ฒ๋ง์ผ๋ก๋ ์ ๋ง ์ข์ ํ๋ก๊ทธ๋๋จธ๊ฐ ๋๊ธฐ์๋ ์ถฉ๋ถํ์ง ์์ต๋๋ค. ๋งค์ฐ ๋น ๋ฅธ ์ฝ๋๋ฅผ ์์ฑํ๋ ค๋ฉด ๋จธ์ ์๋ ๋ฐฉ์ (์บ์, ๋ฉ๋ชจ๋ฆฌ ๋ ์ด์์, ๋ช ๋ น์ด ์ธํธ) ๋ฐ ์ปดํ์ผ๋ฌ์ ๊ธฐ๋ฅ (์ปดํ์ผ๋ฌ๊ฐ ์ต์ ์ ๋คํ์ง๋ง ์๋ฒฝํ์ง๋ ์์)์ ์ดํดํด์ผํฉ๋๋ค.
๊ฐ๋จํ ๋งํด์, ๋ณต์ก์ฑ์ ์ดํดํ๋ฉด ๋ถ๋ช ํ ๋ ๋์ ํ๋ก๊ทธ๋๋จธ๊ฐ ๋ ๊ฒ์ ๋๋ค.
๋ต๋ณ
์ค์ํ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋ฐํ๋ ์ฌ๋์ด ์๊ณ ๋ฆฌ์ฆ์ ๋ณต์ก์ฑ์ ์ดํดํ์ง ๋ชปํ๋ฉด ๋ฌธ์ ๊ฐ๋ฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ์๋ ์ผ๋ฐ์ ์ผ๋ก ์ฑ๋ฅ ํน์ฑ์ด ์ฐ์ํ ๊ตฌํ ํ์ง์ ์์กดํฉ๋๋ค. ๋ณต์ก์ฑ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ฑ๋ฅ ํน์ฑ์ ์ ์ผํ๊ฒ ๊ธฐ์ฌํ๋ ๊ฒ์ ์๋์ง๋ง ์ค์ํ ๊ฒ์ ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ๋ณต์ก์ฑ์ ์ดํดํ์ง ๋ชปํ๋ ์ฌ๋์ ์ ์ฉํ ์ฑ๋ฅ ํน์ฑ์ ๊ฐ์ง ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋ฐํ ๊ฐ๋ฅ์ฑ์ด ์ ์ต๋๋ค.
์ฌ์ฉ ๊ฐ๋ฅํ ์๊ณ ๋ฆฌ์ฆ์ ํ์ง์ด ์ข๋ค๊ณ ๊ฐ์ ํ๋ฉด ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉ์์๊ฒ๋ ๋ณ ๋ฌธ์ ๊ฐ๋์ง ์์ต๋๋ค. ์ด๋ ์ค์ํ๊ณ ์ ์ ์ ๋ ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ๊ฐ์๋ ์ธ์ด๋ฅผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์์๊ฒ ํด๋น๋ฉ๋๋ค. ์๊ตฌ์ ๋ง๋ ์๊ณ ๋ฆฌ์ฆ์ ์ ํํ๋ ๋ฐฉ๋ฒ ๋ง ์๊ณ ์์ผ๋ฉด๋ฉ๋๋ค. ๋ณต์ก์ฑ์ ์ข ์ข ์ ํํ๋ ๊ธฐ์ค ์ค ํ๋์ด๊ธฐ ๋๋ฌธ์ ๋ผ์ด๋ธ๋ฌ๋ฆฌ ๋ด์์ ์ฌ์ฉ ๊ฐ๋ฅํ ํน์ ์ ํ์ ์ฌ๋ฌ ์๊ณ ๋ฆฌ์ฆ (์ : ์ ๋ ฌ)์ด์๋ ๊ฒฝ์ฐ ๋ฌธ์ ๊ฐ ๋ฐ์ํฉ๋๋ค. ๋ณต์ก์ฑ์ ์ดํดํ์ง ๋ชปํ๋ ๊ฐ๋ฐ์๋ ์์ ์ ์์ ์ ํจ๊ณผ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ ์ ํํ๋ ๊ธฐ์ด๋ฅผ ์ดํดํ ์ ์์ต๋๋ค.
๊ทธ๋ฐ ๋ค์ ๋น ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์ ์ด์ ์ ๋ง์ถ๋ ๊ฐ๋ฐ์๊ฐ ์์ต๋๋ค (๋ ๋์ ์ค๋ช ์ ์ํจ). ์๋ฅผ ๋ค์ด, ์ง๊ด์ ์ธ ์ฌ์ฉ์ ์ธํฐํ์ด์ค ๊ฐ๋ฐ์ ์ค์ ์ ๋ ์ ์์ต๋๋ค. ์ด๋ฌํ ๊ฐ๋ฐ์๋ ์ข ์ข ์๊ณ ๋ฆฌ์ฆ์ด๋ ๋ณต์กํ ๊ฒ์ ๋ํด ๊ฑฑ์ ํ ํ์๊ฐ ์์ง๋ง ๋ผ์ด๋ธ๋ฌ๋ฆฌ ๋ ๋ค๋ฅธ ์ฝ๋๋ฅผ ๊ณ ํ์ง๋ก ๊ฐ๋ฐํ ์๋ ์์ต๋๋ค.
๋ต๋ณ
์์ ํ๋ ๋ฐ์ดํฐ์ ์์ด ์๋๋ผ ๊ฐ๋ฐํ๋ ํ๋ก๊ทธ๋จ์ ์ข ๋ฅ์ ๋ฐ๋ผ ๋ค๋ฆ ๋๋ค.
๊ฐ๋ ์ ๋ณต์ก์ฑ์ ๋ํด ๋ชจ๋ฅด๋ ํ๋ก๊ทธ๋๋จธ์๊ฒ ์ ํ๋ฅผ ๊ฑธ์ด ๋ณด์.
๋ฉ์ฒญํ ํ๋ก๊ทธ๋๋จธ๋ ๋ค์์ ์ํ ํ ์ ์์ต๋๋ค.
- ๋น ๋ฐ์ดํฐ ๋ฐ์ดํฐ๋ฒ ์ด์ค ๊ฐ๋ฐ-๋ฐ์ดํฐ๋ฒ ์ด์ค ๋ด๋ถ์ ์๋ ๋ฐฉ์์ ์ ํ์๊ฐ ์์ผ๋ฉฐ ๋ฐ์ดํฐ๋ฒ ์ด์ค ๊ฐ๋ฐ์ ๋ํ ๊ท์น ๋ง ์์ผ๋ฉด๋ฉ๋๋ค. ๊ทธ๋ ๋ค์๊ณผ ๊ฐ์ ๊ฒ์ ์๊ณ ์์ต๋๋ค. ์ธ๋ฑ์ฑํด์ผ ํ ๊ฒ, โฆ ๋ฐ์ดํฐ์์ ์ค๋ณต์ฑ์ ๋ง๋๋ ๊ฒ์ด ๋ ๋์ ๊ณณ, ๊ทธ๋ ์ง ์์ ๊ณณ โฆ
- ๊ฒ์ ๋ง๋ค๊ธฐ-๊ทธ๋ ์ผ๋ถ ๊ฒ์ ์์ง์ ์๋ ๋ฐฉ์์ ์ฐ๊ตฌํ๊ณ ํจ๋ฌ๋ค์์ ๋ฐ๋ฅด๊ธฐ ๋งํ๋ฉด๋ฉ๋๋ค. ๊ฒ์๊ณผ ์ปดํจํฐ ๊ทธ๋ํฝ์ ๋งค์ฐ ํฐ ๋ฐ์ดํฐ ๋ฌธ์ ์ ๋๋ค. ๋จ์ผ ์ฌ์ง / ํ๋ ์์ ๊ฒฝ์ฐ 1920 * 1080 * 32bit = cca 7.9MB๋ฅผ ๊ณ ๋ คํ์ญ์์ค โฆ @ 60 FPS ์ต์ 475MB / s์ ๋๋ค. ๋ถํ์ํ ์ ์ฒด ํ๋ฉด ๊ทธ๋ฆผ ์ฌ๋ณธ ํ๋๋ง ์ด๋น ์ฝ 500MB์ ๋ฉ๋ชจ๋ฆฌ ์ฒ๋ฆฌ๋์ด ๋ญ๋น๋๋ค๋ ์ ์ ๊ณ ๋ คํ์ญ์์ค. ๊ทธ๋ฌ๋ ๊ทธ๋ ์์ง ๋ง ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ ์ ๊ฒฝ ์ฐ์ง ์์๋๋ฉ๋๋ค!
๋ฉ์ฒญํ ํ๋ก๊ทธ๋๋จธ๋ํ์ง ๋ง์์ผํฉ๋๋ค :
- ์๋ฅผ ๋ค์ด, ์์ ๋ฐ์ดํฐ๋ ์ปดํ์ผ ์๊ฐ๋ณด๋ค ๋๋ฆฌ๊ธฐ ๋๋ฌธ์ ๊ฐ๋ฐ ์ค์ ๋ถ์ ์ ํ ์๋ฃจ์ ์ ๋์ ๋๋ ์ํฅ์ ๋ฏธ์น์ง ์์ต๋๋ค. ์๋ฅผ ๋ค์ด 0.5 ์ด๋ณด์ ์ธ ํ๋ก๊ทธ๋๋จธ ๊ด์ ์์ ๋ณผ ๋ ํ๋์ ๊ฐ๋จํ ํ๋ก๊ทธ๋จ์ ๋ํด sec๋์ด ํ๋ก๊ทธ๋จ์ ์ด๋น 20 ํ ์คํํ๋ ์๋ฒ ์๋ฒ๋ฅผ ๊ณ ๋ คํ์ญ์์ค. ๊ทธ ๋ถํ๋ฅผ ๊ฒฌ๋ ์ ์์ผ๋ ค๋ฉด 10cores๊ฐ ํ์ํฉ๋๋ค!
- ์๋ฒ ๋๋ ์ฅ์น๋ฅผ์ํ ํ๋ก๊ทธ๋จ ๊ฐ๋ฐ ์๋ฒ ๋๋ ์ฅ์น๋ ์์ ๋ฐ์ดํฐ๋ก ์๋ํ์ง๋ง ์ค๋ณต ์์ ์ผ๋ก ์ธํด ๋ถํ์ํ ์ ๋ ฅ ์๋น๊ฐ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ ๊ฐ๋ฅํ ํ ํจ์จ์ ์ด์ด์ผํฉ๋๋ค.
๋ฐ๋ผ์ ๊ธฐ์ ์ ์ฌ์ฉํ๊ณ ์ถ์ ๋ noobish ํ๋ก๊ทธ๋๋จธ๋ ๊ด์ฐฎ์ต๋๋ค. ๋ฐ๋ผ์ ์๋ก์ด ์๋ฃจ์ , ๋ง์ถคํ ๊ธฐ์ ๋ฑ์ ๊ฐ๋ฐํ ๋๋ ๋ฉ์ฒญํ ํ๋ก๊ทธ๋๋จธ๋ฅผ ๊ณ ์ฉํ์ง ์๋ ๊ฒ์ด ์ข์ต๋๋ค.
๊ทธ๋ฌ๋ ํ์ฌ๊ฐ ์๋ก์ด ๊ธฐ์ ์ ๊ฐ๋ฐํ์ง ์์ผ๋ฉด ์ด๋ฏธ ๋ง๋ค์ด์ง ๊ธฐ์ ๋ง ์ฌ์ฉํฉ๋๋ค. ์๋ จ๋๊ณ ์ฌ๋ฅ์๋ ํ๋ก๊ทธ๋๋จธ๋ฅผ ๊ณ ์ฉํ๋ ๊ฒ์ ์ฌ๋ฅ์ ๋ญ๋น ์ผ ๊ฒ์ ๋๋ค. ์๋ก์ด ๊ธฐ์ ์ ์ฌ์ฉํ๊ณ ์ถ์ง ์๊ณ ์ด๋ฏธ ๋ง๋ค์ด์ง ํ๋ ์ ์ํฌ๋ฅผ ์ฌ์ฉํ์ฌ ๊ณ ๊ฐ ์์ด๋์ด๋ฅผ ๋์์ธ๊ณผ ํ๋ก๊ทธ๋จ์ ๋ฃ๋ ๊ฒ์ด ์ข์ผ๋ฉด ์๊ฐ์ ๋ญ๋นํ๊ณ ํ์์๋ ๊ฒ์ ๋ฐฐ์ฐ๋ ๊ฒ์ ์๊ฐ ๋ญ๋น์ ๋๋ค. ๊ทธ๊ฒ์ด ์ทจ๋ฏธ์ด๊ณ ๋ ผ๋ฆฌ์ ์ธ ๋์ ์ ์ข์ํ๋ค๋ฉด.
๋ต๋ณ
๋๋ ์ฌ๊ธฐ์ ๋ต์ ์ฐ๋ ๊ฒ์ ๋ค์ ์ฃผ์ ํ์ง๋ง ์ฌ๋ฌ ๋ค๋ฅธ ์ฌ๋๋ค์ ๋ํ nitpicking์ ๋ฐ๊ฒฌํ๊ธฐ ๋๋ฌธ์ (๋ด ์๊ฒฌ ์ค ์ผ๋ถ๋ ์ฑํ ์ผ๋ก ์ด๋ํ์ต๋๋ค), ์ฌ๊ธฐ ๋ด๊ฐ ์ด๋ป๊ฒ ๋ณด๋์ง์ ๋๋ค โฆ
์ปดํจํ ์๋ ๋ง์ ๊ฒ๋ค์ ๋ํ ์์ค์ ์ง์์ด ์์ต๋๋ค (์ด ์ฉ์ด๋ก ๋๋ ์ปดํจํฐ ๊ณผํ๊ณผ ์ ๋ณด ๊ธฐ์ ์ ํตํฉ์ ์๋ฏธํฉ๋๋ค). ๊ณ์ฐ ๋ณต์ก๋๋ ๋ถ๋ช ํ ๊ด๋ ํ ๋ถ์ผ์ด๋ฉฐ (OptP๊ฐ ๋ฌด์์ธ์ง ์๋น ๋ณด์ธ-๋น๋ ์ ์ ๋ฆฌ๊ฐ ๋งํ๋๊ฐ?) ๊น์ด๋ ์ธ์ ํฉ๋๋ค. CS ํ์๋ฅผ ๊ฐ์ง ๋๋ถ๋ถ์ ์ฌ๋๋ค์ ์ฐ๊ตฌ์ ์ฐธ์ฌํ๋ ์ ๋ฌธ๊ฐ์ ์ฆ๊ฑฐ๋ฅผ ๋ง๋ค ์ ์์ต๋๋ค ๊ณ์ฐ ๋ณต์ก์ฑ์ ๊ฐํ๋ฌผ.
๊ทธ๋ฌํ ๋ฌธ์ ์ ํ์ํ ์ง์๊ณผ ๊ธฐ์ / ๋ฅ๋ ฅ์ ์์ค์ ์์ ์ด ๋ฌด์์ ํ๋๊ฐ์ ๋ฌ๋ ค ์์ต๋๋ค. ์์ ํ ๋จ์๊ฐ์๋ O (
์2) ์ ๋ ฌ์ ๋๋๋ก ๋๋ฆฐ ํ๋ก๊ทธ๋จ์ ์ฃผ์ ์์ธ์ด๋ผ๊ณ ๋งํ์ง๋ง [์ธ์ฉ ํ์] 2003 SIGCSE ๋ ผ๋ฌธ์ ๋ฐ๋ฅด๋ฉด โ์ฝ์ ์ ๋ ฌ์ ํ์ค Java ๋ฐ C ++ ๋ผ์ด๋ธ๋ฌ๋ฆฌ์์ ์์ (ํ์) ๋ฐฐ์ด์ ์ ๋ ฌํ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค.โ ๋ฐ๋๋ก, ์ ๊ทผ ์ ์๋ฏธ๊ฐ ๋ฌด์์ธ์ง ์ดํดํ์ง ๋ชปํ๋ ์ฌ๋ (์ปดํจํ ๋ณต์ก๋๋ ๊ทธ๋ฌํ ์ฒ๋ ์)์ด ์กฐ๊ธฐ์ ์ต์ ํ ๋๋ ๊ฒ์ด ๋๋๋ก ํ๋ก๊ทธ๋๋ฐ ์ค๋ฌด์์ ๋ฌธ์ ๊ฐ๋ฉ๋๋ค. ๊ทธ๋ฌ๋ ๊ณ์ฐ ๋ณต์ก์ฑ์ด ์ค์ํ ์์ ์ ์๋ ๊ฒ์ ์ ์ด๋ ํ๋ถ ์์ค์์ ์ด์ ๋ํ ํํธ๊ฐ ํ์ํ ์ด์ ์ ๋๋ค.
C์์ ์ฑ๋ฅ์ ๋ฏผ๊ฐํ ์ฝ๋๋ฅผ ๊ตฌํํ๊ณ ์ฑ๋ฅ์ ์ํฅ์ ๋ฏธ์น์ง ์๋ ๋ค์ ์ผ๋ฐ์ ์ธ ๊ดํ (์๋ฐ ์ธ๊ณ ์ธ๋ถ)๊ณผ ๊ณ์ฐ ๋ณต์ก์ฑ ๊ฐ๋ ์ ์ ์ฉํ๋ ์์ ๊ณผ ์์ ํ๊ฒ ๋ฌด์ํ ์์๋ ์์ ์ ์๊ณ ์๋ ์ํฉ์ ์์งํ ๋น๊ตํฉ๋๋ค. ํ์ด์ฌ ๋ฑ์ ๊ฒ๋ค. (์ ์ณ๋๊ณ , ์ด๊ฒ์ Julia ํ ํฌ์์ โํ์ค ํํโ ์ด๋ผ๊ณ ๋ถ๋ ์ต๋๋ค .) ์ฑ๋ฅ์ ๋ํด ์๊ฐํ ํ์๊ฐ ์์ ๋ ์๋ฉด ํ๋ก๊ทธ๋๋ฐ ์๊ฐ์ ์ ์ฝ ํ ์ ์์ต๋๋ค. ์ด๋ ์๋นํ ๊ท์คํ ์ํ์ด๊ธฐ๋ํฉ๋๋ค.
๋ ํ๋์ ์์ ์ ๊ณ์ฐ์ ๋ณต์ก์ฑ์ ์๋ฉด ํ๋ก๊ทธ๋จ ์ต์ ํ์ ์๋์ผ๋ก ๋์์ด๋์ง ์๋๋ค๋ ๊ฒ์ ๋๋ค. ์บ์ ์ง์ญ์ฑ, [๋๋ก๋] ํ์ดํ ๋ผ์ด๋, ์ค๋๋ ์ ๋ณ๋ ฌ / ๋ฉํฐ ์ฝ์ด ํ๋ก๊ทธ๋๋ฐ๊ณผ ๊ฐ์ ๋ ๋ง์ ์ํคํ ์ฒ ๊ด๋ จ ์ฌํญ์ ์ดํดํด์ผํฉ๋๋ค. ํ์๋ ์์ฒด ๋ณต์ก์ฑ ์ด๋ก ๊ณผ ์ค์ ๊ณ ๋ ค ์ฌํญ์ ๋ชจ๋ ๊ฐ์ง๊ณ ์์ต๋๋ค. A๋ก๋ถํฐ ํ์์ ๋ง 2013 SOSP ์ฉ์ง ๋ชจ๋ ์ ๊ธ ๋ฐฉ์์ โ์ฐ๋ฆฌ๋ ์ง์์ ์ผ๋ก ๋ชจ๋ ๋์ ์ํคํ ์ฒ ๋๋ ์ํฌ๋ก๋์, ๋ค๋ฅธ ํ๋๋ฅผ ๋ฅ๊ฐํ๋ ์ฑ๋ฅ์ ๊ณ ๋ ค ์ํ ๊ฐ ์ ๊ธ ๋ฐฉ์์ ๋ช ์ฑ. ์์์ 15 ๋ถ์๋ค. ์๋ฐํ ๋งํ๋ฉด, ์ต์ ํ๋์ ์ถ๊ตฌํ๋ ํ๋์จ์ด ํ๋ซํผ๊ณผ ์์ ์์ ๋์ ๋ฐ๋ผ ์ ๊ธ ์๊ณ ๋ฆฌ์ฆ์ ์ ํํด์ผํฉ๋๋ค. โ