SEB/TIL

027 | Permutation & Combination, Greedy Implementation

kexon 2022. 7. 29. 20:38

πŸ’™ Permutation & Combination

  • μˆœμ—΄(Permutation): μš”μ†Œ n개 쀑에 m개λ₯Ό μ„ νƒν•˜μ—¬ μˆœμ„œλ₯Ό μ§€ν‚€λ©΄μ„œ λ½‘λŠ” 경우의 수
  • μ‘°ν•©(Combination): μˆœμ„œμ— 상관없이 μš”μ†Œ n개 쀑에 m개λ₯Ό λ½‘λŠ” 경우의 수
  • ! (factorial, νŒ©ν† λ¦¬μ–Ό) n! 은 nμ—μ„œλΆ€ν„° 1μ”© κ°μ†Œν•˜μ—¬ 1κΉŒμ§€μ˜ λͺ¨λ“  μ •μˆ˜μ˜ κ³±
    • (n 보닀 μž‘κ±°λ‚˜ 같은 λͺ¨λ“  μ–‘μ˜ μ •μˆ˜μ˜ κ³±)
    • νŒ©ν† λ¦¬μ–Όμ—μ„œ 0! κ³Ό 1! μ€ 1

πŸ’œ μ˜€λŠ˜μ˜ 생각 쑰각λͺ¨μŒ

  • 그리디 아무리 봐도 λ¬Έμ œλŠ” μ•Œκ² λŠ”λ° κ΅¬ν˜„μ„ λͺ»ν•˜κ² μ–΄μ„œ μž μ‹œ 보λ₯˜ν•˜κ³  μžλ°” κ³΅λΆ€ν–ˆλ‹€. μ•Œκ³ λ¦¬μ¦˜ λ„ˆλ¬΄ μ–΄λ ΅λ‹€...γ… .γ