deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim
Programming language/Python

[python] heapq(ํž™ํ, ์šฐ์„ ์ˆœ์œ„ํ)

[python] heapq(ํž™ํ, ์šฐ์„ ์ˆœ์œ„ํ)
Programming language/Python

[python] heapq(ํž™ํ, ์šฐ์„ ์ˆœ์œ„ํ)

2020. 8. 26. 20:26
๋ฐ˜์‘ํ˜•

๐Ÿ“—heapq๋ž€?

๊ฐ„๋‹จํ•˜๊ฒŒ ๋ฆฌ์ŠคํŠธ๋‚ด์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์ด ๋งจ์ฒ˜์Œ์œ„์น˜(์ธ๋ฑ์Šค 0)์•  ์˜ค๊ฒŒ ํ•ด์ฃผ๋Š” ๋‚ด์žฅ ๋ชจ๋“ˆ

์šฐ์„ ์ˆœ์œ„ ํ๋ผ๊ณ  ์•Œ๋ฉด ์‰ฝ๋‹ค.

 

๐Ÿ”ต ์‹œ์ž‘ํ•˜๊ธฐ

import heapq

 

๐Ÿ”ต ์„ ์–ธํ•˜๊ธฐ

๋ณดํ†ต ๋ฆฌ์ŠคํŠธ๋ฅผ ์„ ์–ธํ•˜๋Š” ๊ฒƒ์ฒ˜๋Ÿผ ๋งŒ๋“ ๋‹ค.

heap_list = []

 

๐Ÿ”ต ์›์†Œ ์ถ”๊ฐ€ํ•˜๊ธฐ ( heapq.heappush(๋ฆฌ์ŠคํŠธ, ๊ฐ’ ))

- ์•„๋ž˜ ๋ณด์ด๋Š” ๊ฒƒ ์ฒ˜๋Ÿผ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์ด ๋งจ ์ฒ˜์Œ ์œ„์น˜์— ์™”๋‹ค.

์‹œ๊ฐ„๋ณต์žก๋„ O(logn)

heapq.heappush(heap_list, 5)
heapq.heappush(heap_list, 10)
heapq.heappush(heap_list, 99)
heapq.heappush(heap_list, 2)

print(heap_list) # [2, 5, 99, 10]

 

๐Ÿ”ต ์›์†Œ ์‚ญ์ œํ•˜๊ธฐ ( heapq.heappop(๋ฆฌ์ŠคํŠธ) )

- ์ œ์ผ ์ฒ˜์Œ์— ์žˆ๋Š” ๊ฐ’์ด ์‚ญ์ œ๋˜๋ฉด์„œ ๊ทธ ๊ฐ’์„ ๋ฆฌํ„ดํ•œ๋‹ค. ๊ฐ’์„ ์‚ญ์ œํ•˜๊ณ  ๋‹ค์‹œ ์ถœ๋ ฅํ•ด๋ณด๋‹ˆ ํž™์ด ์ •๋ ฌ ๋˜์–ด ์žˆ๋‹ค. 

์‹œ๊ฐ„๋ณต์žก๋„ O(logn)

print(heapq.heappop(heap_list))  # [2, 5, 99, 10]
print(heap_list)  # [5, 10, 99] 
a = heapq.heappop(heap_list)
print(a)  # 5

 

๐Ÿ”ต ๊ธฐ์กด์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ํž™์œผ๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ ( heapq.heapify(๋ฆฌ์ŠคํŠธ) )

์‹œ๊ฐ„๋ณต์žก๋„ O(n)

ano_list = [9, 8, 7, 6, 5, 4, 1, 2, 5]
heapq.heapify(ano_list)
print(ano_list)  # [1, 2, 4, 5, 5, 9, 7, 6, 8]

 

๐Ÿ”ต ์ตœ๋Œ€๊ฐ’ ๊ตฌํ•˜๊ธฐ! (์‘์šฉ)

- ๊ฐ’๋“ค์„ ํŠœํ”Œ ํ˜•ํƒœ๋กœ ๋„ฃ์–ด์ค€๋‹ค. ํŠœํ”Œํ˜•ํƒœ๋กœ ๋„ฃ์–ด์ฃผ๋ฉด ํŠœํ”Œ์˜ 0๋ฒˆ์งธ ์ธ๋ฑ์Šค๋ฅผ ๊ธฐ์ค€์œผ๋กœ ํž™์ •๋ ฌ์ด ๋œ๋‹ค.

numbers = [1,5,9,3,7,6,4,2,8]
max_list = []
for number in numbers:
    heapq.heappush(max_list, (-number, number)) # ( ์šฐ์„ ์ˆœ์œ„, -๋ฅผ ๋ถ™์ด๋ฉด ๊ฐ€์žฅ ํฐ ๊ฐ’์ด ๊ฐ€์žฅ ์ž‘์•„์ง„๋‹ค. ์‹ค์ œ ๊ฐ’)

while max_list:
    print(heapq.heappop(max_list)[1])
๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Programming language > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[python] filter  (2) 2020.08.31
[python] accumulate(itertools), ๋ˆ„์  ํ•ฉ  (0) 2020.08.30
[python] defaultdict  (0) 2020.08.29
[python] pow, ์ œ๊ณฑ, ๊ฑฐ๋“ญ์ œ๊ณฑ๊ณผ ๋‚˜๋จธ์ง€  (0) 2020.08.28
[python] input, sys.stdin.readline  (0) 2020.08.27
  • ๐Ÿ“—heapq๋ž€?
  • ๐Ÿ”ต ์‹œ์ž‘ํ•˜๊ธฐ
  • ๐Ÿ”ต ์„ ์–ธํ•˜๊ธฐ
  • ๐Ÿ”ต ์›์†Œ ์ถ”๊ฐ€ํ•˜๊ธฐ ( heapq.heappush(๋ฆฌ์ŠคํŠธ, ๊ฐ’ ))
  • ๐Ÿ”ต ์›์†Œ ์‚ญ์ œํ•˜๊ธฐ ( heapq.heappop(๋ฆฌ์ŠคํŠธ) )
  • ๐Ÿ”ต ๊ธฐ์กด์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ํž™์œผ๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ ( heapq.heapify(๋ฆฌ์ŠคํŠธ) )
  • ๐Ÿ”ต ์ตœ๋Œ€๊ฐ’ ๊ตฌํ•˜๊ธฐ! (์‘์šฉ)
'Programming language/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [python] accumulate(itertools), ๋ˆ„์  ํ•ฉ
  • [python] defaultdict
  • [python] pow, ์ œ๊ณฑ, ๊ฑฐ๋“ญ์ œ๊ณฑ๊ณผ ๋‚˜๋จธ์ง€
  • [python] input, sys.stdin.readline
deo2kim
deo2kim
์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.