Algorithm/μΈνλ°(inflearn)
π μ΅λμ μ ꡬνκΈ°(λ
μ μκ³ λ¦¬μ¦) μ΄λ² μ 보μ¬λ¦ΌνΌμλλνμμ μ’μ μ±μ μ λ΄κΈ° μνμ¬ νμλ μ μλμ΄ μ£Όμ Nκ°μ λ¬Έμ λ₯Ό νλ €κ³ νλ€. κ° λ¬Έμ λ κ·Έκ²μ νμμ λ μ»λ μ μμ νΈλ λ° κ±Έλ¦¬λ μκ°μ΄ μ£Όμ΄μ§κ² λλ€. μ ν μκ° M μμ Nκ°μ λ¬Έμ μ€ μ΅λμ μλ₯Ό μ»μ μ μλλ‘ ν΄μΌ νλ€. (ν΄λΉ λ¬Έμ λ ν΄λΉ μκ°μ΄ 걸리면 νΈλ κ±Έλ‘ κ°μ£Όνλ€. ν μ νλΉ ν κ°λ§ ν μ μλ€.) μ
λ ₯μ€λͺ
첫 λ²μ§Έ μ€μ λ¬Έμ μ κ°μ N(1
Algorithm/μΈνλ°(inflearn)
π λμ κ΅ν(λ
μ μκ³ λ¦¬μ¦) λ€μκ³Ό κ°μ΄ μ¬λ¬ λ¨μμ λμ λ€μ΄ μ£Όμ΄μ Έ μμλ κ±°μ€λ¦λμ κ°μ₯ μ μ μμ λμ μΌλ‘ κ΅νν΄μ£Όλ €λ©΄ μ΄λ»κ² μ£Όλ©΄ λλκ°? κ° λ¨μμ λμ μ 무νμ μΈ μ μλ€. μ
λ ₯μ€λͺ
첫 λ²μ§Έ μ€μλ λμ μ μ’
λ₯κ°μ N(1
Algorithm/μΈνλ°(inflearn)
π μ΅λ λΆλΆ μ¦κ°μμ΄(LIS) Nκ°μ μμ°μλ‘ μ΄λ£¨μ΄μ§ μμ΄μ΄ μ£Όμ΄μ‘μ λ, κ·Έμ€μμ κ°μ₯ κΈΈκ² μ¦κ°νλ(μμ μμμ ν° μλ‘) μμλ€μ μ§ν©μ μ°Ύλ λ¬Έμ μ΄λ€. μλ₯Ό λ€μ΄, μμκ° 2, 7, 5, 8, 6, 4, 7, 12, 3μ΄λ©΄ κ°μ₯ κΈΈκ² μ¦κ°νλλ‘ μμλ€μ μ°¨λ‘λλ‘ λ½μλ΄λ©΄ 2, 5, 6, 7, 12λ₯Ό λ½μλ΄μ΄ κΈΈμ΄κ° 5μΈ μ΅λ λΆλΆ μ¦κ° μμ΄μ λ§λ€ μ μλ€. μ
λ ₯μ€λͺ
첫째 μ€μ μ
λ ₯λλ λ°μ΄ν°μ μ N(1= 0; j--) { if (arr[j] < arr[i] && max < dy[j]) { max = dy[j]; } } dy[i] = max + 1; } answer = Math.max(...dy); return answer; } let arr = [2, 7, 5, 8, 6, 4, 7, 12,..
Algorithm/μΈνλ°(inflearn)
π 02 - λλ€λ¦¬ 건λκΈ°(DP) μ² μλ νκ΅μ κ°λλ° κ°μΈμ λ§λ¬λ€. κ°μΈμ Nκ°μ λλ‘ λ€λ¦¬λ₯Ό λ§λ€μ΄ λμλ€. μ² μλ λ λ€λ¦¬λ₯Ό 건λ λ ν λ²μ ν μΉΈ λλ λ μΉΈμ© κ±΄λλ°λ©΄μ λλ€λ¦¬λ₯Ό 건λ μ μλ€. μ² μκ° κ°μΈμ 건λλ λ°©λ²μ λͺκ°μ§μΌκΉ? π μμ€ μ½λ μ°Έκ³ ) κ³λ¨μ€λ₯΄κΈ° function solution(n) { let answer = 0; let dy = Array.from({ length: n + 2 }, () => 0); dy[1] = 1; dy[2] = 2; for (let i = 3; i
Algorithm/μΈνλ°(inflearn)
π 01 - κ³λ¨μ€λ₯΄κΈ°(λμ κ³νλ²) μ² μλ κ³λ¨μ μ€λ₯Ό λ ν λ²μ ν κ³λ¨ λλ λ κ³λ¨μ© μ¬λΌκ°λ€. λ§μ½ μ΄ 4κ³λ¨μ μ€λ₯Έλ€λ©΄ κ·Έ λ°©λ²μ μλ 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2λ‘ 5κ°μ§μ΄λ€. κ·Έλ λ€λ©΄ μ΄ Nκ³λ¨μΌ λ μ² μκ° μ¬λΌκ° μ μλ λ°©λ²μ μλ λͺ κ°μ§μΈκ°? π νμ΄ λ°©λ²(DFS, DP) DFS μκ³ λ¦¬μ¦μ μ¬μ©νμ¬ λ¬Έμ λ₯Ό νμ΄λ³΄μλ€. μ λ΅μ νλ₯νκ²λ μ λμ¨λ€ π νμ§λ§ nμ κ°μ΄ 컀μ§λ€λ©΄...β μ°μ° νμκ° κΈ°νκΈμμ μΌλ‘ μ¦κ°νκ² λλ€. μ΄λ₯Ό ν΄κ²°ν μ μλ λ°©λ²μΌλ‘ λμ κ³νλ²(dynamic programming, DP)μ΄ μ‘΄μ¬νλ€. function solution(n) { let answer = 0; function DFS(sum) { if (sum > n)..
Algorithm/μΈνλ°(inflearn)
π 07 - μ¬λλΌ μμΌλλ(BFS νμ©) N*Nμ μ¬λλΌ μμΌλλμ μ§λκ° κ²©μνμ μ λ³΄λ‘ μ£Όμ΄μ§λ€. κ° μ¬μ 1λ‘ νμλμ΄ μνμ’μ°μ λκ°μ μΌλ‘ μ°κ²°λμ΄ μμΌλ©°, 0μ λ°λ€μ΄λ€. μ¬λλΌ μμΌλλμ λͺ κ°μ μ¬μ΄ μλμ§ κ΅¬νλ λ¬Έμ μ΄λ€. λ§μ½ μμ κ°λ€λ©΄ μ¬μ κ°μλ μ΄ 5κ°μ΄λ€. μ¬λλΌ μμΌλλ(DFS) λ¬Έμ μ κ°μ§λ§ μ΄λ²μλ BFS μκ³ λ¦¬μ¦μ μ΄μ©ν΄ νμ΄λ³΄μλ€. μμμ νμνλ λ¬Έμ μ κ²½μ°μλ λ³ΈμΈμκ² νΈν λ°©λ²μ μ΄μ©νμ¬ νλ©΄ λ κ² κ°λ€..π€ π νμ΄ λ°©λ² μ΄μ€ for λ¬Έμ λλ©΄μ 1μ΄ λμ¨λ€λ©΄ μ¬μ λ°κ²¬ν κ²μ΄λ―λ‘ λ°°μ΄μμ ν΄λΉ μ’νλ₯Ό 0μΌλ‘ μ¬ν λΉνκ³ answer++μ νλ€. λν, λμ΄ μ°μ νμμ μν΄ νμ ν΄λΉ μ’νλ₯Ό μΆκ°νλ€. while λ¬Έμ λλ©΄μ νμμ shift ν μ’νμ λν΄ ..
Algorithm/μΈνλ°(inflearn)
π 06 - μ¬λλΌ μμΌλλ(DFS νμ©) N*Nμ μ¬λλΌ μμΌλλμ μ§λκ° κ²©μνμ μ λ³΄λ‘ μ£Όμ΄μ§λ€. κ° μ¬μ 1λ‘ νμλμ΄ μνμ’μ°μ λκ°μ μΌλ‘ μ°κ²°λμ΄ μμΌλ©°, 0μ λ°λ€μ΄λ€. μ¬λλΌ μμΌλλμ λͺ κ°μ μ¬μ΄ μλμ§ κ΅¬νλ λ¬Έμ μ΄λ€. λ§μ½ μμ κ°λ€λ©΄ μ¬μ κ°μλ μ΄ 5κ°μ΄λ€. π νμ΄ λ°©λ² λ―Έλ‘ νμ λ¬Έμ μ μ μ¬ν λ¬Έμ μ΄λ―λ‘ μ°Έκ³ νλ©΄ μ’μ λ―νλ€. μ΄μ€ for λ¬Έμ λλ©΄μ 1μ΄ λμ¨λ€λ©΄ μ¬μ λ°κ²¬ν κ²μ΄λ―λ‘ λ°°μ΄μμ ν΄λΉ μ’νλ₯Ό 0μΌλ‘ μ¬ν λΉνκ³ answer++μ νλ€. ν΄λΉ μ’νμ λν΄ DFSλ₯Ό λλ©΄μ μνμ’μ°μ λκ°μ μΌλ‘ μ°κ²°λ μ’νκ° μλμ§ νμνλ€. μ°κ²°λ μ’νκ° μλ€λ©΄ 0μΌλ‘ μ¬ ν λΉνκ³ μ°κ²°λ μ’νλ‘ μ΄λνλ€. λ μ΄μ μ°κ²°λ μ’νκ° μλ€λ©΄ DFS ν¨μλ₯Ό λͺ¨λ μ’
λ£νκ³ μ΄μ€ for λ¬Έμ..
Algorithm/μΈνλ°(inflearn)
π 05 - μ‘μμ§ μ°ΎκΈ°(BFS : μλνΈλ¦¬νμ) νμλ μ‘μμ§λ₯Ό μμ΄λ²λ Έλ€. λ€νν μ‘μμ§μλ μμΉμΆμ κΈ°κ° λ¬λ € μλ€. νμμ μμΉμ μ‘μμ§μ μμΉκ° μμ§μ μμ μ’ν μ μΌλ‘ μ£Όμ΄μ§λ©΄ νμλ νμ¬ μμΉμμ μ‘μμ§μ μμΉκΉμ§ λ€μκ³Ό κ°μ λ°©λ²μΌλ‘ μ΄λνλ€. μ‘μμ§λ μμ§μ΄μ§ μκ³ μ μ리μ μλ€. νμλ μ€μΉ΄μ΄ 콩콩μ νκ³ κ°λλ° ν λ²μ μ νλ‘ μμΌλ‘ 1, λ€λ‘ 1, μμΌλ‘ 5λ₯Ό μ΄λν μ μλ€. μ΅μ λͺ λ²μ μ νλ‘ νμκ° μ‘μμ§μ μμΉκΉμ§ κ° μ μλμ§ κ΅¬νλ λ¬Έμ μ΄λ€. π μ
λ ₯μ€λͺ
첫 λ²μ§Έ μ€μ νμμ μμΉ Sμ μ‘μμ§μ μμΉ Eκ° μ£Όμ΄μ§λ€. μ§μ μ μ’ν μ μ 1λΆν° 10,000κΉμ§μ΄λ€. π μΆλ ₯μ€λͺ
μ νμ μ΅μνμλ₯Ό ꡬνλ€. λ΅μ 1 μ΄μμ΄λ€. λ¬Έμ λ₯Ό ν΄μνλ©΄ νμμ μμΉ(μΆλ° μ§μ )μμ μ‘μμ§μ ..