์ด๋ค ์ผ์ ํ๋ ์์๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.์ฆ, ๋ฐฉํฅ ๊ทธ๋ํ์ ์กด์ฌํ๋ ๊ฐ ์ ์ ๋ค์ ์ ํ ์์๋ฅผ ์๋ฐฐํ์ง ์์ผ๋ฉด์ ๋ชจ๋ ์ ์ ์ ๋์ดํ๋ ๊ฒ์์ ์ ๋ ฌ(Topological Sort)์ด๋(https://gmlwjd9405.github.io/2018/08/27/alg
์ ์ฌํ ๋์์ ๊ฐ์ง ์๋ฃ๊ตฌ์กฐ์ ํด๋์ค์ ๋ํ ์ํ์ ๋ชจ๋ธ์ ๊ฐ๋ฆฌํด๋ง์ ์ถ์ ๋ฐ์ดํฐ ํ์ ์ ๊ฐ๊ธฐ ํด๋์ค๋ ๋ค๋ฅด์ง๋ง, ๊ธฐ๋ฅ์ ์ผ๋ก๋ ๋์ผํ๊ฒ ๊ตฌํ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง ์ ์์๋ฐฐ์ด ๊ธฐ๋ฐ์ ์ฐ์ ๋ฐฉ์ํฌ์ธํธ ๊ธฐ๋ฐ์ ์ฐ๊ฒฐ ๋ฐฉ์ํ์ด์ฌ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ, ๋ฏธ์ ์คํ์ธ ์ง์, ์ต๊ธธ์ฐ ์ฎ
๋ฐ์ดํฐ์์ min/max๊ฐ์ ๋น ๋ฅด๊ฒ ์ฐพ๊ธฐ ์ํด ๊ณ ์๋ ์์ ์ด์งํธ๋ฆฌ๋ ธ๋๋ฅผ ์ฝ์ ํ ๋ ์ตํ๋จ ์ผ์ชฝ ๋ ธ๋๋ถํฐ ์ฐจ๋ก๋ก ์ฝ์ (์์ ์ด์งํธ๋ฆฌ ํน์ง)min/max๊ฐ ์ฐพ๋๋ฐ O(logn)์ฐ์ ์์ ํ์ ๊ฐ์ด min/max๋ฅผ ๋น ๋ฅด๊ฒ ์ฐพ์์ผํ๋ ์๋ฃ๊ตฌ์กฐ ๋ฐ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ์ ๋ฑ์ ํ์ฉ๋จ๊ฐ ๋ ธ
1. ํ ๊ตฌ์กฐ 2. ํ์ด์ฌ queue ๋ผ์ด๋ธ๋ฌ๋ฆฌ 3. FIFO queue ๊ตฌํํ๊ธฐ 4. LIFO queue ๊ตฌํํ๊ธฐ 5. Priority queue ๊ตฌํํ๊ธฐ 6. Queue๋ ์ด๋์ ์ฐ์ด๋?
ํ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ (http://egloos.zum.com/js7309/v/11164744#:~:text=%5BSort%5D%20%ED%8C%80%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%20algor
ํ๋ก๊ทธ๋๋ฐ์ ์์ ์๋ฆฌ๋ฅผ ์ ์ฉํ๋ ๋ฐฉ๋ฒ์ ์ตํ๊ณ ,์ฐ์ต์ ํตํด ์ต์ํด์ ธ์ผ ํจ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ์ ํ๋ก๊ทธ๋๋ฐ ๋ํ์!ํ๋ก๊ทธ๋๋ฐ ์์ฒด์ ์ต์ํ์ง ์๋ค๋ฉด,๋ฐ๋์ ๊ฐ๋จํ ๋ฌธ์ ๋ฅผ ์ค์ค๋ก ์ฝ๋๋ก ๋ง๋ค ์ ์๋๋ก ํด์ผํจ์ต์ 10์ค์ ์ฝ๋๋ ์ค์ค๋ก ์์ฑํ ์ ์์ด์ผ ํจํ๋ก๊ทธ๋๋ฐ์ ๊ฐ๋ฅ
๋ฐ์ดํฐ๋ฅผ ๋์ดํ๊ณ , ๊ฐ ๋ฐ์ดํฐ๋ฅผ ์ธ๋ฑ์ค์ ๋์ํ๋๋ก ๊ตฌ์ฑํ ๋ฐ์ดํฐ ๊ตฌ์กฐํ์ด์ฌ ๋ฆฌ์คํธ๊ฐ์ ์ข ๋ฅ์ ๋ฐ์ดํฐ๋ฅผ ํจ์จ์ ์ผ๋ก ๊ด๋ฆฌํ๊ธฐ ์ํด ์ฌ์ฉ๊ฐ์ ์ข ๋ฅ์ ๋ฐ์ดํฐ๋ฅผ ์์ฐจ์ ์ผ๋ก ์ ์ฅ์ฅ์ : \* ๋น ๋ฅธ ์ ๊ทผ ๊ฐ๋ฅ (์ธ๋ฑ์ค)์ฒซ ๋ฐ์ดํฐ์ ์์น์์ ์๋์ ์ธ ์์น๋ก ๋ฐ์ดํฐ ์ ๊ทผ (์ธ๋ฑ์ค ๋ฒ
์ค์ ์๋ ํ์์ ์ ์ฌ๊ฐ์ฅ ๋จผ์ ๋ฃ์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ฅ ๋จผ์ ๊บผ๋ผ ์ ์๋ ๊ตฌ์กฐFIFO (First-in, First-Out)LILO (Last-In, Last-Out)์ถ์ฒhttp://www.stoimen.com/blog/2012/06/05/computer-alg
๋ฐ์ดํฐ๋ฅผ ์ ํ์ ์ผ๋ก ์ ๊ทผํ ์ ์๋ ๊ตฌ์กฐ \* ํ์ชฝ ๋์์๋ง ์๋ฃ๋ฅผ ๋ฃ๊ฑฐ๋ ๋บ ์ ์๋ ๊ตฌ์กฐ๊ฐ์ฅ ๋์ค์ ์์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ฅ ๋จผ์ ๋นผ๋ผ ์ ์๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ \* ํ : FIFO ์ ์ฑ ์คํ : LIFO ์ ์ฑ ์คํ์ LIFO, FILO ๋ฐ์ดํฐ ๊ด๋ฆฌ ๋ฐฉ์์ ๋ฐ๋ฆ LIFO
์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ผ๊ณ ๋ ํจ๋ฐฐ์ด์ ์์ฐจ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ๊ณต๊ฐ์ ๋ฐ์ดํฐ๋ฅผ ๋์ดํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋งํฌ๋ ๋ฆฌ์คํธ๋ ๋จ์ด์ง ๊ณณ์ ์กด์ฌํ๋ ๋ฐ์ดํฐ๋ฅผ ํ์ดํ๋ก ์ฐ๊ฒฐํด์ ๊ด๋ฆฌํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ณธ๋ C์ธ์ด์์๋ ์ฃผ์ํ ๋ฐ์ดํฐ๊ตฌ์กฐ!, ํ์ด์ฌ์ ๋ฆฌ์คํธ ํ์ ์ด ๋งํฌ๋ ๋ฆฌ์คํธ์ ๊ธฐ๋ฅ์ ๋ชจ๋ ์ง์!๋งํฌ๋
ํธ๋ฆฌ: node์ branch๋ฅผ ์ด์ฉํด์, ์ฌ์ดํด์ ์ด๋ฃจ์ง ์๋๋ก ๊ตฌ์ฑํ ๋ฐ์ดํฐ ๊ตฌ์กฐ์ค์ ๋ก ์ด๋์ ๋ง์ด ์ฌ์ฉ๋๋?ํธ๋ฆฌ ์ค ์ด์ง ํธ๋ฆฌ(binary tree)ํํ์ ๊ตฌ์กธ, ํ์(๊ฒ์) ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ์ ์ํด ๋ง์ด ์ฌ์ฉ๋จnode : ํธ๋ฆฌ์์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ๊ธฐ๋ณธ ์์ (๋ค๋ฅธ
์ ํ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ์ด๋..? (https://mwlab.tistory.com/17)
๋ณต์กํ ๋ฌธ์ ๋ฅผ "์ฌ๊ท"๋ฅผ ํตํด ๊ฐ๋จํ ํ์ ๋ฌธ์ ๋ก ๋ถ๋ฅํ์ฌ ๋จ์ํํ์ฌ ํด๊ฒฐํ๋ ๋ฐฉ๋ฒ์ด๋ค ๋ฌธ์ ๊ฐ ์ต์ ๋ถ๋ถ ๊ตฌ์กฐ(optimal substructure)์ ์ค๋ณต๋๋ ๋ถ๋ถ ๋ฌธ์ (overlapping subproblem)๋ฅผ ๊ฐ๊ณ ์๋ค๋ฉด, ๋์ ๊ณํ๋ฒ์ผ๋ก ํด๊ฒฐํ ์ ์์๋ต์ ๊ตฌ
https://www.fun-coding.org/Chapter19-greedy-live.html
0) ~ ~ ~ ~ max01) ~ ~ ~ max1 max02) ~ ~ max2 max1 max03) ~ max3 max2 max1 max0์ข ๋ฃ0) min0 ~ ~ ~ ~ : ์ ์ฒด ๋ฆฌ์คํธ(index 0 ~ 4)์์ ์ ์ผ ์์ ์์๋ฅผ ์ฐพ์์ index 0 ์์น์1) mi
https://seriouscomputerist.atariverse.com/media/pdf/book/Discipline%20of%20Programming.pdfํ๋ก๊ทธ๋๋จธ๋ฅผ ์ํ ๊ณต๋ถ๋ก (https://javaiyagi.tistory.com/477)
์ฝ์๊ฐ 1, ์๊ธฐ์์ ๋ฐ์ ์๋ ์ ๋ถ (1์ ์์ ์๋)0.00010184100000000182์ด ๊ฑธ๋ ธ์!https://burningrizen.tistory.com/31?category=801405