λͺ©λ‘μ „체 κΈ€ (108)

𝘚𝘭𝘰𝘸 𝘣𝘢𝘡 𝘴𝘡𝘦𝘒π˜₯𝘺

[λ°±μ€€] 10814번: λ‚˜μ΄μˆœ μ •λ ¬ - C++

문제 온라인 저지에 κ°€μž…ν•œ μ‚¬λžŒλ“€μ˜ λ‚˜μ΄μ™€ 이름이 κ°€μž…ν•œ μˆœμ„œλŒ€λ‘œ 주어진닀. μ΄λ•Œ, νšŒμ›λ“€μ„ λ‚˜μ΄κ°€ μ¦κ°€ν•˜λŠ” 순으둜, λ‚˜μ΄κ°€ κ°™μœΌλ©΄ λ¨Όμ € κ°€μž…ν•œ μ‚¬λžŒμ΄ μ•žμ— μ˜€λŠ” μˆœμ„œλ‘œ μ •λ ¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. μž…λ ₯ 첫째 쀄에 온라인 저지 νšŒμ›μ˜ 수 N이 주어진닀. (1 ≤ N ≤ 100,000) λ‘˜μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” 각 νšŒμ›μ˜ λ‚˜μ΄μ™€ 이름이 곡백으둜 κ΅¬λΆ„λ˜μ–΄ 주어진닀. λ‚˜μ΄λŠ” 1보닀 ν¬κ±°λ‚˜ κ°™μœΌλ©°, 200보닀 μž‘κ±°λ‚˜ 같은 μ •μˆ˜μ΄κ³ , 이름은 μ•ŒνŒŒλ²³ λŒ€μ†Œλ¬Έμžλ‘œ 이루어져 있고, 길이가 100보닀 μž‘κ±°λ‚˜ 같은 λ¬Έμžμ—΄μ΄λ‹€. μž…λ ₯은 κ°€μž…ν•œ μˆœμ„œλ‘œ 주어진닀. 좜λ ₯ 첫째 쀄뢀터 총 N개의 쀄에 걸쳐 온라인 저지 νšŒμ›μ„ λ‚˜μ΄ 순, λ‚˜μ΄κ°€ κ°™μœΌλ©΄ κ°€μž…ν•œ 순으둜 ν•œ 쀄에 ν•œ λͺ…μ”© λ‚˜μ΄μ™€ 이름을 곡백으둜 ꡬ뢄해 좜λ ₯ν•œλ‹€. μ •λ ¬..

[λ°±μ€€] 1463번: 1둜 λ§Œλ“€κΈ° - C++

문제 μ •μˆ˜ X에 μ‚¬μš©ν•  수 μžˆλŠ” 연산은 λ‹€μŒκ³Ό 같이 μ„Έ 가지 이닀. Xκ°€ 3으둜 λ‚˜λˆ„μ–΄ 떨어지면, 3으둜 λ‚˜λˆˆλ‹€. Xκ°€ 2둜 λ‚˜λˆ„μ–΄ 떨어지면, 2둜 λ‚˜λˆˆλ‹€. 1을 λΊ€λ‹€. μ •μˆ˜ N이 μ£Όμ–΄μ‘Œμ„ λ•Œ, μœ„μ™€ 같은 μ—°μ‚° μ„Έ 개λ₯Ό 적절히 μ‚¬μš©ν•΄μ„œ 1을 λ§Œλ“€λ €κ³  ν•œλ‹€. 연산을 μ‚¬μš©ν•˜λŠ” 횟수의 μ΅œμ†Ÿκ°’μ„ 좜λ ₯ν•˜μ‹œμ˜€. μž…λ ₯ 첫째 쀄에 1보닀 ν¬κ±°λ‚˜ κ°™κ³ , 106보닀 μž‘κ±°λ‚˜ 같은 μ •μˆ˜ N이 주어진닀. 좜λ ₯ 첫째 쀄에 연산을 ν•˜λŠ” 횟수의 μ΅œμ†Ÿκ°’μ„ 좜λ ₯ν•œλ‹€. DPλ₯Ό μ΄μš©ν•˜μ—¬ ν’€ 수 μžˆλŠ” 문제. 1. N이 3으둜 λ‚˜λˆ„μ–΄ 떨어지면, 3으둜 λ‚˜λˆˆλ‹€ ➑️ D[N] = D[N/3] + 1 2. N이 2둜 λ‚˜λˆ„μ–΄ 떨어지면, 2둜 λ‚˜λˆˆλ‹€ ➑️ D[N] = D[N/2] + 1 3. 1을 λΊ€λ‹€ ➑️ D[N] = D[N - 1] + 1 κ·ΈλŸ¬λ‚˜ ..

[μ•Œκ³ λ¦¬μ¦˜] λ™μ κ³„νšλ²•(Dynamic Programming)

'μ½”λ”© ν…ŒμŠ€νŠΈλ₯Ό μœ„ν•œ 자료 ꡬ쑰와 μ•Œκ³ λ¦¬μ¦˜ with C++' λ₯Ό μ°Έκ³ ν•˜μ—¬ μž‘μ„±ν•˜μ˜€μŠ΅λ‹ˆλ‹€. 1. 동적 κ³„νšλ²• ; dynamic programming 1.1 κ°œλ… λΆ„ν•  정볡 νŒ¨λŸ¬λ‹€μž„ κ°œλ…μ„ ν™•μž₯ν•œ κ²ƒμœΌλ‘œ, 큰 문제λ₯Ό μž‘μ€ 문제둜 λ‚˜λˆ„μ–΄ ν‘ΈλŠ” 문제λ₯Ό μΌμ»«λŠ” 말이닀. μ–Έλœ» 문제λ₯Ό 보면 λΉ„μŠ·ν•˜λ‹€ 생각될 수 μžˆμ§€λ§Œ, λΆ„ν•  정볡과 κ΅¬λΆ„λ˜λŠ” 동적 κ³„νšλ²•λ§Œμ˜ νŠΉμ„±μ€ λ‹€μŒκ³Ό κ°™λ‹€. 1. μ€‘λ³΅λ˜λŠ” λΆ€λΆ„ 문제(overlapping subproblem) 2. 졜적 λΆ€λΆ„ ꡬ쑰(optimal substructure) λ‹€μŒκ³Ό 같은 속성을 λ§Œμ‘±ν•΄μ•Ό 동적 κ³„νšλ²•μ„ 톡해 문제λ₯Ό ν•΄κ²°ν•  수 μžˆλ‹€. 전체 λ¬Έμ œκ°€ 독립적인 λΆ€λΆ„ 문제둜 λ‚˜λ‰˜λŠ” λΆ„ν•  정볡 λ¬Έμ œμ™€ 달리 동적 κ³„νšλ²•μ—μ„œλŠ” μ€‘λ³΅λ˜λŠ” λΆ€λΆ„ λ¬Έμ œκ°€ 반볡적으둜 λ“±μž₯ν•œλ‹€. λ˜ν•œ 졜적 λΆ€λΆ„ ꡬ..

μ•Œκ³ λ¦¬μ¦˜ 2021. 7. 9. 16:06