30_Oct_2021 ๐ฐ ์๋ฆฌ์ค AI ํธ๋ TIL: ์ฌ๊ทํธ์ถ์ ์ด์ฉํ ๋ฌธ์ ํด๊ฒฐ
์ฌ๊ทํจ์
์ฌ๊ทํจ์๋ฅผ ๋์์ธ ํ๊ธฐ ์ํ 3 ๋จ๊ณ
1) ํจ์์ ์ ์๋ฅผ ๋ช
ํํ ํ๋ค
2) ๊ธฐ์ ์กฐ๊ฑด์์ ํจ์๊ฐ ์ ๋๋ก ๋์ํ๊ฒ ์์ฑํ๋ค
3) ํจ์๊ฐ ์ ๋๋ก ๋์ํ๋ค๊ณ ๊ฐ์ ํ๊ณ ํจ์๋ฅผ ์์ฑํ๋ค.
์ด๋ค ๋ฌธ์ ๋ ์ ์ผ ์ฒซ ๋ฒ์งธ๋ก ์๋ํด์ผ ํ ๋ฐฉ๋ฒ์ ๋ฌด์กฐ๊ฑด ์์ ํ์์ด๋ค.
๊ทธ๋ฌ๋ ์์ ํ์์ ๊ฒฝ์ฐ, ํ์๋ฒ์๊ฐ ์ปค์ง์๋ก ๋ถ๋ฆฌํ๋ค๋ ๋จ์ ์ ๊ฐ์ง๊ณ ์๋ค.
๋ฐ์ดํฐ๊ฐ ์ด๋ฏธ ์ ๋ ฌ๋ ์ํ๋ผ๋ฉด ์ด์งํ์์ ํ์ฉํ ์ ์๋ค.
- ์ค๊ฐ๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ฐพ๊ณ ์ ํ๋ ๊ฐ๊ณผ์ ํฌ๊ธฐ ๋น๊ต๋ฅผ ํ๋ค.
์ฐพ๋ ๊ฐ์ ํ์ํ ๋ ๊น์ง ๋ฒ์๋ฅผ ์ง์๋ก๊ทธ ๋งํผ ์ค์ฌ๋๊ฐ๋ฏ๋ก ์ต์ ์ ์๊ฐ ๋ณต์ก๋๋ O(logN)์ด๋ค.
๋ถํ ์ ๋ณต๋ฒ
๋ฌธ์ ๋ฅผ ์๋ฌธ์ ๋ก ๋ถํ ํ์ฌ ๊ฐ๊ฐ์ ์๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ์์ด๋ฉฐ, ์๋ฌธ์ ์ ํด๊ฒฐ ๊ฒฐ๊ณผ๋ฅผ ์ด์ฉํด ์ ์ฒด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด๋ค.
๋ถํ ์ ๋ณต๋ฒ์์๋ ์ํ์ ๋ฌธ์ ํด๊ฒฐ ๋ฅ๋ ฅ์ด ๊ฐ์ฅ ์ค์ํ๊ณ , ์ ์ ํค๋ณด๋์์ ์์ ์น์ฐ๊ณ ๋ ธํธ์ ํ์ ์ก์์ผ ํ๋ค.
ํฉ๋ณ ์ ๋ ฌ
๋ถํ ์ ๋ณต๋ฒ์ผ๋ก ํด๊ฒฐํ ์ ์๋ ๋ํ์ ์ธ ๋ฌธ์ ์์์ด๋ค.
์ ๋ ฌ๋์ง ์์ ๋ฐฐ์ด arr์ด ์๋ค๊ณ ํ์
arr = [3,5,7,2,5,9,13,11,24,11,24,11,23,1,4,5,3,2]
๋จผ์ ์ด ๋ฆฌ์คํธ๋ฅผ 2 ๋ถํ ํ๋ค.
arr1 = [2,3,5,5,7,9,11,13]
arr2 = [1,2,3,4,5,11,23,24]
#์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ผ๋ก ๋๋ ๋ฆฌ์คํธ๋ ์ ๋ ฌ๋์ด ์๋ค.
์ด ๋ ๋ฐฐ์ด์ ๋ค์ ํฉ์น๋ฉด ์ ๋ ฌ๋ ์ ์ฒด ๋ฐฐ์ด์ ๋ง๋ค ์ ์์ ๊ฒ์ด๋ค.
ํฉ์น๊ธฐ ์ํด์๋ ๊ฐ ๋ฆฌ์คํธ์ 0๋ฒ์งธ ์ธ๋ฑ์ค๋ฅผ ๋น๊ตํ๋ค.
๋ ์ธ๋ฑ์ค ๊ฐ์ ๋น๊ตํ์ฌ ๋ ์์ ๊ฐ์ ๋นผ์ ์๋ก ๋ง๋ ๋น ์ ์ฒด ๋ฐฐ์ด์ ๋ฃ์ด์ค๋ค.
ํฉ๋ณ์ ๋ ฌ์ ์๊ฐ๋ณต์ก๋
n๊ฐ์ ์์๋ฅผ ์ ๋ ฌํ๋ ๋ฐ ๋๋ ์๊ฐ์ = T(n)์ด๋ค.
์ฌ๊ธฐ์ T(n)์ ๋๋ก ๋๋ ๋ ๋ฐฐ์ด T(N/2) + T(N/2) ๋ฅผ ์ ๋ ฌํ๋ ์ด ์๊ฐ์ด๋ค.
์ฌ๊ธฐ์ ์ผ์ชฝ ๋ฐฐ์ด๊ณผ ์ค๋ฅธ์ชฝ ๋ฐฐ์ด์ ์์๋ฅผ ํ๋ํ๋ ์ ๋ถ ๋น๊ตํ๊ธฐ ๋๋ฌธ์
T(N) = T(N/2) + T(N/2) + O(N) ์ด๋ค. N์ด 1์ด ๋ ๋๊น์ง 2๋ก ๋๋๋ ์๊ฐ์ logN์ด๋ค.
์ด๊ฒ์ ๋ค์ ํฉ์น๋ ๋ฐ์ O(N)์ ์๊ฐ์ด ์์๋๊ณ , ํด๋น ์์ ์ logN ๋ฒ ์ํํ๊ธฐ ๋๋ฌธ์ ์ด ์ ๋ ฌ์๊ฐ์ O(NlogN)์ด ๋๋ค.
arr = [2,1,-2,5,-10,3,2,5,-3,7,9,-10]
๋ฆฌ์คํธ๋ฅผ ๋๋ก ๋๋ ์ ์ฐ์๋ถ๋ถ ์ต๋ํฉ์ ์ฐพ์๋ณด๋ฉด, [2,1,-2,5] = 6, [2,5,-3,7,9] = 20์ด ๋์จ๋ค. ๋ํ ์ ์ฒด ๋ฐฐ์ด์์์ ์ฐ์์ต๋ํฉ์ ์ฐพ์๋ณด๋ฉด, [3,2,5] = 10์ด๋ค.
์ฌ๊ธฐ์ ์๋ฅธ ์ง์ ์ ํฌํจํ๋ ์ฐ์๋ถ๋ถ์ต๋ํฉ์, ์๋ฅธ ์ง์ ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ ๋ ๋ฆฝ์ ์ผ๋ก ์๊ฐํ๋ ๊ฒ์ด๋ค. ์์ ๋ฐฐ์ด์์ ์๋ฅธ ์ง์ ์ ๊ธฐ์ค์ด ๋๋ ์์๋ 3(์ผ์ชฝ) 2(์ค๋ฅธ์ชฝ)์ด๋ค.
์ด์ ๊ฐ ์์๋ฅผ ํฌํจํ๋ ๊ธฐ์ค์ผ๋ก ๊ฐ ์ฐ์๋ถ๋ถ ์ต๋ํฉ์ ๊ตฌํ๋ฉด,
์ผ์ชฝ ๋ฐฐ์ด ๊ธฐ์ค [3] = 3 ์ด ๊ฐ์ฅ ํฌ๊ณ , ์ค๋ฅธ์ชฝ ๋ฐฐ์ด ๊ธฐ์ค [2,5,-3,7,9] = 20์ผ๋ก ๊ฐ์ฅ ํฌ๋ค.
ํ์๋ฒ (Greedy)
์๊ฐ์ ์ต์ ์ ์ ํ์ด ๊ถ๊ทน์ ์ผ๋ก ์ต์ ์ ์ ํ์ด๋ค. ๋จ์ํ ๋ฐฉ๋ฒ๋ ๋ฌธ์ ํ์ด์๋ ์ถฉ๋ถํ๋ค.
์์ ํ์์ ์ฌ์ฉํ๋ฉด, ๋ฒ์๊ฐ ์ปค์ง์๋ก ๊ฒฝ์ฐ์ ์๊ฐ ์ด๋ง์ด๋งํ๊ฒ ์ปค์ง๊ธฐ ๋๋ฌธ์ ์๊ฐํจ์จ์ฑ์ ๋ณด์ฅํ๊ธฐ ํ๋ค๋ค. ๋ฐ๋ผ์, ์ด์ ๊ฐ์ ๊ฒฝ์ฐ ํ์๋ฒ์ ์ด์ฉํ๋ฉฐ ํจ๊ณผ์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.
์์ฝ
๊ทธ๋ฌ๋, ํ์๋ฒ์ ์๊ฐ์ ์ต์ ์ ์ ํ์ ํ๋ ๊ฐ์ค์ ํ์ ํ๊ธฐ ์ด๋ ค์ฐ๋ฉฐ, ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ๋ค๋ ๊ฒ์ ์ฆ๋ช ํ๊ธฐ ์ด๋ ต๊ธฐ ๋๋ฌธ์ด๋ค.
๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ ์์ฝ
๋ถํ ์ ๋ณต๋ฒ์ ์ด๋ ต๋ค.
๋ถํ ์ ๋ณต๋ฒ์ผ๋ก ํด๊ฒฐํ ์ ์๋ ๋ํ์ ์ธ ์์ ๋ก๋:
ํฉ๋ณ์ ๋ ฌ, ํต์ ๋ ฌ, ๊ฑฐ๋ญ์ ๊ณฑ ๊ตฌํ๊ธฐ, ์ฐ์ ๋ถ๋ถ ์ต๋ํฉ, ๊ฐ์ฅ ๊ฐ๊น์ด ๋ ์ ์ฐพ๊ธฐ, ํ์คํ ๊ทธ๋จ๋ฑ์ด ์์๋ค.
์ด ๋ฌธ์ ์์ ๋ฐ๊ฒฌํ ์ ์์๋ ์ ์, ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ๋๋๊ณ , ์์ ๋ฌธ์ ๋ฅผ ์ด๋ป๊ฒ ํด๊ฒฐํด์ผ ํ๋ฉฐ, ํด๊ฒฐํ ์์ ๋ฌธ์ ๋ฅผ ๋ ์ด๋ป๊ฒ ํฉ์ณ์ ๊ฒฐ๊ณผ๋ฅผ ๋จ๊ธธ ๊ฒ์ธ๊ฐ์ ๋ํ ๋ฌธ์ ์๋ค.
์ด๋ฅผ ํ๋ จํ๊ธฐ ์ํด์๋ ๊ด๋ จ ๋ฌธ์ ๋ค์ ๋ง์ด ํ์ด๋ณด๋ ๊ฒ์ด ์ค์ํ๋ค.
์ฝ๋ฉ ๋ฅ๋ ฅ๊ณผ ๋ฌธ์ ํด๊ฒฐ ๋ฅ๋ ฅ์ ๋ค๋ฅด๋ค
์ฝ๋ฉ๊ณผ ๋ฌธ์ ํด๊ฒฐ ๋ฅ๋ ฅ์ ๊ตฌ๋ณ๋์ด์ผ ํ๋ฉฐ, ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ ๋์๋ ํค๋ณด๋๊ฐ ์๋ ์ค์ค๋ก์ ๋ ผ๋ฆฌ๋ฅผ ๊ฐ์ง๊ณ ๋ ธํธ์ ํ์ผ๋ก ํ์ด๋ฅผ ๋ ์ฌ๋ ค์ผ ํ ๊ฒ์ด๋ค.
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(30_Oct_2021 ๐ฐ ์๋ฆฌ์ค AI ํธ๋ TIL: ์ฌ๊ทํธ์ถ์ ์ด์ฉํ ๋ฌธ์ ํด๊ฒฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@juanito_y247/30Oct2021-์๋ฆฌ์ค-AI-ํธ๋-TIL-์ฌ๊ทํธ์ถ์-์ด์ฉํ-๋ฌธ์ -ํด๊ฒฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค