π μλ£κ΅¬μ‘°

λ°°μ΄(Array) VS λ°°μ΄ λ¦¬μ€νΈ(ArrayList) VS μ°κ²° 리μ€νΈ(LinkedList)
π 1. λ°°μ΄ π 1. κ°λ λ° νΉμ§ λ°°μ΄(Array)μ΄λ κ°μ νμ μ μ¬λ¬ λ³μλ₯Ό νλμ λ¬ΆμμΌλ‘ λ€λ£¨λ κ²μ λ§νλ€. λ°°μ΄μ ꡬμ±νλ κ°κ°μ κ°μ λ°°μ΄ μμ(Element), λ°°μ΄μμμ μμΉλ₯Ό κ°λ¦¬ν€λ μ«μλ₯Ό μΈλ±μ€(Index)λΌκ³ νλ€. λ°°μ΄μ μ°Έμ‘° κ°μ²΄μ΄λ―λ‘ λ°°μ΄μ κ°λ¦¬ν€λ μ°Έμ‘° λ³μλ μ€ν μμμ ν λΉλλ©°, μ΄ μ°Έμ‘° λ³μκ° κ°λ¦¬ν€κ³ μλ μ£Όμκ°μ μ€μ ν μμμ μμ±λλ λ°°μ΄μ μ£Όμκ°μ΄λ€. λ°°μ΄μ ν¬κΈ°λ κ³ μ μ μ΄λ€. λ©λͺ¨λ¦¬ 곡κ°μ΄ μ°μμ μΌλ‘ ꡬμ±λλ€. π 2. μ₯μ μΈλ±μ€λ₯Ό νμ©ν μ μκΈ° λλ¬Έμ, νΉμ μμΉμ μλ μμμ λν μ κ·Όμ μκ°λ³΅μ‘λκ° O(1)μ΄λ€. μΈλ±μ€λ₯Ό νμ©ν μ μκΈ° λλ¬Έμ, νΉμ μμΉμ μλ μμμ λν μμ μ μκ°λ³΅μ‘λκ° O(1)μ΄λ€. π 3. λ¨μ ν¬κΈ°κ° κ³ μ μ μ΄κΈ° λλ¬Έ..

λ°°μ΄(Array)
π 1. λ°°μ΄μ΄λ? λ°°μ΄(Array)μ΄λ κ°μ νμ μ μ¬λ¬ λ³μλ₯Ό νλμ λ¬ΆμμΌλ‘ λ€λ£¨λ κ²μ λ§νλ€. λ°°μ΄μ ꡬμ±νλ κ°κ°μ κ°μ λ°°μ΄ μμ(Element)λΌκ³ νλ©°, λ°°μ΄μμμ μμΉλ₯Ό κ°λ¦¬ν€λ μ«μλ₯Ό μΈλ±μ€(Index)λΌκ³ νλ€. π 2. λ°°μ΄ μ μΈ & μμ± & μ΄κΈ°ν π 1. λ°°μ΄ μ μΈ λ°°μ΄μ μ μΈνλ λ°©λ²μ μνλ νμ μ λ³μλ₯Ό μ μΈνκ³ λ³μ λλ νμ μ λ°°μ΄μμ μλ―Ένλ λκ΄νΈλ₯Ό λΆμ΄λ©΄ λλ€. public static void main(String[] args) { int[] numbers; String[] names; } π 2. λ°°μ΄ μμ± λ°°μ΄μ μ μΈν λ€μμλ λ°°μ΄μ μμ±ν΄μΌ νλ€. λ°°μ΄μ μ μΈνλ κ²μ λ¨μ§ μμ±λ λ°°μ΄μ λ€λ£¨κΈ° μν μ°Έμ‘°λ³μλ₯Ό μν 곡κ°μ΄ λ§λ€μ΄μ§ λΏμ΄κ³ , λ°°μ΄μ μμ±ν΄..

μΈκ·Έλ¨ΌνΈ νΈλ¦¬(Segment Tree)
1. κ°λ π« μΈκ·Έλ¨ΌνΈ νΈλ¦¬(Segment Tree)λ μ¬λ¬ κ°μ λ°μ΄ν°κ° μ‘΄μ¬ν λ νΉμ ꡬκ°μ ν©μ ꡬνλ λ° μ¬μ©νλ μλ£κ΅¬μ‘°μ΄λ€. νΈλ¦¬ μ’ λ₯ μ€ νλλ‘ μ΄μ§νΈλ¦¬μ ννμ΄λ©°, νΉμ ꡬκ°μ ν©μ κ°μ₯ λΉ λ₯΄κ² ꡬν μ μλ€λ μ₯μ μ΄ μλ€. O(log N) 2. λμλ°©μ π μΈκ·Έλ¨ΌνΈ νΈλ¦¬λ₯Ό μ΄μ©νκΈ° μν΄μλ μ°μ 'κ΅¬κ° ν© νΈλ¦¬'λ₯Ό μμ±ν΄μΌ νλ€. κ·Έλ¦¬κ³ 'κ΅¬κ° ν©μ ꡬνλ ν¨μ'μ 'μμλ₯Ό μμ νλ ν¨μ'λ₯Ό μ΄μ©νμ¬ κ΅¬κ° ν©μ ꡬνκ³ νΉμ μμλ₯Ό μμ ν μ μλ€. '1 9 3 8 4 5 5 9 10 3 4 5'λΌλ 12κ°μ μμλ₯Ό κ°μ§ λ°°μ΄μ΄ μ£Όμ΄μ‘μ λ μΈκ·Έλ¨ΌνΈ νΈλ¦¬λ₯Ό μ΄μ©νμ¬ κ΅¬κ° ν©μ ꡬν΄λ³΄μ. 1. κ΅¬κ° ν© νΈλ¦¬ μμ±νκΈ° 'ꡬκ°'μ μλ λ°μ΄ν° λ²μλ₯Ό λ°μ© λΆν νλ κ²μΌλ‘ μ€μ νλ€. μ΅μλ¨ λ Έλ..

μΉ΄μ΄ν μ λ ¬ (Counting Sort)
1. κ°λ π 'κ³μ μ λ ¬'μ΄λΌκ³ λ λΆλ¦¬λ 'μΉ΄μ΄ν μ λ ¬(Counting Sort)'μ κ° μμλ€μ΄ λͺ κ°μ© μλμ§ λνλ΄λ countλ°°μ΄μ νμ©νλ μ λ ¬ μκ³ λ¦¬μ¦μ΄λ€. κ° μμμ κ°μ΄ count λ°°μ΄μ μΈλ±μ€κ° λλ―λ‘ 'μ μλ μ μλ‘ ννν μ μλ μλ£'μ λν΄μλ§ μ μ© κ°λ₯νλ€. 2. λμλ°©μ π λμ λ°©μμ λ€μκ³Ό κ°λ€. μμμ μ΅λκ°μ ν¬ν¨ν μ μλ λ°°μ΄ μ€μ κ°κ°μ μμκ° λͺ λ² λ±μ₯νλμ§ μΉ΄μ΄ν count λ°°μ΄μ μΈλ±μ€ = μμ κ° count λ°°μ΄μ κ° = λ±μ₯ νμ count λ°°μ΄μ λμ ν©μΌλ‘ λ§λ€μ΄μ£ΌκΈ° μ λ ¬λμ§ μμ λ°°μ΄(μ΄κΈ°κ°)μ λ€μμλΆν° λλ©΄μ, μμμ κ°κ³Ό λμΌν μΈλ±μ€κ° κ°λ¦¬ν€λ κ³³μ μμ λ°°μΉν΄ μ£ΌκΈ° '0 2 1 1 4 4 4 3 5'κ° μ£Όμ΄μ‘μ λ λμλ°©μμ μλμ κ·Έλ¦Όμ ..

ν΅ μ λ ¬ (Quick Sort)
1. μ μ π¨π ν΅ μ λ ¬(Quick Sort)μ λΆν μ 볡 λ°©λ²μ μ΄μ©νλ μ λ ¬ μκ³ λ¦¬μ¦μ΄λ€. ν΅ μ λ ¬μ νΌλ²(Pivot)μ κΈ°μ€μΌλ‘ λΆν κ³Ό μ λ³΅μ΄ μ΄λ£¨μ΄μ§κ² λλ€. ν΅ μ λ ¬μ 'νΌλ²μ μ ννλ λ°©μ'κ³Ό 'μ¬κ· λλ λΉμ¬κ· λ°©μ'μ μ νμ λ°λΌ λ€μν ꡬν λ°©λ²μ΄ μ‘΄μ¬νλ€. μ΄λ² κΈμμλ 'μΌμͺ½ νΌλ²μ μ ννλ λ°©μ'κ³Ό 'μ¬κ· λ°©μ'μ ν΅ν ν΅ μ λ ¬μ μμ보λλ‘ νμ. 2. λμ λ°©μ π¦ΈβοΈ κΈ°λ³Έμ μΈ λμ λ°©μμ μλμ κ°λ€. λ°°μ΄μμ μμμ μμμΈ pivotμ μ ννλ€. (ν΄λΉ κΈμμλ λ°°μ΄μμ μ μΌ μΌμͺ½ μμλ₯Ό pivotμΌλ‘ μ ννλ€.) pivotμ κΈ°μ€μΌλ‘ pivotλ³΄λ€ μμ μμλ μΌμͺ½μΌλ‘, pivotλ³΄λ€ ν° μμλ μ€λ₯Έμͺ½μ μ€λλ‘ λ°°μ΄μ λ°°μΉνλ€. pivotμ κΈ°μ€μΌλ‘ λλμ΄μ§ μΌμͺ½ λ°°μ΄κ³Ό ..

ν μ λ ¬ (Heap Sort)
1. μ μ πβοΈ νμ λ ¬μ΄λ μλ£κ΅¬μ‘° ν(Heap)μ κΈ°λ°μΌλ‘ νλ μ λ ¬ λ°©μμ΄λ€. μ€λ¦μ°¨μ μ λ ¬μΌ κ²½μ° μ΅λνμ μ΄μ©νκ³ λ΄λ¦Όμ°¨μ μ λ ¬μΌ κ²½μ° μ΅μνμ μ΄μ©νλ€. κ°λ¨νκ² μ€λͺ νμλ©΄ ν μ λ ¬μ 루νΈλ Έλλ₯Ό μ κ±°νκ³ μ κ±°λ λ£¨νΈ λ Έλλ₯Ό λ°°μ΄μ λ·λΆλΆλΆν° μ±μ λ£μΌλ©΄μ μ λ ¬μ΄ μ΄λ£¨μ΄μ§λ κ²μ΄λ€. 2. λμ λ°©μ π£βοΈ μ΅λνμ μ΄μ©νμ¬ μ€λ¦μ°¨μμΌλ‘ μ λ ¬νλ κ²½μ°λ₯Ό μκ°ν΄ 보μ. κ°μ₯ μ½κ² μκ°ν μ μλ λμλ°©μμ μλμ κ°λ€. μ λ ¬ν΄μΌ νλ μμλ€μ νλμ© νμ λ£μ΄μ€λ€. μμ λ₯Ό νλ©΄μ λ£¨νΈ λ Έλλ₯Ό κ°μ Έμ€κ³ κ·Έκ²μ λ°°μ΄μ λ·λΆλΆλΆν° μ±μ΄λ€. μ΄λ κ² νλ€λ©΄ κΈ°μ‘΄ λ°°μ΄λ‘λΆν° νμ ꡬμ±νλ λ°°μ΄ νλλ₯Ό μΆκ°μ μΌλ‘ λ§λ€κ³ (1λ² κ³Όμ ), λ·λΆλΆλΆν° μ λ ¬λ μμλ€μ λ£μ λ°°μ΄μ νλ λ λ§λ€μ΄μΌ νλ€.(2λ² κ³Όμ ..

[μλ£κ΅¬μ‘°] ν(Heap)
1. μ μ π³ ν(Heap)μ΄λ μ¬λ¬ κ°λ€ μ€ μ΅λκ° νΉμ μ΅μκ°μ λΉ λ₯΄κ² μ°Ύμλ΄κΈ° μν μλ£κ΅¬μ‘°μ΄λ€. νμ νΉμ§ μμ μ΄μ§νΈλ¦¬μ μΌμ’ μ΄λ€. λ°μ λ ¬ μνμ΄λ€. μ΅λν(Max Heap) λλ μ΅μν(Min Heap)μ λ°λΌμ λ£¨νΈ λ Έλκ° νμ κ°μ₯ ν° κ°μ΄κ±°λ κ°μ₯ μμ κ°μ μ μ§νκΈ° λλ¬Έμ΄λ€. μ€λ³΅λ κ°μ νμ©νλ€. νμ μ’ λ₯ μ΅λ ν (Max Heap) λΆλͺ¨ λ Έλμ ν€ κ°μ΄ μμ λ Έλμ ν€ κ°λ³΄λ€ ν¬κ±°λ κ°μ μμ μ΄μ§νΈλ¦¬ νμ μ΅μ ν (Min Heap) λΆλͺ¨ λ Έλμ ν€ κ°μ΄ μμ λ Έλμ ν€ κ°λ³΄λ€ μκ±°λ κ°μ μμ μ΄μ§νΈλ¦¬ νμ 2. λμ λ°©μ π μΈλ±μ€ 0 1 2 3 4 5 6 7 8 κ° - 9 7 6 4 5 1 3 8 Heapμ λ°°μ΄μ ν΅ν΄ μ½κ² ꡬνμ΄ κ°λ₯νλ€. κ·Έ μ΄μ λ νμ΄ μμ μ΄μ§νΈλ¦¬μ΄..

μμ μ λ ¬(Topology Sort)
1. μ μ π§ μμ μ λ ¬(Topology Sort)μ΄λ μμκ° μ ν΄μ Έ μλ μμ μ μ°¨λ‘λλ‘ μνν λ κ·Έ μμλ₯Ό κ²°μ ν΄ μ£Όλ μκ³ λ¦¬μ¦μ΄λ€. κ΅μ‘κ³Όμ μ μ μκ³Όλͺ©μ΄ μμ μ λ ¬μ μ€λͺ νλ κ°μ₯ μ μ ν μμμ΄λ€. μ»΄ν¨ν° 곡νμ μ 곡νκ³ μλ νμμ λ€μ μ 곡과λͺ©(ex. μκ³ λ¦¬μ¦)μ λ£κΈ° μν΄μλ μ μ κ³Όλͺ©(ex. μλ£κ΅¬μ‘°)μ νμμ μΌλ‘ λ€μ΄μΌ νλ€. κΈ°μ΄μ»΄ν¨ν°νλ‘κ·Έλλ° → μλ£κ΅¬μ‘° → μκ³ λ¦¬μ¦ μλ£κ΅¬μ‘° → λ Όλ¦¬νλ‘λ°μ€κ³ → λ Όλ¦¬νλ‘μ€ν μκ³ λ¦¬μ¦ → λ Όλ¦¬νλ‘λ°μ€κ³ → λ Όλ¦¬νλ‘μ€ν λν, μμμ λ ¬μ μμ κ°μ΄ μ¬λ¬ κ°μ κ²½λ‘κ° μ‘΄μ¬ν μ μλ€. λ§μ§λ§ νΉμ§μΌλ‘λ μμ μ λ ¬μ λΉμν μ ν₯ κ·Έλν(DAG - Directed Acyclic Graph)μλ§ μ μ©μ΄ κ°λ₯νλ€. μ¦, μ¬μ΄ν΄μ΄ λ°μνμ§ μλ λ°©ν₯ κ·Έλνμ¬μΌ ν..

λ³ν© μ λ ¬(Merge Sort)
ν©λ³μ λ ¬μ΄λΌκ³ λ λΆλ¦¬λ λ³ν©μ λ ¬μ λν΄μ μμ보μ. 1. μ μ π λ³ν©μ λ ¬μ΄λ μ λ ¬ν΄μΌ νλ λ°°μ΄μ κ°μ₯ μμ λκΉμ§ λλκ³ , κ·Έ μμ λΆν° μΈμ ν λΆλΆλ°°μ΄λΌλ¦¬ λΉκ΅νλ©° μ λ ¬νλ μκ³ λ¦¬μ¦μ΄λ€. ν΄λΉ μκ³ λ¦¬μ¦μ λΆν μ 볡(Divide and Conquer) μκ³ λ¦¬μ¦μ κΈ°λ°μΌλ‘ νλ€. (λΆν μ 볡(Divide and Conquer)μ΄λ λ¬Έμ λ₯Ό λΆν νκ³ , λΆν ν λ¬Έμ λ₯Ό μ 볡νμ¬ ν©μΉλ κ²μ΄λ€.) 2. λμ λ°©μ πͺ μ£Όμ΄μ§ λ°°μ΄μ μ λ°μΌλ‘ λΆν νμ¬ λΆλΆλ°°μ΄λ‘ λλλ€. - λΆν (Divide) ν΄λΉ λΆλΆλ°°μ΄μ κΈΈμ΄κ° 1μ΄ λ λκΉμ§ κ³μν΄μ 1λ² κ³Όμ μ λ°λ³΅νλ€. μΈμ ν λΆλΆ λ°°μ΄λΌλ¦¬ ν©μΉλ€. - μ 볡(Conquer) μμ κ·Έλ¦Όμ ν΅ν΄ μ μ μλ―μ΄ ν¬κΈ°κ° 1μ΄ λ λκΉμ§ λΆν μ΄ μ§νλλ€. κ·Έλ¦¬κ³ μΈμ ν λ°°μ΄λΌλ¦¬ ν©..

μ½μ μ λ ¬(Insertion Sort)
1. μ μ 𧡠μ½μ μ λ ¬μ μμμλΆν° μ°¨λ‘λλ‘ μ΄λ―Έ μ λ ¬λ λ°°μ΄ λΆλΆκ³Ό λΉκ΅νμ¬, μμ μ μμΉλ₯Ό μ°Ύμ μ½μ ν¨μΌλ‘μ¨ μ λ ¬μ μμ±νλ μκ³ λ¦¬μ¦μ΄λ€. μΉ΄λ μμλ₯Ό μ΄ν΄λ³΄λ©΄ μ½κ² μ΄ν΄ν μ μμ κ²μ΄λ€. '4, 2, 3, 1, 5'λΌλ μ«μ μ ν 5μ₯μ μΉ΄λκ° μμλλ‘ μλ€κ³ νμ. μμμλΆν° μμλλ‘ μΉ΄λλ₯Ό λ½μΌλ©΄μ μμ μ₯λ€κ³ μκ°νμ. λ½ν μΉ΄λλ μ΄λ―Έ μμ μ₯μ΄μ§ μΉ΄λλ€ μ¬μ΄μ μμΉλ₯Ό μ°Ύμλ€μ΄κ°λ€. μ΄λ―Έ μμ μ₯μ΄μ Έ μλ μΉ΄λλ€ λ½μ μΉ΄λ μμ μ μμΉλ₯Ό μ°Ύμλ€μ΄κ° λͺ¨μ΅ 4 4 4 2 2 4 2 4 3 2 3 4 2 3 4 1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1λ² μ«μκ° μ ν μΉ΄λκ° μμ μ μμΉλ₯Ό μ°Ύμκ°λ κ²μ λ€μ νλ² μ΄ν΄λ³΄μ. 1λ² μΉ΄λλ 4λ²κ³Ό λΉκ΅νκ³ , 3λ²κ³Ό λΉκ΅νκ³ , 2λ²κ³Ό ..

μ ν μ λ ¬(Selection Sort)
μ ν μ λ ¬μ μ¬λ¬ κ°μ§ λ©΄μμ μμμ μ΄ν΄λ³Έ λ²λΈ μ λ ¬κ³Ό μλΉν λΉμ·νλ€. λ κ°μ§ μ λ ¬ λ°©λ²μ ꡬλΆνλ κ² μ΄λ ΅μ§λ μμΌλ, μ ν μ λ ¬μ 곡λΆνλ κΉμ λ²λΈ μ λ ¬λ κ°μ΄ 곡λΆνλ κ²μ μΆμ²νλ€. 1. μ μ πΏ μ ν μ λ ¬μ μμλ₯Ό λ£μ μμΉλ μ΄λ―Έ μ ν΄μ Έ μκ³ , μ΄λ€ μμλ₯Ό λ£μμ§ μ ννλ μκ³ λ¦¬μ¦μ΄λ€. 2. λμ λ°©μ 𧦠Nκ°μ μμκ° μλ€κ³ νμ. μ°μ , λ°°μ΄μμ μ΅μκ°μ μ°Ύλλ€. κ·Έλ¦¬κ³ μ²« λ²μ§Έ μμμ λ°°μ΄μμ μ°Ύμ μ΅μκ°μ μμλ₯Ό λ°κΏμ€λ€. μ΄κ²μ΄ 1νμ μνν κ²μ΄λ€. μ΄λ κ² λλ©΄ λ°°μ΄μ 첫 λ²μ§Έμ μμΉν μμκ° κ°μ₯ μμ κ°μ κ°μ§κ² λλ€. 2νμ μ μνν λλ 첫 λ²μ§Έ μμλ₯Ό μ μΈν λλ¨Έμ§ λ°°μ΄λ€ μ€μμ μ΅μκ°μ μ°Ύλλ€. κ·Έλ¦¬κ³ ν΄λΉ μμμ λ°°μ΄μ λ λ²μ§Έ μμλ₯Ό λ°κΏμ€λ€. μ΄μ κ°μ λ°©μμΌ..

λ²λΈ μ λ ¬(Bubble Sort)
κ±°ν μ λ ¬μ΄λΌκ³ λ λΆλ¦¬λ λ²λΈ μ λ ¬μ λν΄μ μμ보μ. 1. μ μ π λ²λΈ μ λ ¬μ μλ‘ μΈμ ν λ μμλ₯Ό κ²μ¬νμ¬ μ λ ¬νλ μκ³ λ¦¬μ¦μ΄λ€. 2. λμ λ°©μ π Nκ°μ μμκ° μλ€κ³ νμ. 첫 λ²μ§Έ μμμ λ λ²μ§Έ μμλ₯Ό λΉκ΅νμ¬ λ§μ½ 첫 λ²μ§Έ μμκ° λ ν¬λ€λ©΄ λμ μ리λ₯Ό λ°κΏμ€λ€. κ·Έλ¦¬κ³ λ λ²μ§Έ μμμ μΈ λ²μ§Έ μμλ₯Ό λΉκ΅νμ¬ λ§μ½ λ λ²μ§Έ μμκ° λ ν¬λ€λ©΄ λμ μ리λ₯Ό λ°κΏμ€λ€. μ΄λ¬ν λμμ (λ§μ§λ§ - 1) λ²μ§Έμ μμμ λ§μ§λ§ μμλ₯Ό λΉκ΅ν λκΉμ§ μννλ€. μ΄κ²μ΄ 1νμ μνν κ²μ΄λ€. μ΄λ κ² λλ©΄ λ§μ§λ§μ μμΉν μμκ° κ°μ₯ ν° μμκ° λλ€. 2νμ μ μνν λ λ§μ§λ§ μμλ₯Ό μ μΈν λλ¨Έμ§λ€μ μ λ ¬ν΄ μ€λ€. (N - 1) νμ κΉμ§ μννλ©΄ μ λ ¬μ΄ λ§λ¬΄λ¦¬λλ€. μμ λ°©μμ μ€λ¦μ°¨μμΌλ‘ μ λ ¬μ ..