๐ APS๋ ๋ฌด์์ธ๊ฐ
APS : Algorithm Problem Solving
๋๋ ๊ฐ์์์ ์ฒ์ ๋ฃ๊ฒ ๋ APS,, ํ๋ฒ ์ ๋ฆฌํด๋ณด๋ ค ํ๋ค.
์ฐ์ APS๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด ๋ฐฉ๋ฒ์ ๋งํ๋ค.
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด๋ฒ์๋ ๋ง์ ๊ฒ๋ค์ด ์๊ณ , ๊ทธ์ค์์ ์ฃผ์ด์ง ๋ฌธ์ ์ ๋ฐ๋ผ ์ํ๋ ๊ฒฐ๊ณผ๋ฅผ ๋ผ ์ ์๋๋ก ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ ๊ฒ์ด ๋ชฉํ์ด๋ค.
๊ทธ๋ ๋ค๋ฉด APS ๊ณต๋ถ๋ ์ ํด์ผ ํ ๊น ??
1. ์๊ณ ๋ฆฌ์ฆ ํ์ด๋ฒ์ ๊ณต๋ถํ๋ฉด์ ๋ฌธ์ ๊ตฌํ๋ ฅ์ ๊ธฐ๋ฅผ ์ ์๋ค.
2. ๋ค์ํ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ ๊ฒฝ์ฐ์ ๋๋ฒ๊น ๊ฒฝํ์ ์์ ์ ์์ ๊ฒ์ด๋ค.
- ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด๋ฅผ ํ๋ฉฐ ๋ฐ์ํ๋ ์ค๋ฅ๋ค์ ์ ํด๋ณด๊ณ , ์ด๋ฌํ ์ค๋ฅ๋ฅผ ํด๊ฒฐํด ๋๊ฐ๋ ๊ณผ์ ์์ฒด์์ ์ฐ๋ฆฌ๋ ๋ง์ ๊ฒ์ ๋ฐฐ์ฐ๊ณ ์ฑ์ฅํ ์ ์๋ค.
3. ๋ ผ๋ฆฌ์ ์ผ๋ก ์ฌ๊ณ ํ๋ ๋ฒ์ ๋ฐฐ์ฐ๊ฒ ๋๋ค.
- ์ฌ๋ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๋ฉฐ ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ๋ ผ๋ฆฌ์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์ด๊ฐ๋ ๋ฐฉ๋ฒ์ ๋ํด ๋ฐฐ์ธ ์ ์๋ค.
์ด๋ฌํ APS์ ๋ชฉํ๋ ์คํ์๊ฐ์ ์ค์ด๋ ๊ฒ์ ์๋ค. ์ ์ ์คํ์๊ฐ์ผ๋ก ์ ํํ๊ฒ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฒ์ด ๊ฐ์ฅ ์ค์ํ๋ค.
๋๋ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ๋ณธ๊ฒฉ์ ์ผ๋ก ํ๊ธฐ ์์ํ๋ฉด์ ์คํ์๊ฐ์ ์ค์ด๊ธฐ ์ํ ๊ณ ๋ฏผ์ ํ๊ฒ ๋์๋ค. ๋์ค์ ๋ ๊ณต๋ถํ๊ณ ๋ง์ ๋ฌธ์ ๋ค์ ํ์ด๋ณด๋ฉด์, ๊ฐ์ ํ์ด์์๋ ์คํ ์๊ฐ์ ์ค์ผ ์ ์๋ ๋ฐฉ๋ฒ์ ๊ณ ๋ฏผํด ๋ณด๊ณ ์ ๋ฆฌํด ์ฌ๋ฆด ๊ณํ์ด๋ค.
โฑ ์๊ฐ ๋ณต์ก๋
์๋ํ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ทจํด ์๊ฐ์ ์ ๋ํํ๋ ๊ฒ์ด๋ค. ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ๋ณต์ก๋๋ ์ฃผ๋ก ๋น -์ค ํ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ ๋ํ๋ธ๋ค. - by. ์ํค๋ฐฑ๊ณผ
๋ค์ ์ค๋ช ํ์๋ฉด ์๊ฐ ๋ณต์ก๋๋ ์คํ๋๋ ๋ช ๋ น๋ฌธ์ ๊ฐ์์ ๋ก์ง์ ํตํด ํ๋ก๊ทธ๋จ ์คํ ์ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๋ํ๋ธ ํจ์์ด๋ค.
์คํ์๊ฐ์ ์ค์ด๊ธฐ ์ํด์, ์ฆ ํจ์จ์ ์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ง๊ธฐ ์ํด์๋ ์ ๋ ฅ๊ฐ์ด ์ปค์ง๋๋ผ๋ ์ ์ ์ฐ์ฐ์ ํตํด ๊ฒฐ๊ณผ๋ฅผ ์ฐพ์ ์ ์๋ ์๊ฐ์ ๋จ์ถ์ํค๋ ๊ฒ์ด ์ค์ํ๋ค.
์ด๋ฌํ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋ํ๋ด๋ ๊ฒ์ด ๋ฐ๋ก Big-O ํ๊ธฐ๋ฒ์ด๋ค.
์๋ ์ ๋ ํ์ผ๋ก ๋น ์ค ํ๊ธฐ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๋ ค๋ค๊ฐ ๋ฌด์จ ๋ง์ธ์ง ๋ชจ๋ฅด๊ฒ ๊ณ , ์์ ๋ฅผ ์ ํ๊ธฐ ์ด๋ ค์ ํฌ๊ธฐํ์๋๋ฐ ์ธํผ์์ ๋ฐฐ์ฐ๋๊น ์๊ฐ๋ณด๋ค ์ด๋ ค์ด ๋ด์ฉ์ด ์๋๋ผ ๋นํฉํ๋ค ..
๐ Big-O ํ๊ธฐ๋ฒ
Big-O ํ๊ธฐ๋ฒ์ ๊ฒฝ์ฐ ์ฐ์ฐ์ด ๊ฐ์ฅ ๋ง์ด ์ผ์ด๋๋ ๊ฒฝ์ฐ(์ต์ ์ ๊ฒฝ์ฐ)๋ฅผ ๊ฐ์ ํ๋ค.
์๋ฅผ ๋ค์ด, ๋ฐฐ์ด์ ์์์๋ถํฐ ํ๋์ฉ ๋น๊ต๋ฅผ ์ฐพ์ ๋ {1, 44, 8, 34, 59, 90, 50}์ด๋ผ๋ ๋ฐฐ์ด์ด ์์ ๊ฒฝ์ฐ 50์ด๋ผ๋ ๊ฐ์ ์ฐพ๊ธฐ ์ํด์๋ 7๋ฒ์ ๋น๊ต ๋์ 50์ ์ฐพ์ ์ ์์ ๊ฒ์ด๋ค. ์ด์ ๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐ๋ณต์ก๋์์ ์ต์ ์ ๊ฒฝ์ฐ๋ผ๊ณ ํ๊ณ , 1์ ์ฐพ๋ ๊ฒฝ์ฐ ํ ๋ฒ์ ๋ฐ๋ก ์ฐพ์ ์ ์๊ธฐ ๋๋ฌธ์ ์ต์ ์ ๊ฒฝ์ฐ๋ผ๊ณ ํ๋ค.
์ง๊ธ์ ์์๋ ์์๊ฐ 7๊ฐ์ ๋ถ๊ณผํ์ง๋ง ์์์ ๊ฐ์๊ฐ 10000๊ฐ๋ฅผ ๋์ด๊ฐ๋ค๋ฉด ์ด๋จ๊น ? ์๋ง ์ต์ ์ ๊ฒฝ์ฐ์ ์ต์ ์ ๊ฒฝ์ฐ ์ฐจ์ด๊ฐ ๊ฝค ์ปค์ง ๊ฒ์ด๋ค.
์ด๋ ๊ฒ ๋ค์ํ ๊ฒฝ์ฐ์ ์ ์ค์์ ๊ฐ์ฅ ์ฐ์ฐ์ด ์ค๋ ๊ฑธ๋ฆฌ๋ ๊ฒฝ์ฐ๋ฅผ ๋๋นํด์ผ ํ๊ธฐ ๋๋ฌธ์, Big-O ํ๊ธฐ๋ฒ์ ์์ฃผ ์ฌ์ฉํ๊ฒ ๋๋ค.
Big-O ํ๊ธฐ๋ฒ์ ์ข ๋ฅ
์์ ๊ทธ๋ํ๋ Big O ์๊ฐ ๋ณต์ก๋์์ ์์ ์์ ๋ฐ๋ฅธ ์ฐ์ฐ ์๋ฅผ ๋ํ๋ธ ๊ทธ๋ํ์ด๋ค.
O(log n), O(n)์ ๊ฒฝ์ฐ ์์์๊ฐ ๋ง์ด ๋์ด๋๋๋ผ๋ ์ฐ์ฐ ์๊ฐ ํฌ๊ฒ ์ฐจ์ด ๋์ง ์๋๋ฐ, O(n!)์ด๋ O(2^n)๊ณผ ๊ฐ์ ๊ฒฝ์ฐ์๋ ์์์๊ฐ 10๋ง ๋๋๋ผ๋ ์ฐ์ฐ์ ์๊ฐ ๊ธฐํ๊ธ์์ ์ผ๋ก ๋์ด๋๋ ๊ฒ์ ๋ณผ ์ ์๋ค.
์ด๋ฌํ ์๊ฐ ๋ณต์ก๋๋ฅผ ์๊ณ ๋๋ฉด, ๋ฌธ์ ๋ฅผ ํ ๋์ ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํด์ผ ์๊ฐ์ด๊ณผ๊ฐ ์ผ์ด๋์ง ์์ ์ ์์์ง ์์ํ๋ฉฐ ํ ์ ์๊ฒ ๋๋ค.
๊ทธ๋ผ ๋ค์์๋ ๋ช ๊ฐ์ง ์ ๋ ฌ์ ๋ณด๋ฉด์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ตฌํด๋ณด๋๋ก ํ์.
'๐ป cs' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Spring | AOP์ ๋ํด ์์๋ณด์ !! (0) | 2023.07.27 |
---|---|
IT ์๋น์ค, Cloud ์๋น์ค์ ๋ํด ์์๋ณด์ (0) | 2023.07.12 |
์นดํ ์ผ | 2์ฃผ์ฐจ ๊ณผ์ issue ํด๊ฒฐ (3) | 2023.07.11 |
WEB | API ์์๋ณด๊ธฐ (0) | 2023.06.29 |
GIT | GIT ์์ ์ ๋ณต (1) (0) | 2023.06.15 |