-
[μκ³ λ¦¬μ¦] μ¬κ· ν¨μcodeStates front-end/Algorithm 2023. 2. 14. 15:12λ°μν
π μ¬κ·
πμ¬κ·μ μ΄ν΄
μ¬κ· : μλμ μλ¦¬λ‘ λλμκ°κ±°λ λλμμ΄
π μ¬κ·μ μ½λ
function recursion () { console.log("This is") console.log("recursion!") recursion() }
recursion() ν¨μ?
μκΈ° μμ μ λμμ΄ νΈμΆνλ©΄μ κ°μ μ½λκ° κ³μν΄μ μ€νλλ€
ππΌ μ΄ ν¨μμ²λΌ μκΈ° μμ μ νΈμΆνλ ν¨μλ₯Ό μ¬κ· ν¨μλΌκ³ νλ€
π μ¬κ·λ‘ λ¬Έμ ν΄κ²°νκΈ°
λ¬Έμ : μμ°μλ‘ μ΄λ£¨μ΄μ§ 리μ€νΈ(λ°°μ΄)μ μ λ ₯λ°κ³ , 리μ€νΈμ ν©μ 리ν΄νλ ν¨μ 'arrSum'μ μμ±νμΈμ.
1. λ¬Έμ λ₯Ό μκ² μͺΌκ°κΈ°
[1, 2, 3, 4, 5] μ ν©μ ꡬνλ κ³Όμ
1 + 2 + 3 + 4 + 5 =?
2 + 3 + 4 + 5 =?
3 + 4 + 5 =?
4 + 5 =?
...
μ λ°©μμΌλ‘ λ¬Έμ λ₯Ό μͺΌκ° κ²μ μ½λλ‘ νν
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) ...
2. λ¬Έμ λ₯Ό κ°μ₯ μμ λ¨μλ‘ μͺΌκ°κΈ°
... arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) arrSum([4, 5]) === 4 + arrSum([5]) arrSum([5]) === 5 + arrSum([]) // λ μ΄μ μͺΌκ°€ μ μλ μν
3. λ¬Έμ ν΄κ²°νκΈ°
κ°μ₯ μμ λ¨μμ λ¬Έμ λ₯Ό ν΄κ²°ν λ°©μμΌλ‘ λ¬Έμ μ 체λ₯Ό ν΄κ²°
arrSum([]) === 0; // <-- κ°μ₯ μμ λ¬Έμ λ₯Ό λΉ λ°°μ΄μ ν© 0μΌλ‘ λ¦¬ν΄ // κ°μ₯ μμ κ²½μ°μ ν΄κ²°μ± μ μ μ©ν©λλ€. arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5; arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9; arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12; arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14; arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;
μμ± μ½λ
function arrSum (arr) { // λΉ λ°°μ΄μ λ°μμ λ 0μ 리ν΄νλ 쑰건문 // --> κ°μ₯ μμ λ¬Έμ λ₯Ό ν΄κ²°νλ μ½λ & μ¬κ·λ₯Ό λ©μΆλ μ½λ if (arr.length === 0) { return 0 } // λ°°μ΄μ 첫 μμ + λλ¨Έμ§ μμκ° λ΄κΈ΄ λ°°μ΄μ λ°λ arrSum ν¨μ // --> μ¬κ·(μκΈ° μμ μ νΈμΆ)λ₯Ό ν΅ν΄ λ¬Έμ λ₯Ό μκ² μͺΌκ°λκ°λ μ½λ return arr.shift() + arrSum(arr) }
π μ¬κ· μ¬μ© μμ
1. μ£Όμ΄μ§ λ¬Έμ λ₯Ό λΉμ·ν ꡬ쑰μ λ μμ λ¬Έμ λ‘ λλ μ μλ κ²½μ°
2. μ€μ²©λ λ°λ³΅λ¬Έμ΄ λ§κ±°λ λ°λ³΅λ¬Έμ μ€μ²© νμ(number of loops)λ₯Ό μμΈ‘νκΈ° μ΄λ €μ΄ κ²½μ°
for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { for (let k = 0; k < n; k++) { for (let l = 0; l < n; l++) { for (let m = 0; m < n; m++) { for (let n = 0; n < n; n++) { for (let o = 0; o < n; o++) { for (let p = 0; p < n; p++) { // do something someFunc(i, j, k, l, m, n, o, p); } } } } } } } }
π μ¬κ·μ νμ©
π μ¬κ·μ μΌλ‘ μ¬κ³ νκΈ°
1. μ¬κ· ν¨μμ μ λ ₯κ°κ³Ό μΆλ ₯κ° μ μνκΈ°
μΆμμ , λλ κ°μ₯ λ¨μνκ² μ μ
ν¨μμ μ μΆλ ₯κ°μ μ μ -> μ¬κ· ν¨μλ₯Ό ν΅ν΄ λͺ©ν μ μ
2. λ¬Έμ λ₯Ό μͺΌκ°κ³ κ²½μ°μ μλ₯Ό λλκΈ°
λ¬Έμ λ₯Ό μͺΌκ°€ κΈ°μ€μ μ νκ³ , μ ν κΈ°μ€μ λ°λΌ λ¬Έμ λ₯Ό λ ν° κ²½μ°μ μμ κ²½μ°λ‘ ꡬλΆ
κ΅¬λΆ κΈ°μ€μ "μ λ ₯κ°μ΄λ λ¬Έμ μ μμμ ν¬κΈ°" μ΄λ€
3. λ¨μν λ¬Έμ ν΄κ²°νκΈ°
λ¬Έμ λ₯Ό μ¬λ¬ κ²½μ°λ‘ ꡬλΆν λ€μ, κ°μ₯ ν΄κ²°νκΈ° μ¬μ΄ λ¬Έμ λΆν° ν΄κ²°
ππΌ μ¬κ·μ κΈ°μ΄
μ¬κ·μ κΈ°μ΄λ λμ€μ μ¬κ· ν¨μλ₯Ό ꡬνν λ, μ¬κ·μ νμΆ μ‘°κ±΄(μ¬κ· νΈμΆμ΄ λ©μΆλ 쑰건)μ ꡬμ±
νμΆ μ‘°κ±΄μ΄ μλ€λ©΄? λμμ΄ μκΈ° μμ μ νΈμΆ
4. 볡μ‘ν λ¬Έμ ν΄κ²°νκΈ°
λ¨μμλ 볡μ‘ν κ²½μ°λ₯Ό ν΄κ²°
5. μ½λ ꡬν
λ°μν'codeStates front-end > Algorithm' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[μλ£κ΅¬μ‘°] Tree, Graph (0) 2023.03.15 [μλ£κ΅¬μ‘°] Stack, Queue (0) 2023.03.14 Daily Coding 10 (0) 2023.02.02 Daily Coding 9 (0) 2023.01.30 Daily Coding 8 (0) 2023.01.25