์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- DP
- Python
- ์ด๋ถํ์
- ๋ฐฑํธ๋ํน
- Java
- bfs
- heapq
- ๊ตฌํ
- ์ฌ๊ท
- ์๊ณ ๋ฆฌ์ฆ
- 3์ฐจ์๋ฐฐ์ด
- ๋ฌธ์์ด
- ์ ๋ ฌ
- ํ๋ก์ด๋์์ฌ
- ๋ค์ต์คํธ๋ผ
- Deque
- ๋ถํ ์ ๋ณต
- ํ์ด์ฌ
- ์๋ฎฌ๋ ์ด์
- dfs
- ์๋๋ก์ด๋
- ๋ฐฐ๋ญ๋ฌธ์
- HashMap
- BOJ
- ์กฐํฉ
- ๋นํธ๋ง์คํน
- ํ๋ก๊ทธ๋๋จธ์ค
- ๋ธ๋ฃจํธํฌ์ค
- SQL
- ๋ถ๋ถ์งํฉ
- Today
- Total
๋ชฉ๋กheapq (2)
It's easy, if you try
๋ฌธ์ ๋งค์ด ๊ฒ์ ์ข์ํ๋ Leo๋ ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K ์ด์์ผ๋ก ๋ง๋ค๊ณ ์ถ์ต๋๋ค. ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K ์ด์์ผ๋ก ๋ง๋ค๊ธฐ ์ํด Leo๋ ์ค์ฝ๋น ์ง์๊ฐ ๊ฐ์ฅ ๋ฎ์ ๋ ๊ฐ์ ์์์ ์๋์ ๊ฐ์ด ํน๋ณํ ๋ฐฉ๋ฒ์ผ๋ก ์์ด ์๋ก์ด ์์์ ๋ง๋ญ๋๋ค. ์์ ์์์ ์ค์ฝ๋น ์ง์ = ๊ฐ์ฅ ๋งต์ง ์์ ์์์ ์ค์ฝ๋น ์ง์ + (๋ ๋ฒ์งธ๋ก ๋งต์ง ์์ ์์์ ์ค์ฝ๋น ์ง์ * 2) Leo๋ ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๊ฐ K ์ด์์ด ๋ ๋๊น์ง ๋ฐ๋ณตํ์ฌ ์์ต๋๋ค. Leo๊ฐ ๊ฐ์ง ์์์ ์ค์ฝ๋น ์ง์๋ฅผ ๋ด์ ๋ฐฐ์ด scoville๊ณผ ์ํ๋ ์ค์ฝ๋น ์ง์ K๊ฐ ์ฃผ์ด์ง ๋, ๋ชจ๋ ์์์ ์ค์ฝ๋น ์ง์๋ฅผ K ์ด์์ผ๋ก ๋ง๋ค๊ธฐ ์ํด ์์ด์ผ ํ๋ ์ต์ ํ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ ์ฌํญ scoville์..
heapq ๋ชจ๋์ ๋ํด ๊ฐ๋ตํ ์์๋ณด์ ! Heap ์ด๋ ? ํ(heap)์ ์ต๋๊ฐ ๋ฐ ์ต์๊ฐ์ ์ฐพ์๋ด๋ ์ฐ์ฐ์ ๋น ๋ฅด๊ฒ ํ๊ธฐ ์ํด ๊ณ ์๋ ์์ ์ด์งํธ๋ฆฌ(complete binary tree)๋ฅผ ๊ธฐ๋ณธ์ผ๋ก ํ ์๋ฃ๊ตฌ์กฐ(tree-based structure)๋ก์ ๋ค์๊ณผ ๊ฐ์ ํ ์์ฑ(property)์ ๋ง์กฑํ๋ค. A๊ฐ B์ ๋ถ๋ชจ๋ ธ๋(parent node)์ด๋ฉด, A์ ํค(key)๊ฐ๊ณผ B์ ํค๊ฐ ์ฌ์ด์๋ ๋์๊ด๊ณ๊ฐ ์ฑ๋ฆฝํ๋ค. ํ์๋ ๋๊ฐ์ง ์ข ๋ฅ๊ฐ ์์ผ๋ฉฐ, ๋ถ๋ชจ๋ ธ๋์ ํค๊ฐ์ด ์์๋ ธ๋์ ํค๊ฐ๋ณด๋ค ํญ์ ํฐ ํ์ '์ต๋ ํ', ๋ถ๋ชจ๋ ธ๋์ ํค๊ฐ์ด ์์๋ ธ๋์ ํค๊ฐ๋ณด๋ค ํญ์ ์์ ํ์ '์ต์ ํ'์ด๋ผ๊ณ ๋ถ๋ฅธ๋ค. ์๋ ์ฌ์ง์ ์ต๋ ํ์ ์์์ด๋ค. ์ถ์ฒ : ์ํค๋ฐฑ๊ณผ 'ํ (์๋ฃ ๊ตฌ์กฐ)' heapq ์์ ์ด์งํธ๋ฆฌ ๊ธฐ๋ฐ์ ์ต์ ํ ์..