Algorithm & Data Structure
-
μμ νλ³ μκ³ λ¦¬μ¦(JAVA)Algorithm & Data Structure 2024. 4. 6. 13:48
μμ 1κ³Ό μκΈ° μμ μ μ μΈν μμ°μλ€μ μ½μλ‘ κ°κ³ μμ§ μμ μμ΄λ€. (ex : 2, 3, 5, 7 ...) μ κ³±κ·Όμ μ΄μ©ν λ°©μ public boolean isPrime(long num) { if (num == 1) { return false; } for (int i = 2; i
-
[C++] ν¬ ν¬μΈν°(Two Pointers) μκ³ λ¦¬μ¦Algorithm & Data Structure 2022. 2. 5. 15:49
λ€μ΄κ°λ©° λ°±μ€ 3273λ² λ¬Έμ λ₯Ό ν΄κ²°νλ €λ λ° 2μ€ forλ¬ΈμΌλ‘ μ½λλ₯Ό μ§μ μ μΆνλ©΄ μκ° μ΄κ³Όκ° λμ μ΄μ λν ν΄κ²°λ°©μμ μμλ³΄κ² λμλ€. ν¬ ν¬μΈν°(Two Pointers)λ‘ ν΄κ²°νλ©΄ μ½κ² ν΄κ²°ν μ μλ€λ κ²μ μκ³ μ΄μ λν΄ μ€λͺ νλ€. ν¬ ν¬μΈν°λ? ν¬ ν¬μΈν°(Two Pointers)λ 1μ°¨μ λ°°μ΄μμ λ κ°μ ν¬μΈν°λ₯Ό μ‘°μνμ¬ μνλ κ²°κ³Όλ₯Ό μ»λ μκ³ λ¦¬μ¦μ λ§νλ€. μ΄μ²λΌ λ κ°μ ν¬μΈν°λ₯Ό μ¬μ©νλ©΄ λ°λ³΅λ¬Έμ μ¬λ¬λ² μννλ κ² λ³΄λ€ μκ°μ ν¨μ¨μ μΌλ‘ μ¬μ©ν μ μλ€. μ΅μ μ κ²½μ°μλ λ κ°μ ν¬μΈν°κ° λ°°μ΄μ λ§μ§λ§ μΈλ±μ€λ‘ μ€κ² λλ€. λ°λΌμ μκ° λ³΅μ‘λλ O(n)μ΄λ€. ν¬ ν¬μΈν° μκ³ λ¦¬μ¦ λ°±μ€ 2003λ² λ¬Έμ λ₯Ό μμλ‘ μκ³ λ¦¬μ¦μ μ΄ν΄ν΄λ³΄μ. μ΄ λ¬Έμ μμλ NκΉμ§μ λ°°μ΄μ΄ μκ³ λΆλΆν©μ΄ Mμ΄ ..
-
[C++] DFS(Depth First Search) κΉμ΄ μ°μ νμ μκ³ λ¦¬μ¦Algorithm & Data Structure 2022. 1. 30. 15:19
λ€μ΄κ°λ©° DFSλ μμμ λ°°μ΄ BFSμ²λΌ νμ μκ³ λ¦¬μ¦ μ€ νλμ΄λ€. BFSμ ꡬνμ μ°¨μ΄μ μ΄ μλ€λ©΄ BFSμμλ Queue(ν)λ₯Ό μ¬μ© νμ§λ§, DFSμμλ Stack(μ€ν)μ μ¬μ©ν΄μ ꡬννλ€. DFS(κΉμ΄ μ°μ νμ) μ΄λ? κΉμ΄ μ°μ νμ( - εͺε ζ’η΄’, μμ΄: depth-first search, DFS)μ λ§Ήλͺ©μ νμλ°©λ²μ νλλ‘ νμνΈλ¦¬μ μ΅κ·Όμ 첨κ°λ λ Έλλ₯Ό μ ννκ³ , μ΄ λ Έλμ μ μ© κ°λ₯ν λμμ μ€ νλλ₯Ό μ μ©νμ¬ νΈλ¦¬μ λ€μ μμ€(level)μ ν κ°μ μμλ Έλλ₯Ό 첨κ°νλ©°, 첨κ°λ μμ λ Έλκ° λͺ©νλ ΈλμΌ λκΉμ§ μμ μμ λ Έλμ μ²¨κ° κ³Όμ μ λ°λ³΅ν΄ κ°λ λ°©μμ΄λ€. - μν€λ°±κ³Ό DFS μκ³ λ¦¬μ¦ μλμ μ¬μ§λ€μ λ³΄κ³ DFSλ₯Ό μ΄ν΄ν΄λ³΄μ. μμ μ§μ μ 1μ΄λΌκ³ νμ. 1μ λ°©λ¬Ένλ€λ νμλ₯Ό ..
-
[C++] BFS(Breadth First Search) λλΉ μ°μ νμ μκ³ λ¦¬μ¦Algorithm & Data Structure 2022. 1. 21. 23:01
λ€μ΄κ°λ©° BFSλ μ½λ©ν μ€νΈμ μμ£Ό μ¬μ©λλ μκ³ λ¦¬μ¦μ΄λ€. Flood Fillκ³Ό κ°μ λ¬Έμ λ€μ ν΄κ²°νλ λ° μ¬μ©ν μ μλ€. μ΄λ₯Ό ꡬννκΈ° μν΄μλ Queue(ν)λ₯Ό μ¬μ©νλ€! BFS(λλΉ μ°μ νμ) μ΄λ? λλΉ μ°μ νμ(Breadth-first search, BFS)μ λ§Ήλͺ©μ νμλ°©λ²μ νλλ‘ μμ μ μ μ λ°©λ¬Έν ν μμ μ μ μ μΈμ ν λͺ¨λ μ μ λ€μ μ°μ λ°©λ¬Ένλ λ°©λ²μ΄λ€. λ μ΄μ λ°©λ¬Ένμ§ μμ μ μ μ΄ μμ λκΉμ§ λ°©λ¬Ένμ§ μμ λͺ¨λ μ μ λ€μ λν΄μλ λλΉ μ°μ κ²μμ μ μ©νλ€. OPEN Listλ νλ₯Ό μ¬μ©ν΄μΌλ§ λ 벨 μμλλ‘ μ κ·Όμ΄ κ°λ₯νλ€. - μν€λ°±κ³Ό BFS μκ³ λ¦¬μ¦ μλμ μ¬μ§λ€μ λ³΄κ³ BFSλ₯Ό μ΄ν΄ν΄λ³΄μ. μμ μ§μ μ΄ 1μ΄λΌκ³ νμ. κ·Έλ¬λ©΄ 1μ λ°©λ¬Ένλ€λ νμλ₯Ό λ¨κΈ°κ³ ν΄λΉ μΉΈμ νμ..
-
[C++] μ€νμ νμ©(μμμ κ΄νΈ κ²μ¬)Algorithm & Data Structure 2022. 1. 20. 22:50
λ€μ΄κ°λ©° μ΄λ²μλ μ€νμ νμ©νμ¬ μμμ κ΄νΈ μμ κ²μ¬νλ μκ³ λ¦¬μ¦μ λν΄ μμ보μ! μμμ κ΄νΈ μ μμ ( { { ) } } -> μ¬λ°λ₯΄μ§ μμ μ ( ( ) ) -> μ¬λ°λ₯Έ μ μμμ κ΄νΈ μ ν΄κ²° μκ³ λ¦¬μ¦ μ¬λ κ΄νΈκ° λμ€λ©΄ μ€νμ μΆκ°νλ€. λ«λ κ΄νΈκ° λμμ λ μλμ 3κ°μ§ λ°©λ²μΌλ‘ μ²λ¦¬νλ€. μ€νμ΄ λΉμ΄μμΌλ©΄ μ¬λ°λ₯΄μ§ μμ κ΄νΈ μμ΄λ€. μ€νμ topκ³Ό μ§μ΄ λ§μ§ μλ κ΄νΈλΌλ©΄ μ¬λ°λ₯΄μ§ μμ κ΄νΈ μμ΄λ€. μ€νμ topκ³Ό μ§μ΄ λ§λ κ΄νΈλΌλ©΄ popνλ€. μμ κ³Όμ μ λλΈ ν μ€νμ κ΄νΈκ° λ¨μμμΌλ©΄ μ¬λ°λ₯΄μ§ μμ κ΄νΈ μμ΄κ³ , λ°λλ‘ μ€νμ κ΄νΈκ° λ¨μμμ§ μλ€λ©΄ μ¬λ°λ₯Έ κ΄νΈ μμ΄λ€. λ¬Έμ ν΄κ²° μλλ λ°±μ€(BOJ) 4949λ² κ· νμ‘ν μΈμμ μμ μκ³ λ¦¬μ¦μ μ΄μ©ν΄ ν΄κ²°ν μ½λμ΄λ€. ht..
-
[C++] λ±μ κ°λ κ³Ό STL Deque μ¬μ©λ²Algorithm & Data Structure 2022. 1. 18. 22:47
λ€μ΄κ°λ©° λ±(Deque)μ Double Ended Queueμ μ½μλ‘ νμ μμͺ½ λμμ μμλ₯Ό μΆκ°νκ±°λ μμ λ₯Ό ν μ μλ μλ£κ΅¬μ‘°μ΄λ€. κ·Έλ¦¬κ³ C++ STLμ λ±μ΄ ꡬνλμ΄ μμ΄ μ½κ² μ΄μ©ν μ μλ€! λ±(Deque) μ΄λ? λ±(deque, "deck"κ³Ό λ°μμ΄ κ°μ ← double-ended queue)μ μμͺ½ λμμ μ½μ κ³Ό μμ κ° λͺ¨λ κ°λ₯ν μλ£ κ΅¬μ‘°μ ν ννμ΄λ€. λ κ°μ ν¬μΈν°λ₯Ό μ¬μ©νμ¬, μμͺ½μμ μμ μ μ½μ μ λ°μμν¬ μ μλ€. νμ μ€νμ ν©μΉ ννλ‘ μκ°ν μ μλ€. - μν€λ°±κ³Ό λ± λ±μ λν΄μ μλμ μ¬μ§μ λ³΄κ³ μ΄ν΄ν΄λ³΄μ. μ μ¬μ§μ 보면 μμ 32λ₯Ό backμ λ£μ΄μ λ± μμ μμκ° 5, 17, 32κ° λ€μ΄μκ² λλ€. μ¬κΈ°μ frontμ μλ μμ 5λ₯Ό μ κ±°νλ©΄ λ± μμ 17,..
-
[C++] νμ κ°λ κ³Ό STL Queue μ¬μ©λ²Algorithm & Data Structure 2022. 1. 17. 22:31
λ€μ΄κ°λ©° νλ λ¨Όμ λ€μ΄κ° μμκ° λ¨Όμ λμ€κ² λλ ꡬ쑰μ¬μ FIFO(First In First Out) μλ£κ΅¬μ‘°λΌκ³ λΆλ₯Έλ€. κ·Έλ¦¬κ³ C++ STLμ νκ° κ΅¬νλμ΄ μμ΄ μ½κ² μ΄μ©ν μ μλ€! νλ BFS, Flood Fill μκ³ λ¦¬μ¦μ λ³΄ν΅ μ¬μ©νλ€. ν(Queue) λ? ν(queue)λ μ»΄ν¨ν°μ κΈ°λ³Έμ μΈ μλ£ κ΅¬μ‘°μ νκ°μ§λ‘, λ¨Όμ μ§μ΄ λ£μ λ°μ΄ν°κ° λ¨Όμ λμ€λ FIFO(First In First Out)κ΅¬μ‘°λ‘ μ μ₯νλ νμμ λ§νλ€. μμ΄ λ¨μ΄ queueλ νλ₯Ό μ¬λ¬ μΌλ ¬λ‘ λμ΄μ μ¬λλ€λ‘ μ΄λ£¨μ΄μ§ μ€μ λ§νκΈ°λ νλ©°, λ¨Όμ μ€μ μ μ¬λμ΄ λ¨Όμ λκ° μ μλ μν©μ μ°μνλ©΄ λλ€. λμ€μ μ§μ΄ λ£μ λ°μ΄ν°κ° λ¨Όμ λμ€λ μ€νκ³Όλ λ°λλλ κ°λ μ΄λ€. νλ¦°ν°μ μΆλ ₯ μ²λ¦¬λ μλ μμ€ν μ λ©μμ§ μ²..
-
[C++] μ€νμ κ°λ κ³Ό STL Stack μ¬μ©λ²Algorithm & Data Structure 2022. 1. 15. 22:46
λ€μ΄κ°λ©° μμΌλ‘ μΈ κ°μ§ κ΄λ ¨ μλ μλ£κ΅¬μ‘°μΈ μ€ν, ν, λ±μ λν΄μ λ€λ£° κ²μ΄λ€. μ€νμ λ¨Όμ λ€μ΄κ° μμκ° μ μΌ λμ€μ λμ€κ² λλ ꡬ쑰μ¬μ FILO(First In Last Out) μλ£κ΅¬μ‘°λΌκ³ λΆλ₯΄κΈ°λ νλ€. λν λ°λλ‘ λμ€μ λ€μ΄κ° μμκ° μ μΌ λ¨Όμ λμ€κ² λλ ꡬ쑰μ΄λ―λ‘ LIFO(Last In First Out)μ ννλ₯Ό λ λ μλ£κ΅¬μ‘°μ΄κΈ°λ νλ€. κ·Έλ¦¬κ³ C++ STLμ μ€νμ΄ κ΅¬νλμ΄ μμ΄ μ½κ² μ΄μ©ν μ μλ€! μ€ν(Stack) μ΄λ? μ€ν(stack)μ μ νμ μΌλ‘ μ κ·Όν μ μλ λμ΄ κ΅¬μ‘°μ΄λ€. κ·Έ μ κ·Ό λ°©λ²μ μΈμ λ λͺ©λ‘μ λμμλ§ μΌμ΄λλ€. λλ¨Όμ λ΄κΈ° λͺ©λ‘(Pushdown list)μ΄λΌκ³ λ νλ€. μ€νμ ν μͺ½ λμμλ§ μλ£λ₯Ό λ£κ±°λ λΊ μ μλ μ ν ꡬ쑰(LIFO - Last I..