λ¬Έμ ν΄κ²° (PS)/κΈ°μ΅ν΄λ κ²
λΆλΆ μμ΄
9taetae9
2023. 12. 22. 01:18
728x90
λΆλΆ μμ΄(Subsequence)μ μ΄λ€ μ£Όμ΄μ§ μμ΄μμ μμλ₯Ό μ μ§νλ©΄μ μΌλΆ λλ μ 체 μμλ₯Ό μ ννμ¬ λ§λ€ μ μλ μλ‘μ΄ μμ΄μ΄λ€.
μ€μν μ μ μ νλ μμλ€μ΄ μλ μμ΄μμμ μμλ₯Ό μ μ§ν΄μΌ νλ€λ κ²μ΄λ€.
μμ΄μ΄ A,B,C,DλΌκ³ ν λ, κ°λ₯ν λΆλΆ μμ΄ μ€ μμλ λ€μκ³Ό κ°λ€.
- A,B (첫 λ²μ§Έμ λ λ²μ§Έ μμ μ ν)
- B,D (λ λ²μ§Έμ λ€ λ²μ§Έ μμ μ ν)
- A,C,D (첫 λ²μ§Έ, μΈ λ²μ§Έ, λ€ λ²μ§Έ μμ μ ν)
- C (μΈ λ²μ§Έ μμλ§ μ ν)
- A,B,C,D (λͺ¨λ μμ μ ν, μ΄ κ²½μ° μλ μμ΄κ³Ό λμΌ)
- [] (μ무 μμλ μ ννμ§ μμ, λΉ λΆλΆ μμ΄)
μμλ₯Ό μ νν λ, μλ μμ΄μμμ μμλ₯Ό λ³κ²½νκ±°λ μμλ₯Ό λ°λ³΅ν΄μ μ¬μ©ν μ μλ€.
μλ₯Ό λ€μ΄, B,Aλ C,Cλ μ ν¨ν λΆλΆ μμ΄μ΄ μλλ€.
λΆλΆ μμ΄μ κ°λ μ κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄(Longest Increasing Subsequence) μ°Ύλ dp νμ© λ¬Έμ λ±μμ λ±μ₯ν μ μλ€.
728x90