์๊ฐ ๋ณต์ก๋๋?
- ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ด ๋ ๋์์ง ๋น๊ตํ ์ ์๋ ๊ธฐ์ค์ด ํ์ํจ
- ํ๋ก๊ทธ๋จ์ด ๋์ํ๊ณ ๊ฒฐ๊ณผ๋ฅผ ๋ง๋ค์ด๋ด๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์ ๋๋ฅผ ๋ณต์ก๋๋ผ๊ณ ํจ
- ์๊ฐ ๋ณต์ก๋: ์ผ๋ง๋ ์ค๋ ๊ฑธ๋ฆฌ๋์ง
- ๊ณต๊ฐ ๋ณต์ก๋: ์ผ๋ง๋ ๋ง์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋์ง
- ์ฝ๋ฉ ํ
์คํธ์์๋ ๋ ๋ณต์ก๋์ ๋ํ ์กฐ๊ฑด์ด ํจ๊ป ์ ์๋จ → ๋ช ์ด/๋ช MB ์ด๋ด
- ๋ฌธ์ ๋ ์ธ์ด๋ง๋ค ์ฃผ์ด์ง ์๊ฐ์ด ๋ค๋ฅด์ง๋ง ํ๋ก๊ทธ๋๋จธ์ค๋ ํน๋ณํ ์ธ๊ธํ์ง ์์ผ๋ฉด ์ ํ ์๊ฐ์ด 10์ด์
- 10์ด??? … ์ด๋ฅผ ์ดํดํ๋ ค๋ฉด ๋จผ์ ์ฐ๋ฆฌ๊ฐ ์ง ์ฝ๋๋ฅผ ์ด๋ป๊ฒ ์๊ฐ์ผ๋ก ๋ํ๋ผ ์ ์๋์ง ์ ํ์๊ฐ ์์
๋น ์ค(Big-O) ํ๊ธฐ๋ฒ
- SW๋ HW์ ๋ณ์๊ฐ ๋ง์ ๋๊ฐ์ ์ฝ๋๋ผ๋ ํ๊ฒฝ์ ๋ฐ๋ผ ์คํ ์๊ฐ์ด ์กฐ๊ธ์ฉ ๋ค๋ฆ
- ์ด ๋๋ฌธ์ ์๊ฐ์ ์ ํํ ์์น๋ก ๋ํ๋ด๊ธด ์ด๋ ต์ง๋ง, ๋ฌธ๋ฒ์ด๋ ๊ตฌ์ฑ์์ ๋ฐํํ๋ ๋น์ฉ์ ์์นํํด ๋ฌธ์ ๋ฅผ ํธ๋๋ฐ ํ์ํ ์ด ์ฐ์ฐ์ ์๋ฅผ ์ํ์ ์ผ๋ก ํ๊ธฐํ ์ ์์ ⇒ ์ ๊ทผ ํ๊ธฐ๋ฒ
- 3๊ฐ์ง ํ๊ธฐ๋ฒ ์ค ๊ฐ์ฅ ํํ๊ฒ ์ฌ์ฉ. ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํ๋ ๋น ์ค(Big-O) ํ๊ธฐ๋ฒ์ ๋ํด ์์๋ณด์.
- ์ด ๋๋ฌธ์ ์๊ฐ์ ์ ํํ ์์น๋ก ๋ํ๋ด๊ธด ์ด๋ ต์ง๋ง, ๋ฌธ๋ฒ์ด๋ ๊ตฌ์ฑ์์ ๋ฐํํ๋ ๋น์ฉ์ ์์นํํด ๋ฌธ์ ๋ฅผ ํธ๋๋ฐ ํ์ํ ์ด ์ฐ์ฐ์ ์๋ฅผ ์ํ์ ์ผ๋ก ํ๊ธฐํ ์ ์์ ⇒ ์ ๊ทผ ํ๊ธฐ๋ฒ
- ๋น
์ค ํ๊ธฐ๋ฒ: ์๊ณ ๋ฆฌ์ฆ์ด ํด๋น ์ฐจ์์ด๊ฑฐ๋, ๊ทธ๋ณด๋ค ๋ฎ์ ์ฐจ์์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ ์ ๊ทผ์ ์ํ ํ๊ธฐ ๋ฐฉ๋ฒ์ ์๋ฏธํจ
- ์ฝ๊ฒ ‘์ต์ ์ ๊ฒฝ์ฐ ์ด ์ ๋์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค’๋ก ์ดํดํ๋ฉด ๋จ
- n² + 2n + 1์ ์๊ฐ ๋ณต์ก๋: O(n²)
- 99n์ ์๊ฐ ๋ณต์ก๋: O(n)
- ์ฐ์ฐ ํ์๊ฐ ์ต๊ณ ์ฐจํญ์ ๋น๋กํ๋ ํ๋ฆ์ ๋ณด์ธ๋ค๋ฉด ๋ถ๊ฐ์ ์ธ ์ฐ์ฐ์ ์ ๊ฒฝ ์ธ ํ์ ์์(๋ง์ ๋ฐ์ดํฐ๋ฅผ ์
๋ ฅํ๋ฉด ์ฐ์ฐํ์๊ฐ ์ฐจ์ด๋๊ธฐ ๋๋ฌธ์ ์์ ์๋ ์๋์ ์ผ๋ก ๋ฌด์ํ ์ ์์)
- 4n²๊ณผ 4n์ ๋น๊ต: 10๋ง๊ฐ ์ ๋ ฅ → ์ฐ์ฐ ํ์: 400์ต, 40๋ง ์ ๋๋ก ์ฐจ์ด ๋จ
- ์ฐ์ฐ ํ์๊ฐ ์ต๊ณ ์ฐจํญ์ ๋น๋กํ๋ ํ๋ฆ์ ๋ณด์ธ๋ค๋ฉด ๋ถ๊ฐ์ ์ธ ์ฐ์ฐ์ ์ ๊ฒฝ ์ธ ํ์ ์์(๋ง์ ๋ฐ์ดํฐ๋ฅผ ์
๋ ฅํ๋ฉด ์ฐ์ฐํ์๊ฐ ์ฐจ์ด๋๊ธฐ ๋๋ฌธ์ ์์ ์๋ ์๋์ ์ผ๋ก ๋ฌด์ํ ์ ์์)
์๊ฐ ๋ณต์ก๋ ๊ทธ๋ํ
- ํ: ์ ๋ ฅ ๋ฐ์ดํฐ ์์ ๋ฐ๋ฅธ ์ฐ์ฐ ํ์
- 1, 2, 3, 4, 8, 16, 32, 64, 1000 .. : ์ ๋ ฅ ๋ฐ์ดํฐ ์ n
- ์ฐ์ฐํ์๊ฐ ํ ์๋๋ก ํฅํ ์๋ก ๊ธฐํ๊ธ์์ ์ผ๋ก ๋์ด๋จ
- ๋ง์ฝ, ๋ฌธ์ ์ ์ฃผ์ด์ง ๋ฐ์ดํฐ ์๊ฐ 10๋ง ๊ฐ๊ณ , ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๊ฐ O(n²)์ด๋ผ๋ฉด 10๋ง x 10๋ง์ผ๋ก 100์ต ๋ฒ ์ฐ์ฐ์ ์ํํ๊ฒ ๋จ
- ์ปดํจํฐ๋ ๋ณดํต 1์ด์ 1์ต๋ฒ ์ฐ์ฐํ๋ฏ๋ก ์ด ํ๋ก๊ทธ๋จ์ ๋์ํ๋๋ฐ 100์ด๊ฐ ๊ฑธ๋ฆฐ๋ค๋ ๊ฒฐ๋ก ์ ๋ผ ์ ์์
- ๋ฌธ์ ์์ ์ฃผ์ด์ง ์
๋ ฅ๊ฐ์ ์ต๋ ํฌ๊ธฐ๊ฐ 10๋ง ๊ฐ๋ผ๋ฉด ์๊ฐ ๋ณต์ก๋๊ฐ O(nlogn) ์ ๋์ธ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ด์ผ ํ๋ค๋ ๊ฒ์ ์์์ผ ํจ → O(n²) ์๊ฐ ๋ณต์ก๋์ธ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ๋ฉด ๋์ ํ๋ฅ ๋ก ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํด ํ
์คํธ์ ์คํจํจ
-
๋๋ณด๊ธฐ๐ค ์??
๐ก ์ ๋ ฅ ํฌ๊ธฐ๊ฐ n=10โต์ธ ์ํฉ์์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋น๊ตํด๋ณด์
- O(nlogn) ์๊ณ ๋ฆฌ์ฆ:
- logn์ ๋๋ต logโ(10โต) ≈ 17 ์ ๋
- ๋ฐ๋ผ์ O(nlogn)์ ๊ฒฝ์ฐ ์คํ ์๊ฐ์ด 10โต × 17 ≈ 1,700,000 ์ ๋์ ์ฐ์ฐ ํ์๋ก ์ถ์ ๋จ
- O(n²) ์๊ณ ๋ฆฌ์ฆ :
- ๋ง์ฝ O(n²) ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ค๋ฉด, ์คํ ์๊ฐ์ด 10โต × 10โต = 10¹โฐ = 10,000,000,000 (100์ต) ๋ฒ์ ์ฐ์ฐ์ ์๊ตฌํจ
- ์ด๋ ์ค์ ๋ก๋ ๋งค์ฐ ๋ง์ ์๊ฐ์ด ๊ฑธ๋ ค ์ฑ๋ฅ์ ํฐ ์ํฅ์ ๋ฏธ์น๊ฒ๋จ
- ์๊ฐ ์ ํ
- ๋๋ถ๋ถ์ ์ปดํจํฐ๋ ์ด๋น ์ฝ 1์ต ๋ฒ ์ ๋์ ์ฐ์ฐ์ ์ฒ๋ฆฌํ ์ ์๋ค๊ณ ๊ฐ์
- O(nlogn) ์๊ณ ๋ฆฌ์ฆ์ 1,700,000๋ฒ์ ์ฐ์ฐ์ผ๋ก, 1์ด ์์ ์ถฉ๋ถํ ์ฒ๋ฆฌํ ์ ์์
- ํ์ง๋ง O(n²) ์๊ณ ๋ฆฌ์ฆ์ 10¹โฐ๋ฒ์ ์ฐ์ฐ์ด ํ์ํ์ฌ, 100์ด ์ด์ ๊ฑธ๋ฆด ์ ์์
- ๋๋ถ๋ถ์ ์ปดํจํฐ๋ ์ด๋น ์ฝ 1์ต ๋ฒ ์ ๋์ ์ฐ์ฐ์ ์ฒ๋ฆฌํ ์ ์๋ค๊ณ ๊ฐ์
- O(nlogn) ์๊ณ ๋ฆฌ์ฆ:
-
O(1) |
|
O(logn) |
|
O(n) |
|
O(nlogn) |
|
O(n²) |
|
O(2โฟ) ์ด์ |
|
์๊ฐ ๋ณต์ก๋ ์ ํ ์ ์ฐธ๊ณ ํ ๋งํ ์ฌํญ
- ์ต๋ ์๊ฐ์ด 1์ด์ผ ๋ ์
๋ ฅ ๋ฐ์ดํฐ ์์ ๋ฐ๋ฅธ ์๊ฐ ๋ณต์ก๋
- 1,000๊ฐ๋ผ๋ฉด → O(n²) ์ดํ
- 1000*1000=100๋ง
- 10,000๊ฐ๋ผ๋ฉด → O(n²) ๋ฏธ๋ง(์ต๋ํ ์ ๊ฒ ์ฌ์ฉํ๋ ๋ฐฉํฅ์ผ๋ก)
- 10000*10000=1์ต
- 100,000๊ฐ๋ผ๋ฉด → O(nlogn) ์ดํ
- logn์ ๋๋ต logโ(10โต)≈17 ์ ๋
- 100000*17=1700000=๋ฐฑ ์น ์ญ๋ง
O(n²)์ ์ฌ์ฉํ๊ฒ ๋๋ฉด, 10000000000์ผ๋ก ๋ฐฑ์ต..!
- 1,000,000๊ฐ๋ผ๋ฉด → O(nlogn) ๋ฏธ๋ง(๊ฐ๊ธ์ O(n) ์ ๋๋ก)
- logn์ ๋๋ต logโ(10โต)≈17 ์ ๋
- 1000000*17=17000000=์ฒ ์น ๋ฐฑ๋ง
- ๊ทธ ์ด์์ด๋ผ๋ฉด → ์ ๋ ฅ ๋ฐ์ดํฐ ์๊ฐ ๋ฐฑ๋ง ๊ฐ ์ด์์ด๋ผ๋ฉด ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ ์ฌํ ์ดํด๋ด๋ผ. ํน์ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋๋ก ์๊ตฌํ ๊ฐ๋ฅ์ฑ์ด ํผ
- 1,000๊ฐ๋ผ๋ฉด → O(n²) ์ดํ
- ์์ฃผ ์ฌ์ฉํ๋ ์๋ฃ ๊ตฌ์กฐ์ ์๊ฐ ๋ณต์ก๋
์๊ฐ ๋ณต์ก๋ ๊ณ์ฐํ๊ธฐ
์ด๋ฆผ์ง์ํด๋ณด๊ธฐ
- ํด๋น ๊ตฌ๊ตฌ๋จ๋ง ์ฐ์ฐํ๋ ๊ฒฝ์ฐ์, ํด๋น ๊ตฌ๊ตฌ๋จ๋ถํฐ 9๋จ๊น์ง ์ ๋ถ ์ฐ์ฐํ๋ ๊ฒฝ์ฐ
- for๋ฌธ์ 1๋ฒ ์ผ์ผ๋ O(n)์ด๊ณ for๋ฌธ์ 2๋ฒ ์ผ์ผ๋ O(n²)์ผ๊น? → ์๋
- ์ฃผ์ด์ง ์ซ์์ 9๋จ๊น์ง๋ง ์ถ๋ ฅํ๋ ํจ์์ ๊ฒฝ์ฐ 1๋ฒ ์
๋ ฅํ๊ณ , 9๋ฒ ์ฐ์ฐ์ ์ํํจ
- ์ ๋ ฅ์ด 10๋ง ๊ฐ๋ผ๋ฉด 10๋ง ๊ฐ × 9์ด๊ณ , ์ด๋ ๊ณง 9n์ด๋ฏ๋ก O(n)์ด๋ผ๊ณ ๋ํ๋ผ ์ ์์
- ์ฃผ์ด์ง ์ซ์๋ถํฐ 9๋จ๊น์ง ์ถ๋ ฅํ๋ ํจ์์ ๊ฒฝ์ฐ 1~9 ์ค ํ๋์ ๊ฐ๋ง ํ์ํ๋ฏ๋ก, ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ์์ ํ์ฌ 1์ด ์ ๋ ฅ์ด๋ผ๋ฉด 10๋ง ๊ฐ × 9(1๋จ๋ถํฐ 9๋จ) × 9๊ฐ ๋์ด 81n์ด ๋๋ฏ๋ก ์ญ์ O(n)์ด๋ผ ํ ์ ์์
- ๊ธฐ๋ณธ์ ์ผ๋ก ๊ตฌ๊ตฌ๋จ์ ๊ฒฝ์ฐ ํญ์ ๋์ผํ ์ฐ์ฐ๋์ ๊ฐ์ง๋ฏ๋ก ์
๋ ฅ ๊ฐ์์ ์ํฅ์ ๋ฐ๊ณ , ๋ฐ๋ผ์ O(n) ์๊ณ ๋ฆฌ์ฆ์ ์ค์ฐจ ๋ฒ์ ์ด๋ด๋ก ๊ท๊ฒฐ๋๋ค๋ ์ ์ ์ ์ ์์
- ๋ฐ๋ณต๋ฌธ์ด๋ ์ข ๋ณต์กํ ์ฐ์ฐ์ ํ๋๋ผ๋ ์ฃ๋ถ๋ฅด๊ฒ O(n²)์ด๋ผ ๋จ์ ์ง์ ํ์ ์์ → ๋น ์ค ํ๊ธฐ๋ฒ์ ์ฝ๋๊ฐ ์ผ๋ง๋ ๋ณต์กํ๊ฒ ๋์๊ฐ๋์ง์ ๋ํด ๋น ๋ฅด๊ฒ ๊ฐ์ ์ก๊ธฐ ์ํ ์ ๋ ์ฌ์ฉ๋๋ ๊ฒ์ด์ง, ์ ํํ ์ธก์ ์๊ฐ์ ์ํด ์ฌ์ฉํ๋ ํ๊ธฐ๋ฒ์ด ์๋
๋ด์ฅ ํจ์ ์๊ฐ ๋ณต์ก๋
๋ฆฌ์คํธ(list; [ ])
โป b-a๋ผ์ O(n) ‘๋ฏธ๋ง’์. ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ์์ ํ์ฌ O(n)์ผ๋ก ํ๊ธฐํจ
์งํฉ(set; { })
๋์ ๋๋ฆฌ(dictionary; { })
์๊ฐ ๋ณต์ก๋ ์ค์ด๊ธฐ
- ์ง๊ธ๊น์ง ๋ฐฐ์ด ์๊ฐ ๋ณต์ก๋ ์ค์ด๋ ๋ฐฉ๋ฒ
- ์ ๋ ฅ ๊ฐ์๋ฅผ ๋ณด๊ณ ๊ทธ์ ๋ง๋ ์ ์ ํ ์๊ณ ๋ฆฌ์ฆ์ ์ ํํ๊ธฐ
- ์๋ฃํ์ด๋ ์๋ฃ ๊ตฌ์กฐ๋ฅผ ์ ๊ทน์ ์ผ๋ก ์ฌ์ฉํ๊ธฐ
- ๋ฐ๋ณต๋ฌธ์ ์ค์ด๊ธฐ
readline(): ์ ๋ ฅ ์๋๋ฅผ ๋น ๋ฅด๊ฒ
- ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฒฝ์ฐ ์ ๋ ฅ๊ฐ์ ๋ชจ๋ ์ฃผ๊ณ , ์ํ๋ ๊ธฐ๋ฅ๋ง ๊ตฌํํ๋ฉด ๋๋ ํจ์ ํํ๋ก ์์ ์ฝ๋๊ฐ ์ฃผ์ด์ง์ง๋ง, ์ค์ ํ ์คํธ๋ฅผ ๋ณผ ๋๋ ์ ๋ ฅ ๊ฐ์ ๋ฐ๋ ์ฝ๋๋ ์ง์ ๊ตฌํํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ์์
- sys ๋ชจ๋์ readline()์ ํ์ฉ
- input() ํจ์๋ ๋ฐ์ดํฐ๊ฐ ๋ง์์๋ก ํจ์จ์ด ๋จ์ด์ง
import sys data = sys.stdin.readline()
๋ฆฌ์คํธ ๊ณฑ์ : ์ด๊ธฐํ์ ํ ๋น์ ๋น ๋ฅด๊ฒ
- ๊ธฐ๋ณธ์ ์ผ๋ก ๋ฐฐ์ด(๋ฆฌ์คํธ)์ ๋ค๋ฃฐ ๋ ๋์ ์ผ๋ก ๋ค๋ฃจ์ง๋ง, ๊ฐ๋ ๋ฏธ๋ฆฌ ํ ๋นํด ๋์ ๊ณ ์ ๋ฐฐ์ด์๋ค๊ฐ ๊ณ์ฐํด์ผ ํ๋ ๊ฒฝ์ฐ๊ฐ ์์
- ์ด๋ด ๋ ๋ฆฌ์คํธ์ ๊ณฑ์ ์ฐ์ฐ์ ํ์ฌ ์ด๊ธฐํ์ ํ ๋น์ ๋์์ ์งํํ๋๋ก ๋ง๋ค ์ ์์
data1 = [0 for _ in range(1000)] data2 = [0] * 1000
- data1์ ๊ฒฝ์ฐ for ๋ฌธ์ 1,000๋ฒ ๋ฐ๋ณตํ๋ฉด์ ๋ฆฌ์คํธ์ 0์ ์ง์ด๋ฃ๊ธฐ ๋๋ฌธ์ O(n)๋งํผ ์๋ชจ๋์ง๋ง, data2์ ๊ฒฝ์ฐ [0]์ 1,000๋ฒ ๋ฐ๋ณตํ๋ ๊ฒ์ด ์ ๋ถ์ด๋ฏ๋ก O(n) ์๊ฐ์ผ๋ก ๋์ผํ ์์ ์ ์ํํ ์ ์์
๋ฌธ์์ด ํฉ์น๊ธฐ: ‘ ’.join()์ ์ฐ๊ณ +๋ ์ฌ์ฉํ์ง ๋ง
- +๋ก ํฉ์น ๊ฒฝ์ฐ ๊ฐ๊ฐ์ ๋ฌธ์์ด์ ์๋ก์ด ๋ฉ๋ชจ๋ฆฌ์ ๋ณต์ฌํ์ฌ ์ ๋ฌธ์์ด์ ๋ง๋ค๊ธฐ ๋๋ฌธ์ ์ฌ์ค์ ์๊ฐ ๋ณต์ก๋๊ฐ O(n²) ์ ๋๊ฐ ๋จ
์กฐ๊ฑด๋ฌธ ์ฐ์ฐ ์ค์ด๊ธฐ: ์งง์ ๊ฒ๋ถํฐ ๋จผ์ ๊ณ์ฐํ์
- if ์กฐ๊ฑด๋ฌธ์์ ๋ค์ค ์กฐ๊ฑด์ ์ฌ์ฉํ๋ฉด ๋ ์กฐ๊ฑด ์ค ๋นจ๋ฆฌ ์คํ๋๋ ์ชฝ์ ์์ชฝ์ผ๋ก ๋ฐฐ์นํ๋ ๊ฒ์ด ์ ๋ฆฌํจ
- and ์ฐ์ฐ์ ํ ๋ ์์ ์ฐ์ฐ ๊ฒฐ๊ณผ๊ฐ False๋ผ๋ฉด ๋ค์ ์ฐ์ฐ์ ์คํํ์ง ์๊ณ ๋ฐ๋ก ๋์ด๊ฐ
- or ๋ํ ์์ ์ฐ์ฐ ๊ฒฐ๊ณผ๊ฐ True๋ผ๋ฉด ๋ค์ ์ฐ์ฐ์ ์คํํ์ง ์์
์ฌ๋ผ์ด์ฑ: ๋ถํ์ํ ์ฐ์ฐ์ ์ต์๋ก
- ๋ฆฌ์คํธ, ํํ, ์ด์์ด๊ณผ ๊ฐ์ ์๋ฃํ์ ๋ฒ์๋ฅผ ์ง์ ํด ์ผ๋ถ๋ถ๋ง ์ถ์ถํ๋ ๊ธฐ๋ฅ
- ex) a[start : end : step] ํ์์ผ๋ก ์ฌ์ฉํจ
- start: ์์ ์์น(์์ ํฌํจ), ์ซ์ ์๋ตํ๋ฉด ๊ฐ์ฅ ์ฒซ ๋ฒ์งธ๋ถํฐ๋ก ์ธ์
- end: ๋๋ผ ์์น(์์ ํฌํจx), ์ซ์ ์๋ตํ๋ฉด ๊ฐ์ฅ ๋ง์ง๋ง๊น์ง๋ก ์ธ์
- step: ๊ฐ๊ฒฉ(๊ธฐ๋ณธ์ 1), ์์๋ฅผ ๋ฃ๊ฒ ๋๋ฉด ๋งจ ๋์์๋ถํฐ ์ธ๋ฑ์ค๋ฅผ ํ์ํจ
- a[-1 : -3] : ๋งจ๋์์๋ถํฐ ๋งจ ๋์์ ๋ ๋ฒ์งธ ์์๊น์ง ๊ฐ์ ธ์ด
# ๋ฌธ์์ด ์ฌ๋ผ์ด์ฑ
print('Python is awesome'[3::2])
# 2์ฐจ์, 3์ฐจ์ ๋ฐฐ์ด ์ฌ๋ผ์ด์ฑ
data = [[(0, 1), (2, 3), (4, 5)], [(6, 7), (8, 9), (0, 1)]]
print(data[1:][0][::2])
- ์ด ์ธ์๋ for ๋ฌธ์ ์ฌ์ฉ ๊ฐ๋ฅ
ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ ํ์ฉํ๊ธฐ: ์๋์ ์์ ์ฑ ๋ชจ๋ ์ก๊ธฐ
- heapq
- ์ด์ง ํธ๋ฆฌ ๊ธฐ๋ฐ์ ์ต์ ํ ์๋ฃ ๊ตฌ์กฐ
- ํญ์ ์ ๋ ฌ๋ ์ํ๋ก ๊ฐ์ ์ถ๊ฐ/์ญ์ ๊ฐ ์ด๋ฃจ์ด์ง
- ์ฐ์ ์์ ํ๋ ์ต๋จ ๊ฑฐ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ ๋ ๋ง์ด ์ฌ์ฉ๋จ
- collections
- ์ฐ์๋๋ ์๋ฃ๋ฅผ ๊ฐ์ง๊ณ ์๋ ์๋ฃํ์์ ๋์ผํ ์์๊ฐ ๋ช ๊ฐ ์๋์ง ํ์ธ ๊ฐ๋ฅํ counter๊ฐ ์๊ธฐ ๋๋ฌธ์ ํด์ ๋ฌธ์ ๋ฅผ ํ ๋ ์ ์ฉํจ
- ์ถ๊ฐ๋ก ๋ฑ(dequeue) ์๋ฃ ๊ตฌ์กฐ๋ฅผ ๊ตฌํํ๋๋ฐ ์ฌ์ฉํ๋ deque๋ ์์
- itertools
- ๊ฒฝ์ฐ์ ์ ๋ฌธ์ ์ ์ฌ์ฉํ๋ฉฐ ์์ด, ์กฐํฉ, ์ค๋ณต์์ด, ์ค๋ณต์กฐํฉ ๋ฑ์ ์ฌ์ฉํจ
- math
- ๋ณต์กํ ์ํ ์ฐ์ฐ์ ๋์ ํ๋ ๋ผ์ด๋ธ๋ฌ๋ฆฌ
- ์ต๋๊ณต์ฝ์, ์ต์๊ณต๋ฐฐ์, ํฉํ ๋ฆฌ์ผ, ์ ๊ณฑ๊ทผ, ๋ก๊ทธ ๋ฑ์ ๊ณ์ฐํ๋ฉฐ, ํ์ด, ์์ฐ์์์ ๊ฐ์ ์์๋ ์กด์ฌํจ
- bisect
- ์ด์ง ํ์ ๊ธฐ๋ฅ์ ์ ๊ณตํจ
- ์ ๋ ฌ๋ ๋ฐ์ดํฐ๊ฐ ํ์ํ๋ฉฐ, ํน์ ๋ฒ์ ์์ ์์๊ฐ ์๋์ง ๊ฒ์ฌํ๊ฑฐ๋ ๋ช ๊ฐ๊ฐ ์กด์ฌํ๋์ง ํ์ธํ๋๋ฐ ์ ์ฉํจ
๋ฆฌ์คํธ ์ปดํ๋ฆฌํจ์ vs ์ ๋๋ ์ดํฐ: ํธ์์ ์ ํจ์จ์ ๋๊ฒฐ
- ๋ฆฌ์คํธ์ 1๋ถํฐ 10๊น์ง ๋ฐ์ดํฐ ๋ฃ๊ธฐ
- for ๋ฌธ
- data = [] for i in range(1, 11): data.append(i)
- ์ปดํ๋ฆฌํจ์ (comprehension) ์ฌ์ฉ → ์ฝ๋ ํ ์ค๋ก ์ค์ด๊ธฐ
- [i for i in range(1, 11)]
๐ก ๋ฆฌ์คํธ ์ปดํ๋ฆฌํจ์ ์ฌ์ฉํ๊ธฐ
- ์ ์ธ → ํ ๋น → ์ฌ๊ตฌ์ฑ ๊ณผ์ ์ ํ ์ค์ ๋ชจ๋ ๋๋ผ ์ ์์
- ์๊ฐ์ O(n)
- ์ฌ๋ฌ ์ค๋ก ๋ฐ๊ฟ ์จ๋ ์ฐจ์ด๊ฐ ๋์ง ์์์ ๊ฐํธํ๊ฒ ๋ฐ์ดํฐ๋ฅผ ์ค๋นํ ์ ์์
[(๋ณ์ ํํ์) for (์ฌ์ฉํ ๋ณ์) in (์ํ ๊ฐ๋ฅํ ์ฐ์์ ์ธ ๋ฐ์ดํฐ)]
# ์กฐ๊ฑด๋ฌธ ์ถ๊ฐ - ์ง์๋ง ๋ฝ๊ธฐ
[i for i in range(11) if i % 2 == 0]
# if๋ฌธ ์ค์ฒฉ (and๋ก ์ทจ๊ธ) - ์ง์์ 5์ ๋ฐฐ์ ๋์ ๋ง์กฑํ๋ ์ซ์ ๊ตฌํ๊ธฐ
[i for i in range(11) if i % 2 == 0 if i % 5 == 0]
- ๊ทธ๋ฌ๋ ์ปดํ๋ฆฌํจ์
์ ๋ฐ์ดํฐ๊ฐ 10๋ง ๊ฐ, 100๋ง ๊ฐ ์์ ๋ ์ด ๋ฐ์ดํฐ๋ฅผ ๋ชจ๋ ์์ฑํ๊ธฐ ๋๋ฌธ์ ํฌ๊ฒ ์ ๊ฒฝ ์ธ ํ์๊ฐ ์๋ค๊ณ ํ๋ ๊ณต๊ฐ ๋ณต์ก๋๋ฅผ ๊ณ ๋ คํ๊ฒ ํ๋ ์์ธ์ด ๋๊ธฐ๋ ํจ
- ํธ๋ฆฌํ ๊ธฐ๋ฅ์ ๋๋ถ๋ถ ๊ณต๊ฐ ๋ณต์ก๋๊ฐ ์ปค์ง๋ ๊ฒฝ์ฐ๊ฐ ๋ง์
๐ก ์ ๋๋ ์ดํฐ
- ์ฐ์ ๊ฐ๋ฅํ ์๋ฃํ์ ๋ฐํํ๋ ํจ์
- ์คํ ์ค yield๋ฅผ ๋ง๋๋ฉด ๊ฐ์ ๋ฐํํ๊ณ ๋ ์ด์ ์งํํ ์ ์๋ ์ํ๊ฐ ์๋๋ผ๋ฉด next()๊ฐ ํธ์ถ๋๊ธฐ ์ ๊น์ง ๋๊ธฐํจ
- ์ฆ, ํ ๋ฒ์ ๋ชจ๋ ์คํํ๊ณ ๊ทธ์ ๋ํ ๊ฒฐ๊ด๊ฐ์ ๋ฐํํ๋ ๊ฒ์ด ์๋๋ผ, ํจ์๊ฐ ์คํ๋์๋ค๊ฐ ๋ค์ next()๋ฅผ ๋๊ธฐํ๋ฉด์ ์คํ์ด ๋ฉ์ถค
- ์ฅ์ : ํจ์๊ฐ ์คํํ ๊ฒ์ด ๋งค์ฐ ๋ง์๋ ๋ฉ๋ชจ๋ฆฌ๋ ํญ์ ๊ณ ์ ๋ ๊ฐ์ ์ง๋
- ๋ง๋๋ ๋ฐฉ๋ฒ
- ํจ์ ์ ์ํ ๋ return ๋์ yield ์ฌ์ฉ
- ์ปดํ๋ฆฌํจ์ ๋ฌธ๊ตฌ๋ฅผ ์๊ดํธ๋ก ๊ฐ์ธ์ค
# 1๋ถํฐ 10๊น์ง ํ ๋ฒ์ ์งํํ์ง ์๊ณ , ์ง์ next()๋ฅผ ํธ์ถํด์ผ 1, 2, 3์ ๊ฐ์ด ๋ฐํ๋จ
# ์ด๋ ์ด์ ๊ฐ์ ๊ฐ์ง ์๊ณ , ํ์ํ๋ค๋ฉด ๋ฐ๋ก list() ๊ฐ์ ํจ์๋ฅผ ํตํด ์คํ๋๋ ๊ฐ์ ์ ์ฅํด์ผ ํจ
(i for i in range(11))
๋ฐ์ดํฐ ๋๋ ค์ฐ๊ธฐ: ์ค๋ณต ํผํ๊ธฐ
- ๋ถํ์ํ ์ฐ์ฐ ๋ญ๋น๋ฅผ ๋ง๊ธฐ ์ํด ํญ์ ์๋ฏธ ์๋ ๋ฐ์ดํฐ์ ๋ณต์ฌ๋ ์ฐ์ฐ์ด ๋ฐํํ๋์ง ํ์ธํด์ผ ํจ
# ์์ ์
def solution(data):
answer = data
for i in range(len(answer)):
temp = answer[i] * answer[i]
answer[i] = temp
return answer
# ์์ ํ
def solution(data):
return [i * i for i in data]
์ฌ๋ฌ ์ํฉ์์์ ์๊ฐ ๋ณต์ก๋ ์๊ฐํด๋ณด๊ธฐ
์ด์จ๋ ๋ฐ๋ณต๋ฌธ์ด ๊ฐ์ฅ ํฐ ํต์ฌ
- ๊ฐ์ฅ ์ค๋ ๊ฑธ๋ฆฌ๋ ๋ฐ๋ณต๋ฌธ์ ์ฐพ๋ ๊ฒ์ด ํต์ฌ์ด๊ณ , ์ด ๋ฐ๋ณต๋ฌธ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ตฌํ๋ ๊ฒ์ด ์ ์ผ ๋จผ์ ํด์ผ ํ ์ผ์
- ๋ค๋ฅด๊ฒ ๋งํ๋ฉด ํจ์๋ณ๋ก ๊ฑธ๋ฆฌ๋ ์๊ฐ ๋ณต์ก๋๋ฅผ ์์ธกํด ๊ฐ์ฅ ์ค๋ ๊ฑธ๋ฆฌ๋ ํจ์๊ฐ ์๋ค๋ฉด ๋ค๋ฅธ ์์ ์ ์ค์ผ์ง, ์๋๋ฉด ํด๋น ํจ์๋ฅผ ์ต์ ํํ ์ง ์ ๋ต์ ์ง๋ ๊ฒ์
- ์)
- Aํจ์: ๋ฐฐ์ด ์ ๋ ฌ - O(nlogn)
- Bํจ์: ๋ฐฐ์ด ์ํ - O(n)
- Cํจ์: ๋ ๋ฐฐ์ด ํจ๊ป ์ฌ์ฉ - O(n²)
- ๋ง์ฝ ์ด ๋ฌธ์ ๊ฐ ํต๊ณผํ์ง ๋ชปํ๋ค๋ฉด, ์ค๋ ๊ฑธ๋ฆฌ๋ ์์ ์ด Cํจ์๋ผ๋ ์ฌ์ค์ ์๊ณ ์์ผ๋ ์๋ฃ ๊ตฌ์กฐ๋ฅผ ๋ฐ๊ฟ ๊ฐ์ ํ ์ง, ๋ค๋ฅธ ํจ์์ ๋ ผ๋ฆฌ๋ฅผ ๋ณ๊ฒฝํด ์์ ๋์ ์ค์ด๋ ๋ฐฉ์์ผ๋ก ๊ฐ์ ํ ์ง ์ ํํ๋ฉด ๋จ
์ฐจ์์ ๊ณ์ ์๋ตํ์ง ์๊ธฐ
- ์๊ฐ ๋ณต์ก๋ ์ธก์ ํ ๋ ‘O(n)๋ค’, ‘O(nlogn)์ด๋ค’,… ์ฒ๋ผ ๋จ์ ์ง์ง ๋ง๊ณ ๋น ์ค ํ๊ธฐ๋ฒ์ ์ํด ์๋ต๋๋ ์ฐจํญ์ ๊ณ์๋ ๊ผผ๊ผผํ๊ฒ ๋ฐ์ ธ๋ณด์
- ์ฌ๋ฌ ์๊ฐ ๋ณต์ก๋๊ฐ ์ฎ์ด๋ฉด ํ๋ก๊ทธ๋จ์ ์ค์ ์คํ ์๊ฐ์ ์์ธกํ์ง ๋ชปํ๋ ์ผ์ด ์์ฃผ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ ๋ญ๋ฑ๊ทธ๋ ค์ ํํํ๊ธฐ๋ณด๋จ ์ฐจ์์ ๊ณ์๊น์ง ๋ชจ๋ ๊ณ์ฐํ์ฌ ๊ณ ๋ คํ์
- ์) 3n³ + 5n²์ ์๊ฐ ๋ณต์ก๋๋ O(n³)์
- 1์ด ์ ํ ์๊ฐ์ ๊ธฐ์ค์ผ๋ก ํ๋ค๋ฉด O(n³)์ ์ต๋ ์ ๋ ฅ ๊ฐ์๋ 500๊ฐ ์ ๋๊ฐ ๋จ (500³ = 125,000,000 = 1์ต 2์ฒ 5๋ฐฑ๋ง ) (1์ด์ 1์ต๋ฒ ์ฐ์ฐ ๊ฐ๋ฅ)
- ๋ฌธ์ ์์ ์ ๋ ฅ ๊ฐ์๊ฐ 500๊ฐ ์ฃผ์ด์ก๊ณ , ์ฝ๋๋ฅผ ๋น ์ค ํ๊ธฐ๋ฒ์ผ๋ก ๊ณ์ฐํด๋ณด๋ O(n³)๊ฐ ๋์ ์ ์ถํ์ง๋ง, ์คํจํจ..
- ์ด์ : ์ค์ 3n³์ 200๊ฐ๋ ๊ฐ๋นํ๊ธฐ ์ด๋ ค์..
ํฌ๊ธฐ N๊ณผ ํฌ๊ธฐ M์ ์๊ฐ ๋ณต์ก๋ ๊ณ์ฐ
- ํฌ๊ธฐ๊ฐ N๊ณผ M์ธ ๋ ๋ฐ์ดํฐ๋ก ์ฐ์ฐํ ๋ O(n²)? O(n³)?
- ('์๊ฐ ๋ณต์ก๋ ๊ณ์ฐํ๊ธฐ - ์ด๋ฆผ์ง์ํด๋ณด๊ธฐ' ๋ถ๋ถ ์ฐธ๊ณ )
for i in N: for j in M: ...
- ๊ฒฝ์ฐ์ ์๋ฅผ ๋ฐ์ ธ๋ณด์ - N์ ๊ฐ์ ๊ณ ์ ์ด๊ณ , M์ ๊ฐ์ด ๋ณํ๋ค๊ณ ๊ฐ์ ํ์
- M์ด ๋งค์ฐ ์ ์ ์ซ์์ผ ๊ฒฝ์ฐ(~20)
- M์ ์ฐ์ฐ์ ์ฌ์ค์ ์์ ์๊ฐ ์ด๋ด๋ก ๋๋๊ธฐ ๋๋ฌธ์ ์กฐ๊ธ ์ฐ์ฐ์ด ํฐ O(n)์ผ๋ก ๋ด๋ ๋ฌด๋ฐฉํจ
- M์ด ์ด๋ ์ ๋ ํฐ ์ซ์์ผ ๊ฒฝ์ฐ(~100)
- N × M์ด N²์ ๋์ด์์ง ์๋๋ค๋ฉด N × M์ผ๋ก ๊ณ์ฐํด์ผํจ
- M์ด N๊ณผ ๊ฑฐ์ ๋น์ทํ๊ฑฐ๋ ๋งค์ฐ ํฐ ์ซ์์ผ ๊ฒฝ์ฐ
- ์
๋ ฅ ๊ฐ์์ ํฌ๊ธฐ์ ๋น๋กํ๋ ๊ฒ๊ณผ ๋ค๋ฆ์์ผ๋ฏ๋ก ์ด ์์ ๋ถํฐ๋ O(n²)์ผ๋ก ์ทจ๊ธํด์ผ ํจ
-
- ์
๋ ฅ ๊ฐ์์ ํฌ๊ธฐ์ ๋น๋กํ๋ ๊ฒ๊ณผ ๋ค๋ฆ์์ผ๋ฏ๋ก ์ด ์์ ๋ถํฐ๋ O(n²)์ผ๋ก ์ทจ๊ธํด์ผ ํจ
- M์ด ๋งค์ฐ ์ ์ ์ซ์์ผ ๊ฒฝ์ฐ(~20)
'Study > ์ฝํ ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ์ฝ๋ฌธ] chapter1. ์ฝ๋ฉ ํ ์คํธ (0) | 2024.09.21 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค/C++] ๋ถ์์ ๋ง์ (0) | 2023.09.05 |
๋ฐฑ์ค ๋ธ๋ก ์ฆ2 3052๋ฒ: ๋๋จธ์ง (0) | 2023.03.28 |
๋ฐฑ์ค ๋ธ๋ก ์ฆ2 8958๋ฒ: OXํด์ฆ (0) | 2023.03.20 |
๋ฐฑ์ค ๋ธ๋ก ์ฆ2 2577๋ฒ: ์ซ์์ ๊ฐ์ (0) | 2023.03.12 |