๐ ์ ์ฒด ์นดํ ๊ณ ๋ฆฌ
[ํ๋ก๊ทธ๋๋จธ์ค] ์ต์๊ฐ ๋ง๋ค๊ธฐ (level2, python)
๋ฌธ์ ์ค๋ช ๊ธธ์ด๊ฐ ๊ฐ์ ๋ฐฐ์ด A, B ๋๊ฐ๊ฐ ์์ต๋๋ค. ๊ฐ ๋ฐฐ์ด์ ์์ฐ์๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ๋ฐฐ์ด A, B์์ ๊ฐ๊ฐ ํ ๊ฐ์ ์ซ์๋ฅผ ๋ฝ์ ๋ ์๋ฅผ ๊ณฑํฉ๋๋ค. ์ด๋ฌํ ๊ณผ์ ์ ๋ฐฐ์ด์ ๊ธธ์ด๋งํผ ๋ฐ๋ณตํ๋ฉฐ, ๋ ์๋ฅผ ๊ณฑํ ๊ฐ์ ๋์ ํ์ฌ ๋ํฉ๋๋ค. ์ด๋ ์ต์ข ์ ์ผ๋ก ๋์ ๋ ๊ฐ์ด ์ต์๊ฐ ๋๋๋ก ๋ง๋๋ ๊ฒ์ด ๋ชฉํ์ ๋๋ค. (๋จ, ๊ฐ ๋ฐฐ์ด์์ k๋ฒ์งธ ์ซ์๋ฅผ ๋ฝ์๋ค๋ฉด ๋ค์์ k๋ฒ์งธ ์ซ์๋ ๋ค์ ๋ฝ์ ์ ์์ต๋๋ค.) ์๋ฅผ ๋ค์ด A = [1, 4, 2] , B = [5, 4, 4] ๋ผ๋ฉด A์์ ์ฒซ๋ฒ์งธ ์ซ์์ธ 1, B์์ ์ฒซ๋ฒ์งธ ์ซ์์ธ 5๋ฅผ ๋ฝ์ ๊ณฑํ์ฌ ๋ํฉ๋๋ค. (๋์ ๋ ๊ฐ : 0 + 5(1x5) = 5) A์์ ๋๋ฒ์งธ ์ซ์์ธ 4, B์์ ์ธ๋ฒ์งธ ์ซ์์ธ 4๋ฅผ ๋ฝ์ ๊ณฑํ์ฌ ๋ํฉ๋๋ค. (๋์ ๋ ๊ฐ : 5 + 16(4x4) = 21..
[ํ๋ก๊ทธ๋๋จธ์ค] ์ด์ง ๋ณํ ๋ฐ๋ณตํ๊ธฐ (level2, python)
๋ฌธ์ ์ค๋ช 0๊ณผ 1๋ก ์ด๋ฃจ์ด์ง ์ด๋ค ๋ฌธ์์ด x์ ๋ํ ์ด์ง ๋ณํ์ ๋ค์๊ณผ ๊ฐ์ด ์ ์ํฉ๋๋ค. x์ ๋ชจ๋ 0์ ์ ๊ฑฐํฉ๋๋ค. x์ ๊ธธ์ด๋ฅผ c๋ผ๊ณ ํ๋ฉด, x๋ฅผ "c๋ฅผ 2์ง๋ฒ์ผ๋ก ํํํ ๋ฌธ์์ด"๋ก ๋ฐ๊ฟ๋๋ค. ์๋ฅผ ๋ค์ด, x = "0111010"์ด๋ผ๋ฉด, x์ ์ด์ง ๋ณํ์ ๊ฐํ๋ฉด x = "0111010" -> "1111" -> "100" ์ด ๋ฉ๋๋ค. 0๊ณผ 1๋ก ์ด๋ฃจ์ด์ง ๋ฌธ์์ด s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. s๊ฐ "1"์ด ๋ ๋๊น์ง ๊ณ์ํด์ s์ ์ด์ง ๋ณํ์ ๊ฐํ์ ๋, ์ด์ง ๋ณํ์ ํ์์ ๋ณํ ๊ณผ์ ์์ ์ ๊ฑฐ๋ ๋ชจ๋ 0์ ๊ฐ์๋ฅผ ๊ฐ๊ฐ ๋ฐฐ์ด์ ๋ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ s์ ๊ธธ์ด๋ 1 ์ด์ 150,000 ์ดํ์ ๋๋ค. s์๋ '1'์ด ์ต์ ํ๋ ์ด์ ํฌํจ๋์ด ์์ต๋๋ค. ์ ์ถ๋ ฅ ์..
[ํ๋ก๊ทธ๋๋จธ์ค] JadenCase ๋ฌธ์์ด ๋ง๋ค๊ธฐ (level2, python)
๋ฌธ์ ์ค๋ช JadenCase๋ ๋ชจ๋ ๋จ์ด์ ์ฒซ ๋ฌธ์๊ฐ ๋๋ฌธ์์ด๊ณ , ๊ทธ ์ธ์ ์ํ๋ฒณ์ ์๋ฌธ์์ธ ๋ฌธ์์ด์ ๋๋ค. ๋จ, ์ฒซ ๋ฌธ์๊ฐ ์ํ๋ฒณ์ด ์๋ ๋์๋ ์ด์ด์ง๋ ์ํ๋ฒณ์ ์๋ฌธ์๋ก ์ฐ๋ฉด ๋ฉ๋๋ค. (์ฒซ ๋ฒ์งธ ์ ์ถ๋ ฅ ์ ์ฐธ๊ณ ) ๋ฌธ์์ด s๊ฐ ์ฃผ์ด์ก์ ๋, s๋ฅผ JadenCase๋ก ๋ฐ๊พผ ๋ฌธ์์ด์ ๋ฆฌํดํ๋ ํจ์, solution์ ์์ฑํด์ฃผ์ธ์. ์ ํ ์กฐ๊ฑด s๋ ๊ธธ์ด 1 ์ด์ 200 ์ดํ์ธ ๋ฌธ์์ด์ ๋๋ค. s๋ ์ํ๋ฒณ๊ณผ ์ซ์, ๊ณต๋ฐฑ๋ฌธ์(" ")๋ก ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค. ์ซ์๋ ๋จ์ด์ ์ฒซ ๋ฌธ์๋ก๋ง ๋์ต๋๋ค. ์ซ์๋ก๋ง ์ด๋ฃจ์ด์ง ๋จ์ด๋ ์์ต๋๋ค. ๊ณต๋ฐฑ๋ฌธ์๊ฐ ์ฐ์ํด์ ๋์ฌ ์ ์์ต๋๋ค. ์ ์ถ๋ ฅ ์ s return "3people unFollowed me" "3people Unfollowed Me" "for the last week" "..
[ํ๋ก๊ทธ๋๋จธ์ค] ์ต๋๊ฐ๊ณผ ์ต์๊ฐ (level2, python)
๋ฌธ์ ์ค๋ช ๋ฌธ์์ด s์๋ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋ ์ซ์๋ค์ด ์ ์ฅ๋์ด ์์ต๋๋ค. str์ ๋ํ๋๋ ์ซ์ ์ค ์ต์๊ฐ๊ณผ ์ต๋๊ฐ์ ์ฐพ์ ์ด๋ฅผ "(์ต์๊ฐ) (์ต๋๊ฐ)"ํํ์ ๋ฌธ์์ด์ ๋ฐํํ๋ ํจ์, solution์ ์์ฑํ์ธ์. ์๋ฅผ๋ค์ด s๊ฐ "1 2 3 4"๋ผ๋ฉด "1 4"๋ฅผ ๋ฆฌํดํ๊ณ , "-1 -2 -3 -4"๋ผ๋ฉด "-4 -1"์ ๋ฆฌํดํ๋ฉด ๋ฉ๋๋ค. ์ ํ ์กฐ๊ฑด s์๋ ๋ ์ด์์ ์ ์๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์์ต๋๋ค. ์ ์ถ๋ ฅ ์ s return "1 2 3 4" "1 4" "-1 -2 -3 -4" "-4 -1" "-1 -1" "-1 -1" ํ์ด์ฝ๋ def solution(s): arr = list(map(int, s.split())) arr.sort() answer = " ".join([str(arr[0]), str(arr[-1..
![[Algorithm] ํ ์ ๋ ฌ (Heap Sort)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbnhJVn%2FbtrLgZvKPnZ%2FLVZVsKIUHBU67gPtbYxFGK%2Fimg.png)
[Algorithm] ํ ์ ๋ ฌ (Heap Sort)
ํ ์ ๋ ฌ (Heap Sort) ํ ์ ๋ ฌ์ ์๊ฐ ๋ณต์ก๋๊ฐ O(NlogN)์ธ ์ ๋ ฌ์ผ๋ก, ๋ฒ๋ธ / ์ ํ / ์ฝ์ ์ ๋ ฌ์ ๋นํด ์ฐ์ํ ์ฑ๋ฅ์ ๊ฐ์ง๊ณ ์๋ค. ์ฐ์ ํ ์ ๋ ฌ์ ์ดํด๋ณด์. ํ์ ์๋ฃ๊ตฌ์กฐ ์ค ํ๋๋ก, ์ด 'Heap' ์๋ฃ๊ตฌ์กฐ์ ํน์ฑ์ ํ์ฉํ ์ ๋ ฌ ๋ฐฉ๋ฒ์ด๋ค. ํ์ ์์ ์ด์งํธ๋ฆฌ์ ์ผ์ข ์ผ๋ก, ์ฌ๋ฌ ๊ฐ๋ค ์ค์์ ์ต์๊ฐ ํน์ ์ต๋๊ฐ์ ๋น ๋ฅด๊ฒ ์ฐพ๊ธฐ ์ํด ์ค๊ณ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ํ์ ๋์จํ ์ ๋ ฌ ์ํ(๋ฐ ์ ๋ ฌ ์ํ)๋ฅผ ์ ์งํ๊ณ , ์ด๋ฅผ ์ฝ๊ฒ ํ์ดํ๋ฉด ๋ถ๋ชจ ๋ ธ๋์ ํค ๊ฐ์ด ์์ ๋ ธ๋์ ํค ๊ฐ๋ณด๋ค ํญ์ ํฐ(์์) ์ด์ง ํธ๋ฆฌ๋ฅผ ๋งํ๋ค. ๋ถ๋ชจ ๋ ธ๋์ ํค ๊ฐ์ด ์์ ๋ ธ๋์ ํค ๊ฐ๋ณด๋ค ํฐ ์ง, ์์ ์ง์ ๋ฐ๋ผ ํ์ ์ข ๋ฅ๊ฐ ๋๋๋ค. - ์ต๋ ํ (Max Heap) : ๋ถ๋ชจ ๋ ธ๋์ ํค ๊ฐ์ด ์์ ๋ ธ๋์ ํค ๊ฐ๋ณด๋ค ํฐ ํ → ๋ฃจํธ ..
[Alogrithm] ์ฝ์ ์ ๋ ฌ (Injection Sort)
์ฝ์ ์ ๋ ฌ (Injection Sort) ์ฝ์ ์ ๋ ฌ์, ํ ๋ฐฐ์ด์ '์ ๋ฐฐ์ด'๊ณผ '๋ท ๋ฐฐ์ด'๋ก ์ชผ๊ฐ์ด '๋ท ๋ฐฐ์ด'์ ์์๋ฅผ ์ ๋ ฌ๋ '์ ๋ฐฐ์ด'์ ๋ค์ด๊ฐ ์ฌ๋ฐ๋ฅธ ์์น๋ฅผ ์ฐพ์ ์ฝ์ ํ๋ ์ ๋ ฌ์ด๋ค. ์ ์ดํด๊ฐ ๋์ง ์์ ์ ์์ผ๋ฏ๋ก, ํ๋์ฉ ์ค๋ช ์ ํด๋ณด๊ฒ ๋ค. ๋ค์๊ณผ ๊ฐ์ด ์ฃผ์ด์ง ๋ฐฐ์ด์ด ์๋ค๊ณ ํ์. array = [3, 4, 5, 2, 1, 6, 7] 3 4 5 2 1 6 7 ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ์ , ์ฃผ์ด์ง ๋ฐฐ์ด์ ๋ค์๊ณผ ๊ฐ์ด ๋นจ๊ฐ ๋ถ๋ถ๊ณผ ํ๋ ๋ถ๋ถ์ผ๋ก ๋ณผ ์ ์๋ค. ๋นจ๊ฐ ๋ถ๋ถ์ ์ด๋ฏธ ์ ๋ ฌ์ด ๋ '์ ๋ฐฐ์ด', ํ๋ ๋ถ๋ถ์ '์ ๋ฐฐ์ด'์ ์ฝ์ ์ด ๋๊ธฐ ์ํด ๋๊ธฐํ๊ณ ์๋ '๋ท ๋ฐฐ์ด'๋ก ์ดํดํ๋ฉด ์ข๋ค. ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ '๋ท ๋ฐฐ์ด'์ ๋ค์ด์๋ ์ฒซ ๋ฒ์งธ ์์๋ถํฐ ์์ํ๋ฏ๋ก, ์ ์ฒด ๋ฐฐ์ด๋ก ์๊ฐํ๋ฉด ๋ ๋ฒ์งธ ์์๋ถํฐ ์ ๋ ฌ ๋์์ด..
![[Algorithm] ์ ํ ์ ๋ ฌ (Selection Sort)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FwQhOE%2FbtrJCpDjJSE%2FGknqSFyLIU0NkIyKjILls1%2Fimg.png)
[Algorithm] ์ ํ ์ ๋ ฌ (Selection Sort)
์ ํ ์ ๋ ฌ (Selection Sort) ์ ํ ์ ๋ ฌ์, ๋ฐฐ์ด์ ์ ์ผ ์์์๋ถํฐ ํด๋น ์๋ฆฌ์ ๋ค์ด๊ฐ ์ซ์๋ฅผ ์ ํํ๋ ์ ๋ ฌ์ด๋ค. ๋ค์ด๊ฐ ์ซ์๋ฅผ ๊ฒฐ์ ํ๋ ๊ฒ์ ๋ฐฐ์ด ๋ด์ ๋ชจ๋ ์์๋ฅผ ๋น๊ตํด ๊ฐ์ฅ ์์ ๊ฒ์ ์ ํํ๋ค. ๋ค์ loop ๋ถํฐ๋ ์ด๋ฏธ ์๋ฆฌ๊ฐ ๊ฒฐ์ ๋ ์ซ์๋ ๋น๊ตํ์ง ์๊ณ , ๋๋จธ์ง ์๋ค ์ค์ ๋ค์ด๊ฐ ๊ฒ์ ์ฐพ๊ธฐ๋ฅผ ๋ฐ๋ณตํ๋ค. ์ฆ, 1๋ฒ์งธ loop์์๋ ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ์๋ฆฌ์ ๋ค์ด๊ฐ ์์๋ฅผ n๊ฐ๋ฅผ ๋ชจ๋ ๋น๊ตํด ์ ํํ๊ณ , 2๋ฒ์งธ loop์์๋ ์ด๋ฏธ ๊ฒฐ์ ๋ ์ฒซ ๋ฒ์งธ ์๋ฆฌ์ ์ซ์๋ฅผ ์ ์ธํ ๋๋จธ์ง n-1๊ฐ๋ฅผ ๋น๊ตํด ๋ ๋ฒ์งธ ์๋ฆฌ์ ๋ค์ด๊ฐ ์ซ์๋ฅผ ๊ฒฐ์ ํ๋ค. 3๋ฒ์ฌ loop์์๋ ์ด๋ฏธ ๊ฒฐ์ ๋ 1~2๋ฒ์งธ ์๋ฆฌ์ ์ซ์๋ฅผ ์ ์ธํ ๋๋จธ์ง n-2๊ฐ๋ฅผ ๋น๊ตํด ์ธ ๋ฒ์งธ ์๋ฆฌ์ ๋ค์ด๊ฐ ์ซ์๋ฅผ ๊ฒฐ์ ํ๊ณ , ๋ชจ๋ ์๋ฆฌ์ ๋ค์ด๊ฐ ์ซ์๊ฐ ์ ํด..
![[Algorithm] ๋ฒ๋ธ ์ ๋ ฌ (Bubble Sort)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcktF30%2FbtrJBFS6n6U%2FzipvEED7or08CAvWXskrHk%2Fimg.png)
[Algorithm] ๋ฒ๋ธ ์ ๋ ฌ (Bubble Sort)
๋ฒ๋ธ ์ ๋ ฌ (Bubble Sort) ๋ฒ๋ธ ์ ๋ ฌ์, ์ด์ํ ๋ ์ซ์๋ฅผ ๊ณ์ํด์ ๋น๊ตํ๋ฉฐ ์ ํด์ง ๊ท์น์ ๋ฐ๋ผ ์๋ฆฌ๋ฅผ ์ค์์นญํ๋ ์ ๋ ฌ์ด๋ค. ์๋ฅผ ๋ค์ด, ์ค๋ฆ์ฐจ์์ด๋ผ๋ฉด ์ด์ํ ๋ ์ซ์ ์ค ๋ ํฐ ์ซ์๊ฐ ๋ท ์๋ฆฌ๋ก ์ด๋ํ๋๋ก ์๋ก ๋ฐ๊ฟ์ค๋ค๋ ๊ฒ์ด๋ค. ๋ฒ๋ธ ์ ๋ ฌ์ด๋ผ๋ ์ด๋ฆ์ด ๋ถ์ ์ด์ ๋ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ๊ฒ์ด ์๋ก ์ฌ๋ผ๊ฐ๋ ๊ฑฐํ์ ์์ง์์ ๋น๋์ด ๋ถ์ฌ์ง ์ด๋ฆ์ด๋ผ ํ๋ค. (๊ทธ๋ ๊ฒ ๊ณต๊ฐ์ด ๊ฐ์ง ์๋๋ค) ์ ๊ทธ๋ฆผ์ ๋ฒ๋ธ ์ ๋ ฌ์ switching ํ๋ ๊ณผ์ ์ ๋ณด์ฌ์ฃผ๋ ๊ทธ๋ฆผ์ด๋ค. ์ฐ์๋ ๋ ์ด์์ ๊ฐ์ ๋น๊ตํด ๋ ๋์ ๊ฐ์ ๋ท์๋ฆฌ๋ก ์ค์์นญํ๊ฒ ๋๋ค. ํน์ง์, ํ loop๊ฐ ๋ ๋๋ง๋ค, ์ ์ผ ๋ง์ง๋ง ์๋ฆฌ์ ์ซ์๊ฐ ๊ฒฐ์ ๋๋ค๋ ๊ฒ์ด๋ค. ๋ค์ loop๋ n-1๋ฒ์งธ ์๋ฆฌ์ ์ซ์๊ฐ, ๊ทธ ๋ค์์ n-2๋ฒ์งธ ์๋ฆฌ์ ์ซ์๊ฐ ๊ฒฐ์ ๋๋ค๋ ํน์ง์ ์..