λͺ¨λ
: ν¨μ,λ³μ λλ ν΄λμ€λ€μ λͺ¨μλμ νμΌ - νμΌλͺ μ΄ λͺ¨λλͺ μ΄ λλ€.
if __name__ == "__main__" μ μλ―Έ
π pythonμ cλ javaμ λ€λ₯΄κ² μ€ν¬λ¦½νΈ κΈ°λ° μΈν°νλ¦¬ν° μΈμ΄λ‘ νΉλ³ν μμ μ§μ μ΄ λͺ μκ° λμ΄μμ§ μμ μΈμ΄μ΄λ€.
κ·Έλμ νΉλ³ν λ³μλ₯Ό ν λΉνμ¬ νμ¬ μ€νΈλ¦½νΈμ μμμ μ΄ μ΄λμΈμ§ νλ¨νλλ° κ·Έ λ³μλ‘μ μ΄μ©νλ κ²μ΄ __name__ μ΄λ€.
νμΌ μ€νμμλ __name__ λ³μμ "__main__"μ μ μ₯νκ² λμ§λ§ ν΄λΉ λͺ¨λμ΄ import λ κ²½μ° λ³μμ "λͺ¨λλͺ "μ΄ λ€μ΄κ°κΈ°λλ¬Έμ
if __name__ == "__main__" λ¬Έμ μ€νλμ§μλλ€.
__init__μ μλ―Έ
π μμ±μμ μλ―Έ ( μ¬κΈ°μ selfλ μΈμ€ν΄μ€ μμ , λ©μλμ μμμ μΈμ μ λμ μλ―Έλ₯Ό κ°μ§λ€. )
classμ μΈμ€ν΄μ€λ₯Ό μμ±ν λ μ΄κΈ°νλ₯Ό μν ν¨μ. μΈμ€ν΄μ€νλ₯Ό μ€μν λ λ°λμ μ²μμ νΈμΆλλ νΉμν ν¨μμ΄λ€.
class test:
def __init__(self,x) :
self.x = x
def test_function(self) : #λ©μλ
perint(self.x)
ADT μΆμμ μλ£ν
: 물리μ μΌλ‘ μ‘΄μ¬νλ κ²μ΄ μλλΌ μΌμ’ μ κ·μΉ, λ°°μ΄μμ μ΄λ€ κ·μΉμ μ€μ ν μ§ μ νλ κ²
- μ€ν stack : μ μ νμΆ
- ν queque : μ μ μ μΆ
μ€ν
- νμ΄μ¬μ λ°λ‘ μ€ν λͺ¨λμ΄ μ‘΄μ¬νμ§μλλ€. λ³΄ν΅ λ±(deque) λΌμ΄λΈλ¬λ¦¬λ₯Ό importν΄μ μ€ν λμ μ¬μ©κ°λ₯νλ€.
- 리μ€νΈ ν¨μλ₯Ό μ¬μ©ν΄μ κ°λ¨νκ² μ€νμ μ¬μ©ν μμλ€.
ν
ν λμ
enqueue / dequeue
ν 리μ€νΈ ꡬννκΈ°
- 리μ€νΈλ₯Ό ν λ°©μμΌλ‘ ꡬννλ©΄ headλ³μμ tail λ³μμ indexμ 보λ₯Ό λ΄λλ€.
- λ°μ΄ν°λ₯Ό μΆμΆνλ©΄(dequeue) λ°μ΄ν°κ° λΉκ²¨μ§λ κ²μ΄ μλλΌ head λ³μκ° λ€λ‘ λμ΄κ°λ€.
- μΆκ°μ μΆμΆμ λ°λ³΅νλ€ λ³΄λ©΄ headμ tailμ΄ λ€λ‘ λ°λ € 리μ€νΈκ° κ°λ μ°¨ μμͺ½μ λΉκ³΅κ°(μ°λ κΈ° κ°)μ΄ λ§μλ°λ λ μ΄μ λ°μ΄ν°λ₯Ό λ£μ μ μκ² λλ€.
- κ·Έκ²μ λ°©μ§νκΈ° μν΄ μν 리μ€νΈλ₯Ό μ΄μ©νλ€.
- 물리μ μ΄ μλ κ΄λ μ μν listμ΄λ©° 리μ€νΈ indexκ° λ§μ§λ§ indexμ 1μ΄ λν΄μ§λ©΄ λ€μ 0λ²μ§λ‘ λμμ€λλ‘ μ μ νλ€. - μ μ μ€λ₯Έμͺ½μΌλ‘ μ΄λνλ©° νμ₯ (dequeμ .rotate()ν¨μ μ¬μ© κ°λ₯)
μν νλ μκ³ λ¦¬μ¦ λΏ μλλΌ μ€λ¬΄μμ λ§μ΄ μ¬μ©λλ λ°μ΄ν° ꡬ쑰μ΄λ€.
μν νμ νΉμ§μ λ§₯μλ© μ¬μ΄μ¦κ° μκΈ° λλ¬Έμ μ€λ²νλ‘μ΄κ° μκΈΈ μ μλ€.
β λ± (double ended queue) λͺ¨λ
μμͺ½ λμμ μ½μ κ³Ό μμ κ° κ°λ₯νλ€.
μμΉμ μΌλ‘λ μ μΌ μ/λ€κ° μλ λλ¨Έμ§ μμλ€μ νμΈ, λ³κ²½μ΄ λΆκ°λ₯νλ° λ±μμλ indexμ κ·Όμ΄ κ°λ₯νλ€.
μμͺ½μΌλ‘ νμ₯μ΄ κ°λ₯νκΈ° λλ¬Έμ ꡬνμ μμ μ§μ μ μ€κ°μ λμ΄μΌνλ€.
popleft() - 첫λ²μ§Έ λ°μ΄ν°λ₯Ό μ κ±°
eppendleft() - λ°μ΄ν°λ₯Ό 맨 μμ μ½μ
- ν (Queue) λͺ¨λ
λ±λ³΄λ€ λλ¦Ό, μΈλ±μ€ κ°μΌλ‘ κ°μ μμμλ€.
: μ£Όλ‘ λ©ν° μ°λ λ© νκ²½μμ μ¬μ©λλ©°, λ΄λΆμ μΌλ‘ λΌνΉ(locking)μ μ§μνμ¬ μ¬λ¬ κ°μ μ°λ λκ° λμμ λ°μ΄ν°λ₯Ό μΆκ°νκ±°λ μμ ν μ μλ€.
λ±κ³Ό λ¬λ¦¬ λ°©ν₯μ±μ΄ μκΈ° λλ¬Έμ λ°μ΄ν°λ₯Ό μΆκ°μ μμ κ° νλμ λ©μλλ‘ μ²λ¦¬λ¨.
put(x) - λ°μ΄ν° μΆκ°
get( ) - λ°μ΄ν° μμ
μ°μ μμ ν
: popν λ κ°μ₯ λ¨Όμ λ€μ΄μ¨ μμ λμ μ°μ μμκ° κ°μ₯ λμ μμκ° λμ€λ ν κΈ°λ₯ - ν ꡬ쑰λ₯Ό μ΄μ©ν΄ λΉ λ₯΄κ² μ°μ°μ΄ κ°λ₯νλ€.
- μμμΆκ° O(logN)
- μ°μ μμκ° κ°μ₯ λμ μμμ νμΈ O(1)
- μ°μ μμκ° κ°μ₯ λμ μμμ μ κ±° O(logN)
ν
μ΄μ§ νΈλ¦¬ - μ΄μ§κ²μνΈλ¦¬(BST)μ λ¬λ¦¬ λ κ· νμ΄ μ λ§λ μ΄μ§νΈλ¦¬
μ΅μν / μ΅λν
- μ½μ : μλ μμλλ‘ μ½μ (맨μ-μ€λ₯Έμͺ½-μΌμͺ½)νμ 쑰건μ μλ°°λλ€λ©΄ μλ°°λμ§μμλκΉμ§ μ리 λ³κ²½
- μΆμΆ : 루νΈμ λ€μ΄μλ κ°μ΄ μ΅μ/μ΅λκ° - μ΅μνμμλ μ΅μκ°, μ΅λνμμλ μ΅λκ°μ μ°Ύμ μμκ³ λ€λ₯Έ κ°μ μ°Ύλ κ²μ νΈλ¦¬λ₯Ό μ λΆ λ€μ§λκ² μλ μ΄μ νμΈμ΄ λΆκ°λ₯νλ€.
- μμ : 루νΈκ°μ μμ ν λ νΈλ¦¬ κ΅¬μ‘°κ° κΉ¨μ§μ§μκ² κ°μ₯ λ§μ§λ§ μ리μ(μμμ΄ μλ)μ 루νΈκ°μ λ°κΎΌν μμ νλ€. κ·Έ ν μ½μ μμμ λμΌνκ² νΈλ¦¬κ΅¬μ‘°κ° μλ°°λμ§μκ² λ΄λΆμ μΌλ‘ μ리λ₯Ό λ³κ²½ν΄μ€λ€.
xλ²μ§μ μΌμͺ½ μμ index : 2x
xλ²μ§μ μ€λ₯Έμͺ½ μμ index : 2x + 1
xλ²μ§μ λΆλͺ¨ index : x/2
μ΄μ§κ²μνΈλ¦¬λ μ νμ²λΌ λ°°μ΄λ‘ λνλΌ μ μλ μ§ μκ°ν΄λ³΄κΈ°
β ν (heapq) λͺ¨λ
heapq.heappush(heap, item) : itemμ heap list μ μΆκ°
heapq.heappop(heap) : heap list μμ κ°μ₯ μμ μμλ₯Ό pop. λΉμ΄ μλ κ²½μ° IndexErrorκ° νΈμΆλ¨.
heapq.heapify(x) : 리μ€νΈ xλ₯Ό μ¦κ°μ μΌλ‘ heapμΌλ‘ λ³νν¨ O(N)
- λ±(queue) λͺ¨λ PriorityQueue ν΄λμ€
λ΄λΆμ μΌλ‘ heapλͺ¨λμ μ¬μ©νλ€.
μμ±μ
que = PriorityQueue()
que = PriorityQueue(maxsize=8) : μ΅λν¬κΈ° μ§μ μμ μ
μ΄μ½ π₯π₯
'SWμ¬κ΄νκ΅ μ κΈ > κ°λ°μΌμ§ - TIL' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Week03] μκ³ λ¦¬μ¦ - DFS / BFS λ°±μ€ λ¬Έμ (5) | 2022.04.21 |
---|---|
[Week03] μκ³ λ¦¬μ¦ - μ λμ¨ νμΈλ (3) | 2022.04.20 |
[Week02] μκ³ λ¦¬μ¦ - μ΄λΆνμ (5) | 2022.04.09 |
[Week01] μκ³ λ¦¬μ¦ - μ λ ¬01 (0) | 2022.04.09 |
[Week01] μκ³ λ¦¬μ¦ - μ¬κ·ν¨μ (0) | 2022.04.07 |
λκΈ