์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
- ์ค์ฌ์นด
- ํ์ด๋ค์ผ ๋งฅ์ฃผ ๋ฐ๋ฌผ๊ด
- C++
- ์คํ๋ฒ ์ค
- ๋ฃจ๋ธ๋ฅด ๋ฐ๋ฌผ๊ด
- ๋์ ๋ฉ๋ชจ๋ฆฌ ํ ๋น
- Windows
- ์ฌํ
- ๊ตญ๋ฆฝ ๋ ์ผ ๋ฐ๋ฌผ๊ด
- ๋ฆฌ๋ฒ ํฌ๋ฃจ์ฆ
- Qt
- ๊ฐ์ฌ์ด ๊ณตํญ
- ์ ๋ฝ
- ๋คํ์ฐ ์์ฉ์
- ํ๋ฆฌ
- ์์คํ ๋ฅด๋ด ๊ตญ๋ฆฝ ๋ฏธ์ ๊ด
- ํ๋ก์ฐ๋ฉํฐ
- ๋ฎํจ
- ๋งค์ค์ปคํผ
- ๋ํค๋ณด๋ฆฌ
- ์ฌ๋ฅํฝ ํ๋ฅดํฌ
- ๋น๋์คํธ
- ์๋ฉ๋ฆฌ์นด๋ ธ
- ์ด์ฝ ๋ฐ๋๋ ์ฝ์ฝ์
- ๋ฒ ๋ก ๋นต
- ๋ง์๊ทธ๋ ์ด
- ์์ด์ค ์๋ฉ๋ฆฌ์นด๋ ธ
- ํฌ๋ฅด์ ๋ฐ๋ฌผ๊ด
- ๋ ์ผ
- this call
- Today
- Total
๊ตฌ๋ฆ
[ํ]2์ฐจ์ ๋ฐฐ์ด์ ํ ๋น ๋ณธ๋ฌธ
c++ ์์ 2์ฐจ์ ๋ฐฐ์ด์ ํ ๋นํ๋ ๋ฐฉ๋ฒ์ ์๋์ ๊ฐ์ต๋๋ค.
100*100 ์ int ํ ๋ฐฐ์ด์ด stack ์์ญ์ ์กํ๊ฒ ๋ฉ๋๋ค.
stack ์ ํฌ๊ธฐ(๋ณดํต 1~8MB ์ ๋) ๊ฐ ๋์ด๊ฐ๋ ๋ฐฐ์ด์ ์ก์ผ๋ ค๋ฉด, data ์์ญ(์ ์ญ ๋ณ์) ํน์ heap ์์ญ(๋์ ํ ๋น) ์ ์ด์ฉํ์ฌ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํด์ผ ํฉ๋๋ค.
data ์์ญ์ stack ์์ญ์์ ์ํ๋ ๋ฐฉ๋ฒ์ด ๊ฐ์ผ๋ฏ๋ก ์ฐ๋ฆฌ๋ heap ์ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ก๋ ๊ฒ์ ๋ํด ์์๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
int[3000][2000] ๋ฐฐ์ด์ stack ์์ญ์ ์กํ์ง ์์ผ๋ฏ๋ก, ์๋์ ๊ฐ์ด ๋์ ํ ๋น์ ํตํด run time ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋น๋ฐ์ ์ฌ์ฉํฉ๋๋ค.
๋จผ์ arr ์ด์ค ํฌ์ธํฐ ๋ณ์์ ๋ฐฐ์ด์ ๋์ด ๋งํผ(์ฌ๊ธฐ์๋ 3000*2000์ฌ๊ฐํ ๋ฐฐ์ด) ์ ํ ๋นํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ 3000๋งํผ ๋ฃจํ๋ฅผ ๋๋ฉฐ arr[n] ์ ๋ฐฐ์ด์ ๋๋น ๋งํผ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํฉ๋๋ค.
๋ชจ๋ ์ฌ์ฉํ ๋ค์์๋ ํ ๋นํ ๊ฒ๊ณผ ๋ฐ๋ ์์๋ก ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํด์ ํด์ค๋๋ค.
์ด๋ ๊ฒ 2์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ค๊ฒ ๋๋ฉด ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์ฐ์ฐ์ ๋์ด+1 ๋ฒ ๋งํผ ํด์ฃผ์ด์ผ ํฉ๋๋ค.
new ์ฐ์ฐ ํน์ malloc() ๋ฑ ๊ณผ ๊ฐ์ heap ์์ญ ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์์ฒญ์ ํ ๋นํฌ๊ธฐ๋ฅผ k ๋ผ ํ ๋ O(k) ๋งํผ์ ๋น์ฉ์ด ๋ค์ง๋ง ํ ๋นํฌ๊ธฐ-์๊ฐ ๊ทธ๋ํ์์ ๊ธฐ์ธ๊ธฐ๊ฐ 1๋ณด๋ค ์์ ํํ๋ก ๋์ต๋๋ค.
(์ค์ง์ ์ผ๋ก ๋ง์ด ์ฌ์ฉ ๋ ์์ญMB ์ ๋ ๊น์ง์ ํ ๋น ์๊ฐ์์๋ ์ ์๋ฏธํ ๋ฐ์ดํฐ๋ฅผ ๋ฝ์๋ด๊ธฐ๊ฐ ์ด๋ ค์ ์ต๋๋ค.)
๋ฐ๋ผ์ ์์๊ฐ์ด ๋์ด๋งํผ ๋์ ํ ๋น์ ํ๊ฒ๋๋ฉด, O(n*k) ๋งํผ์ ๋น์ฉ์ด ๋ค๊ฒ ๋ฉ๋๋ค. ๋ฌผ๋ก ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ฐํํ ๋์๋ O(n*k) ์ ๋น์ฉ์ด ๋ญ๋๋ค.
๋ฐ๋ผ์ ๋ฐฐ์ด์ ๋์ ํ ๋น ํ ๋์๋ ์์๊ฐ์ ๋ฐฉ๋ฒ์ด ์๋ ์๋ ์ฝ๋์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ํ ๋น์ ํ์ฌ์ผ ํฉ๋๋ค.
์ฒ์ ํฌ์ธํฐ ๋ฐฐ์ด์ ๋์ด ๋งํผ ํ ๋นํ๋๊ฒ์ ๊ธฐ์กด์ ์ฝ๋์ ๊ฐ์ต๋๋ค.
๋ค์์ผ๋ก 2์ฐจ์ ํฌ๊ธฐ๋ฅผ ํ๋ฒ์ 1์ฐจ์ ๋ฐฐ์ด์ ํ ๋นํฉ๋๋ค.
๋ง์ง๋ง์ผ๋ก ํฌ์ธํฐ ๋ฐฐ์ด์ ๊ฐ ์์์ 2์ฐจ์ ํฌ๊ธฐ๋ก ํ ๋นํ 1์ฐจ์ ๋ฐฐ์ด์ ๋ฐฐ์ด์ ๋๋น ๋งํผ ๋์์ ์ฐ๊ฒฐ์์ผ ์ฃผ๋ฉด, stack ์์ญ์ ์ ์ธํ ๋ฐฐ์ด๊ณผ ์์ ํ ๋์ผํ ๋ฉ๋ชจ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง 2์ฐจ์ ๋ฐฐ์ด์ด ์์ฑ ๋ฉ๋๋ค.
๋จ ๋๋ฒ๋ง์ new ์ฐ์ฐ ํธ์ถ๋ก 2์ฐจ์ ๋ฐฐ์ด์ด ์์ฑ๋์์ต๋๋ค.
๋์ด ๋งํผ์ ๋ฃจํ๋ฅผ ๋์ง๋ง, ๋์ ์ฐ์ฐ๊ณผ ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์ฐ์ฐ์ ๋น๊ตํด ๋ณธ๋ค๋ฉด ๋์ ์ฐ์ฐ์ ๊ฑฐ์ ์๋์๊ฐ์ด๋ผ๊ณ ํ ์ ์์ต๋๋ค.
์์ ์ฝ๋์์ size ๋ฅผ 1000, count ๋ฅผ 1000 ์ผ๋ก ๋๊ณ ์คํํ๊ฒ ๋๋ฉด,
๊ฒฐ๊ณผ์ ์ผ๋ก ๊ฐ์ ํฌ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋น ํ์๋๋ฐ, ๋๋ ์๊ฐ์ด 100๋ฐฐ ์ด์ ์ฐจ์ด๊ฐ ๋๋ ๊ฒ ์ ๋ณผ ์ ์์ต๋๋ค.
(๋ฌผ๋ก , ์ฌ์ฉ์์ ํ๊ฒฝ์ ๋ฐ๋ผ ์ฐจ์ด๊ฐ ์๊ฒ ์ง๋ง, ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์ฐ์ฐ์ด ์ค๋ฒํค๋๊ฐ ํฌ๋ค๋ ๊ฒ ์ ๋๋ค.)
(g++ ์์ ํ ์คํธ ํด๋ณด๋ ์ฐจ์ด๊ฐ ๋ง์ด ๋๋ค์. ์ญ์ g++ ์ ์ต์ ํ๋ ์์ฒญ๋๊ฑฐ ๊ฐ์ต๋๋ค.)
์ฌ๊ธฐ์ ํฌ์ธํฐ ๋ฐฐ์ด์ด ์๋๋ผ๋ 1์ฐจ์ ๋ฐฐ์ด์ 2์ฐจ์์ฒ๋ผ ์ฌ์ฉํ๋๊ฒ์ด๊ธฐ์, ์ธ๋ฑ์ค๋ฅผ ์ฐ์ฐํ์ฌ ์ ๊ทผ ํ ์ ์์ต๋๋ค.
๊ฐ์ ์๋ฆฌ๋ก n์ฐจ ๋ฐฐ์ด์ new ์ฐ์ฐ n๋ฒ ํธ์ถ ํน์ new ์ฐ์ฐ ๋จ ํ๋ฒ์ ํธ์ถ ๋ง์ผ๋ก ๋ง๋ค ์ ์์ต๋๋ค.
1. ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์ฐ์ฐ์ ์ค๋ฒํค๋๊ฐ ๊ต์ฅํ ํฌ๋ค.
ํ ๋นํ ๋ฉ๋ชจ๋ฆฌ๋ ํด์ ํ์ง ๋ง๊ณ , ์ฌ์ฌ์ฉ ํ์.
ํ ๋น ์ฐ์ฐ์๋ฅผ ์ต์ํ์ผ๋ก ํ๋ ์ฝ๋ฉ์ ํ์.