λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

μ•Œκ³ λ¦¬μ¦˜24

파이썬 ν–‰λ ¬ κ³±μ…ˆ, κ±°λ“­μ œκ³± κ΅¬ν•˜κΈ° 파이썬 ν–‰λ ¬ μ•Œκ³ λ¦¬μ¦˜ 문제λ₯Ό ν’€ λ•Œ μ‹œκ°„ λ³΅μž‘λ„λ₯Ό 쀄이기 μœ„ν•΄ ν–‰λ ¬μ˜ κ±°λ“­μ œκ³±μ„ μ‚¬μš©ν•˜λŠ” κ²½μš°κ°€ μžˆμŠ΅λ‹ˆλ‹€. λŒ€ν‘œμ μœΌλ‘œ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ˜ κ°€μž₯ λΉ λ₯Έ μ‹œκ°„ λ³΅μž‘λ„κ°€ O(LogN)이 ν–‰λ ¬λ‘œ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€. ν”Όλ³΄λ‚˜μΉ˜μ™€ 행렬에 λŒ€ν•œ λ‚΄μš©μ€ μžμ„Έν•œ λ‚΄μš©μ€ μ•„λž˜ 링크λ₯Ό μ°Έμ‘°ν•΄μ£Όμ„Έμš”. [CS/μ•Œκ³ λ¦¬μ¦˜] - ν”Όλ³΄λ‚˜μΉ˜ 파이썬으둜 κ΅¬ν•˜λŠ” 3가지 μ•Œκ³ λ¦¬μ¦˜ ν”Όλ³΄λ‚˜μΉ˜ 파이썬으둜 κ΅¬ν•˜λŠ” 3가지 μ•Œκ³ λ¦¬μ¦˜ ν”Όλ³΄λ‚˜μΉ˜ 파이썬 3가지 μ•Œκ³ λ¦¬μ¦˜ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ€ μ•„λž˜μ˜ μˆ˜μ‹μ€ λ§Œμ‘±ν•˜λŠ” μˆ˜μ—΄μž…λ‹ˆλ‹€. λ°”λ‘œ 이전 μˆ«μžμ™€ κ·Έ μ „ 숫자의 합을 μ—°μ†ν•΄μ„œ κ΅¬ν•˜λŠ” μˆ˜μ—΄μ΄κ³  μ•„λž˜μ™€ 같이 μ§„ν–‰λ©λ‹ˆλ‹€. 이번 κΈ€μ—μ„œλŠ” myjamong.tistory.com μ΄λ ‡κ²Œ 가끔씩 ν–‰λ ¬μ˜ κ³±μ…ˆμ„ μ‚¬μš©ν•˜λŠ”λ°... 이게 자주 μ‚¬μš©ν•˜μ§€ μ•ŠλŠ” 3개의 μ€‘μ²©λœ for문을 μ‚¬μš©ν•˜λ‹€λ³΄λ‹ˆ.. 2021. 10. 21.
λ°±μ€€ 12865 파이썬 - ν‰λ²”ν•œ λ°°λ‚­ - 동적 κ³„νšλ²• λ°±μ€€ 12865 파이썬 https://www.acmicpc.net/problem/12865 12865번: ν‰λ²”ν•œ λ°°λ‚­ 첫 쀄에 λ¬Όν’ˆμ˜ 수 N(1 ≀ N ≀ 100)κ³Ό μ€€μ„œκ°€ 버틸 수 μžˆλŠ” 무게 K(1 ≀ K ≀ 100,000)κ°€ 주어진닀. 두 번째 쀄뢀터 N개의 쀄에 거쳐 각 물건의 무게 W(1 ≀ W ≀ 100,000)와 ν•΄λ‹Ή 물건의 κ°€μΉ˜ V(0 ≀ V ≀ 1,000) www.acmicpc.net 이번 λ¬Έμ œλŠ” 가방에 λ“€μ–΄κ°ˆ 수 μžˆλŠ” μ΅œλŒ€ λ¬΄κ²Œκ°€ μ •ν•΄μ Έ μžˆμ„ λ•Œ 넣을 수 μžˆλŠ” 물건의 μ΅œλŒ€ κ°€μΉ˜λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. 일단 μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” 문제이기 λ•Œλ¬Έμ— κ°€μž₯ λ¨Όμ € 동적 κ³„νšλ²•μ΄ λ– μ˜¬λžμŠ΅λ‹ˆλ‹€. λ©”λͺ¨μ΄μ œμ΄μ…˜μœΌλ‘œ μ‚¬μš©ν•  값을 가방에 λ“€μ–΄κ°€λŠ” 무게λ₯Ό μ€‘μ μœΌλ‘œ 두고 물건을 확인할 λ•Œ κ°€λ°©μ˜ μ΅œλŒ€ λ¬΄κ²ŒλΆ€ν„° 물건의 무게.. 2021. 10. 21.
λ°±μ€€ 1912 파이썬 - 연속합 - 동적 κ³„νšλ²• λ°±μ€€ 1912 파이썬 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 쀄에 μ •μˆ˜ n(1 ≀ n ≀ 100,000)이 주어지고 λ‘˜μ§Έ μ€„μ—λŠ” n개의 μ •μˆ˜λ‘œ 이루어진 μˆ˜μ—΄μ΄ 주어진닀. μˆ˜λŠ” -1,000보닀 ν¬κ±°λ‚˜ κ°™κ³ , 1,000보닀 μž‘κ±°λ‚˜ 같은 μ •μˆ˜μ΄λ‹€. www.acmicpc.net 10 -4 -3 1 5 6 -35 12 21 -1 = 33 2 1 -4 3 4 -4 6 5 -5 1 = 14 μœ„μ˜ μ˜ˆμ‹œμ™€ 같이 μ—°μ†λ˜λŠ” ν•©μ˜ μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. 이 λ¬Έμ œμ—μ„œ ν˜„μž¬μ˜ μœ„μΉ˜κ°€ 음수이고 이 음수λ₯Ό μ΄μ „κΉŒμ§€μ˜ μ—°μ†λœ 합에 ν•©ν–ˆμ„ λ•Œ 0보닀 큰지 ν™•μΈν•˜λŠ” 것이 핡심이닀. ν•©ν–ˆλŠ”λ° 0보닀 μž‘μ€ 경우.. μ΅œλŒ€κ°’μ΄ μ΄μ–΄κ°ˆ 수 μ—†λ‹€. λ°˜λŒ€λ‘œ... ν•©ν–ˆλŠ”λ° 0보닀 큰 μˆ˜κ°€ λ‚˜μ˜€λ©΄... 2021. 10. 19.
λ°±μ€€ 9251 파이썬 - LCS - 동적 κ³„νšλ²• λ°±μ€€ 9251 파이썬 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 졜μž₯ 곡톡 λΆ€λΆ„ μˆ˜μ—΄)λ¬Έμ œλŠ” 두 μˆ˜μ—΄μ΄ μ£Όμ–΄μ‘Œμ„ λ•Œ, λͺ¨λ‘μ˜ λΆ€λΆ„ μˆ˜μ—΄μ΄ λ˜λŠ” μˆ˜μ—΄ 쀑 κ°€μž₯ κΈ΄ 것을 μ°ΎλŠ” λ¬Έμ œμ΄λ‹€. 예λ₯Ό λ“€μ–΄, ACAYKP와 CAPCAK의 LCSλŠ” ACAKκ°€ λœλ‹€. www.acmicpc.net 이번 λ¬Έμ œλŠ” λ‘κ°œμ˜ λ¬Έμžμ—΄μ΄ μ£Όμ–΄μ‘Œμ„ λ•Œ LCS(Longest Common Subsequence, 졜μž₯ 곡톡 λΆ€λΆ„ μˆ˜μ—΄)λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œλ‹€. 예λ₯Ό λ“€μ–΄ ACAYKP CAPCAK LCSλŠ” ACAK 이닀. 이전에 ν’€μ—ˆλ˜ 동적 κ³„νšλ²•μ΄λž‘μ€ 쑰금 λ‹€λ₯΄κ²Œ 2차원 λ°°μ—΄μ˜ μΊμ‹œλ₯Ό λ§Œλ“€μ–΄μ„œ ν•΄κ²°ν•  수 있고... λˆ„μ  값을 κ΅¬ν•΄μ„œ ν•΄κ²°ν•  μˆ˜λ„ μžˆλ‹€... 2021. 10. 18.
λ°±μ€€ 2565 파이썬 - 전깃쀄 - 동적 κ³„νšλ²•, LIS λ°±μ€€ 2565 파이썬 https://www.acmicpc.net/problem/2565 2565번: 전깃쀄 첫째 μ€„μ—λŠ” 두 μ „λ΄‡λŒ€ μ‚¬μ΄μ˜ μ „κΉƒμ€„μ˜ κ°œμˆ˜κ°€ 주어진닀. μ „κΉƒμ€„μ˜ κ°œμˆ˜λŠ” 100 μ΄ν•˜μ˜ μžμ—°μˆ˜μ΄λ‹€. λ‘˜μ§Έ 쀄뢀터 ν•œ 쀄에 ν•˜λ‚˜μ”© 전깃쀄이 Aμ „λ΄‡λŒ€μ™€ μ—°κ²°λ˜λŠ” μœ„μΉ˜μ˜ λ²ˆν˜Έμ™€ Bμ „λ΄‡λŒ€μ™€ μ—°κ²°λ˜λŠ” www.acmicpc.net 이번 λ¬Έμ œλŠ” 전깃쀄이 μ„œλ‘œ κ΅μ°¨ν•˜μ§€ μ•Šκ²Œ μ—†μ• μ•Όν•˜λŠ” μ „κΉƒμ€„μ˜ μ΅œμ†Œ 개수λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. μ²˜μŒμ— 문제λ₯Ό μ–΄λ–»κ²Œ 접근해야할지 λͺ¨λ₯΄κ² λ‹€κ³  μƒκ°ν–ˆλŠ”λ°... μ—­μ‹œ μ•Œκ³ λ¦¬μ¦˜μ€ 쒅이에 μ μ–΄κ°€λ©΄μ„œ 경우의 수λ₯Ό μ°Ύλ‹€λ³΄λ‹ˆ κ·œμΉ™μ„ μ°Ύμ•˜μŠ΅λ‹ˆλ‹€. 이 λ¬Έμ œλ„ 이전에 ν’€μ—ˆλ˜ LIS 문제 : [CS/μ•Œκ³ λ¦¬μ¦˜] - λ°±μ€€ 11053 파이썬 - κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄ - 동적 κ³„νšλ²•, LIS 의 μ—°μž₯μ„  μ‘μš©.. 2021. 10. 15.
λ°±μ€€ 11054 파이썬 - κ°€μž₯ κΈ΄ 바이토닉 λΆ€λΆ„ μˆ˜μ—΄ - 동적 κ³„νšλ²•, LIS λ°±μ€€ 11054 파이썬 https://www.acmicpc.net/problem/11054 11054번: κ°€μž₯ κΈ΄ 바이토닉 λΆ€λΆ„ μˆ˜μ—΄ 첫째 쀄에 μˆ˜μ—΄ A의 크기 N이 주어지고, λ‘˜μ§Έ μ€„μ—λŠ” μˆ˜μ—΄ Aλ₯Ό 이루고 μžˆλŠ” Aiκ°€ 주어진닀. (1 ≀ N ≀ 1,000, 1 ≀ Ai ≀ 1,000) www.acmicpc.net 이번 λ¬Έμ œλŠ” 이전에 ν’€μ—ˆλ˜ [CS/μ•Œκ³ λ¦¬μ¦˜] - λ°±μ€€ 11053 파이썬 - κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄ - 동적 κ³„νšλ²•, LIS 문제의 μ‘μš©μ΄λ‹€. 바이토닉 λΆ€λΆ„ μˆ˜μ—΄μ„ κ°€μž₯ κΈ΄ μ¦κ°€ν•˜κ³  κ°μ†Œν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ΄λ‹€. 즉 이전에 ν’€μ—ˆλ˜ LIS λ¬Έμ œμ—μ„œ λ°°μ—΄μ˜ 각 μœ„μΉ˜μ—μ„œμ˜ μ΅œλŒ€ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ„ 주어진 λ°°μ—΄κ³Ό 주어진 배열을 뒀집은 λ°°μ—΄ 2가지λ₯Ό κ΅¬ν•΄μ„œ ν•΄κ²°ν•  수 μžˆλ‹€. Python 풀이 impor.. 2021. 10. 15.
λ°±μ€€ 11053 파이썬 - κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄ - 동적 κ³„νšλ²•, LIS λ°±μ€€ 11053 파이썬 https://www.acmicpc.net/problem/11053 11053번: κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄ μˆ˜μ—΄ Aκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. 예λ₯Ό λ“€μ–΄, μˆ˜μ—΄ A = {10, 20, 10, 30, 20, 50} 인 κ²½μš°μ— κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ€ A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이번 λ¬Έμ œλŠ” μˆ˜μ—΄μ˜ κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄μ˜ 길이λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. LIS(Longest Increasing Subsequence)라고 ν•œλ‹€. AλΌλŠ” μˆ˜μ—΄ {10, 20, 10, 30, 20, 50}이 μžˆλ‹€λ©΄ {10, 20, 10, 30, 20, 50}이 κ°€μž₯ κΈ΄ λΆ€λΆ„ μˆ˜μ—΄μ΄λ‹€. 이번 문제.. 2021. 10. 13.
λ°±μ€€ 2156 파이썬 - 포도주 μ‹œμ‹ - 동적 κ³„νšλ²• λ°±μ€€ 2156 파이썬 https://www.acmicpc.net/problem/2156 2156번: 포도주 μ‹œμ‹ νš¨μ£ΌλŠ” 포도주 μ‹œμ‹νšŒμ— κ°”λ‹€. κ·Έ 곳에 κ°”λ”λ‹ˆ, ν…Œμ΄λΈ” μœ„μ— λ‹€μ–‘ν•œ 포도주가 λ“€μ–΄μžˆλŠ” 포도주 μž”μ΄ 일렬둜 놓여 μžˆμ—ˆλ‹€. νš¨μ£ΌλŠ” 포도주 μ‹œμ‹μ„ ν•˜λ €κ³  ν•˜λŠ”λ°, μ—¬κΈ°μ—λŠ” λ‹€μŒκ³Ό 같은 두 가지 규 www.acmicpc.net ν•΄λ‹Ή λ¬Έμ œλŠ” 주어진 쑰건에 μ˜ν•΄ κ°€μž₯ λ§Žμ€ μ–‘μ˜ 포도주λ₯Ό μ‹œμ‹ν•˜λŠ” 방법을 κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€. ν¬λ„μ£Όμ˜ μž”μ„ μ„ νƒν•˜λ©΄ λͺ¨λ‘ λ§ˆμ…”μ•Όν•œλ‹€. μ—°μ†μœΌλ‘œ 놓여 μžˆλŠ” 3μž”μ„ λͺ¨λ‘ λ§ˆμ‹€ 수 μ—†λ‹€. [CS/μ•Œκ³ λ¦¬μ¦˜] - λ°±μ€€ 2579 파이썬 - 계단 였λ₯΄κΈ° - 동적 κ³„νšλ²• λ¬Έμ œμ™€ μœ μ‚¬ν•œ 문제인데 차이가 μžˆλ‹€λ©΄ κ°€μž₯ λ§ˆμ§€λ§‰ μž”μ„ κΌ­ λ§ˆμ‹œμ§€ μ•Šμ•„λ„ λœλ‹€λŠ” κ²ƒμž…λ‹ˆλ‹€. 즉, μ΅œλŒ€κ°’μ„ ꡬ할 λ•Œ 쑰건이 .. 2021. 10. 10.
λ°±μ€€ 10844 파이썬 - μ‰¬μš΄ 계단 수 - 동적 κ³„νšλ²• λ°±μ€€ 10844 파이썬 https://www.acmicpc.net/problem/10844 10844번: μ‰¬μš΄ 계단 수 첫째 쀄에 정닡을 1,000,000,000으둜 λ‚˜λˆˆ λ‚˜λ¨Έμ§€λ₯Ό 좜λ ₯ν•œλ‹€. www.acmicpc.net 이번 λ¬Έμ œλŠ” 계단 수λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. 계단 μˆ˜λŠ” "45656" 처럼 숫자의 자릿수 λ§ˆλ‹€ ν•˜λ‚˜ μ”© 쀄고 λŠ˜μ–΄λ‚˜λŠ” 수λ₯Ό λ§ν•œλ‹€. 0으둜 μ‹œμž‘ν•  수 μ—†μœΌλ©° 90은 계단 μˆ˜κ°€ μ•„λ‹ˆλ‹€. 이런 쑰건으둜 μ•„λž˜μ™€ 같은 κ·œμΉ™μ΄ λ§Œλ“€μ–΄ 진닀. 0 λ‹€μŒμ—λŠ” 1만 올 수 μžˆλ‹€. 9 λ‹€μŒμ—λŠ” 8만 올 수 μžˆλ‹€. λ‚˜λ¨Έμ§€ μˆ«μžμ— λŒ€ν•΄μ„œλŠ” μ•žλ’€ λͺ¨λ‘ 올 수 μžˆλ‹€. 동적 κ³„νšλ²•μœΌλ‘œ 숫자의 길이에 따라 λ§Œλ“€ 수 μžˆλŠ” 숫자의 갯수λ₯Ό μ €μž₯ν•˜λŠ”λ°... 각 숫자의 끝자리λ₯Ό κΈ°μ€€μœΌλ‘œ κΈ°μ–΅ν•  수 μžˆλŠ” λ©”λͺ¨μ΄μ œμ΄μ…˜ 리슀트λ₯Ό 생성.. 2021. 10. 10.
λ°±μ€€ 2579 파이썬 - 계단 였λ₯΄κΈ° - 동적 κ³„νšλ²• λ°±μ€€ 2579 파이썬 https://www.acmicpc.net/problem/2579 2579번: 계단 였λ₯΄κΈ° 계단 였λ₯΄κΈ° κ²Œμž„μ€ 계단 μ•„λž˜ μ‹œμž‘μ λΆ€ν„° 계단 κΌ­λŒ€κΈ°μ— μœ„μΉ˜ν•œ λ„μ°©μ κΉŒμ§€ κ°€λŠ” κ²Œμž„μ΄λ‹€. κ³Ό 같이 각각의 κ³„λ‹¨μ—λŠ” μΌμ •ν•œ μ μˆ˜κ°€ μ“°μ—¬ μžˆλŠ”λ° 계단을 밟으면 κ·Έ 계단에 μ“°μ—¬ μžˆλŠ” 점 www.acmicpc.net 이번 λ¬Έμ œλŠ” 쑰건에 λ§žμΆ°μ„œ 계단을 였λ₯΄λ©΄μ„œ μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€. 계단은 ν•œλ²ˆμ— 1~2 계단씩 였λ₯Ό 수 μžˆλ‹€. μ‹œμž‘μ μ€ ν¬ν•¨ν•˜μ§€ μ•Šκ³ ... μ—°μ†λœ 3개의 계단은 λ°Ÿμ„ 수 μ—†λ‹€. 즉, μ΅œλŒ€ 2개 κ³„λ‹¨κΉŒμ§€ μ—°μ†μœΌλ‘œ λ°Ÿμ„ 수 μžˆλ‹€. λ§ˆμ§€λ§‰ κ³„λ‹¨μ—λŠ” λ°˜λ“―μ΄ λ„μ°©ν•΄μ•Όν•œλ‹€. 동적 κ³„νšλ²•μ„ μ‚¬μš©ν•˜λ©΄ ν˜„μž¬ μœ„μΉ˜μ˜ μ΅œλŒ€κ°’μ„ μ €μž₯ν•˜λ©΄μ„œ κ°€κΈ° λ•Œλ¬Έμ—... 3번 μ§Έ 쑰건은 크게 κ±±μ •ν•  것 μ—†κ³ ... 문제.. 2021. 10. 10.
λ°±μ€€ 1932 파이썬 - μ •μˆ˜μ‚Όκ°ν˜• - 동적 κ³„νšλ²• λ°±μ€€ 1932 파이썬 https://www.acmicpc.net/problem/1932 1932번: μ •μˆ˜ μ‚Όκ°ν˜• 첫째 쀄에 μ‚Όκ°ν˜•μ˜ 크기 n(1 ≀ n ≀ 500)이 주어지고, λ‘˜μ§Έ 쀄뢀터 n+1번째 μ€„κΉŒμ§€ μ •μˆ˜ μ‚Όκ°ν˜•μ΄ 주어진닀. www.acmicpc.net κ°€μž₯ μƒλ‹¨μ—μ„œ 쒌우둜만 μ΄λ™ν•˜λ©΄μ„œ 수의 합이 μ΅œλŒ€κ°€ λ˜λŠ” 경둜의 μ΅œμ’… 합을 κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€. ν•΄λ‹Ή λ¬Έμ œλŠ” μ–‘μͺ½ 끝의 숫자λ₯Ό μ œμ™Έν•˜κ³  이전 μΈ΅μ—μ„œ 인덱슀... i-1κ³Ό i의 μœ„μΉ˜λ₯Ό λ”ν•œ 값을 μΊμ‹œκ°’μœΌλ‘œ μ €μž₯ν•΄μ„œ κ°€μž₯ λ§ˆμ§€λ§‰ 측의 μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λ©΄ λœλ‹€. μœ„μ˜ μ˜ˆμ‹œμ—μ„œ λ©”λͺ¨μ΄μ œμ΄μ…˜μ„ 톡해 μ΅œμ’…μ μœΌλ‘œ μ–»λŠ” μΊμ‹œκ°’μ€ μ•„λž˜μ™€ 같을 것이닀. Python 풀이 1 import sys read = sys.stdin.readline n = int(read()) c.. 2021. 10. 10.
λ°±μ€€ 1149 파이썬 - RGB거리 - 동적 κ³„νšλ²• λ°±μ€€ 1149 파이썬 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 쀄에 μ§‘μ˜ 수 N(2 ≀ N ≀ 1,000)이 주어진닀. λ‘˜μ§Έ 쀄뢀터 N개의 μ€„μ—λŠ” 각 집을 λΉ¨κ°•, 초둝, νŒŒλž‘μœΌλ‘œ μΉ ν•˜λŠ” λΉ„μš©μ΄ 1번 집뢀터 ν•œ 쀄에 ν•˜λ‚˜μ”© 주어진닀. 집을 μΉ ν•˜λŠ” λΉ„μš©μ€ 1,000보닀 μž‘κ±°λ‚˜ www.acmicpc.net 이번 λ¬Έμ œλŠ” 2차원 λ°°μ—΄μ—μ„œ μ•žλ’€λ‘œ 인덱슀 λ²ˆν˜Έκ°€ λ‹€λ₯΄κ²Œν•΄μ„œ ν•©μ‚°ν•œκ²Œ κ°€μž₯ 적은 값을 κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.이런 μ΅œμ†Œλ‚˜ μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œλŠ” κ°€μž₯ λ¨Όμ € 동적 κ³„νšλ²•μ΄ λ– μ˜€λ₯Έλ‹€. 그런데... λ§Œμ•½... κ°€μž₯ 적은 λΉ„μš©λ§Œ μ €μž₯ν•˜κ² λ‹€λŠ” 생각에 쀑점을 두면... μ•„λž˜μ™€ 같은 μ˜ˆμ™Έμ‚¬ν•­μ΄ λ°œμƒν•  수 μžˆλ‹€. 이전에 κ°€μž₯ 적은 λΉ„μš©λ§Œ κ³ λ €ν•˜λ©΄.... μœ„μ™€ 같이 λΉ„μš©μ΄ 같은.. 2021. 10. 10.
λ°±μ€€ 9461 파이썬 - νŒŒλ„λ°˜ μˆ˜μ—΄ - 동적 κ³„νšλ²• https://www.acmicpc.net/problem/9461 9461번: νŒŒλ„λ°˜ μˆ˜μ—΄ 였λ₯Έμͺ½ κ·Έλ¦Όκ³Ό 같이 μ‚Όκ°ν˜•μ΄ λ‚˜μ„  λͺ¨μ–‘μœΌλ‘œ 놓여져 μžˆλ‹€. 첫 μ‚Όκ°ν˜•μ€ μ •μ‚Όκ°ν˜•μœΌλ‘œ λ³€μ˜ κΈΈμ΄λŠ” 1이닀. κ·Έ λ‹€μŒμ—λŠ” λ‹€μŒκ³Ό 같은 κ³Όμ •μœΌλ‘œ μ •μ‚Όκ°ν˜•μ„ 계속 μΆ”κ°€ν•œλ‹€. λ‚˜μ„ μ—μ„œ κ°€μž₯ κΈ΄ λ³€μ˜ www.acmicpc.net ν”Όλ³΄λ‚˜μΉ˜μ™€ λΉ„μŠ·ν•˜κ²Œ κ·œμΉ™μ΄ μžˆλŠ” νŒŒλ„λ°˜ μˆ˜μ—΄μ˜ N번째 값을 κ΅¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ λ¬Έμ œμž…λ‹ˆλ‹€. μœ„μ˜ 그림을 보면 μ•Œ 수 μžˆλ“―μ΄... μ •μ‚Όκ°ν˜•μ˜ 변을 따라 계속 λŠ˜λ €κ°€λŠ”λ°... μ •μ‚Όκ°ν˜•μ˜ λ³€μ˜ 길이가 μˆ˜μ—΄μ˜ κ°’μœΌλ‘œ λ“€μ–΄κ°„λ‹€. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16... κ°€μž₯ 핡심은 νŒŒλ„λ°˜ μˆ˜μ—΄μ˜ κ·œμΉ™μ„ μ°ΎλŠ” κ²ƒμ΄μ—ˆμŠ΅λ‹ˆλ‹€. μœ„μ˜ κ·œμΉ™μ„ 기반으둜 ν•˜κ³  μžˆμŠ΅λ‹ˆλ‹€. 근데 쑰건으둜 n이 8보닀.. 2021. 10. 8.
λ°±μ€€ 1904 파이썬 - 01타일 - 동적 κ³„νšλ²•, ν–‰λ ¬ λ°±μ€€ 1904 파이썬 https://www.acmicpc.net/problem/1904 1904번: 01타일 μ§€μ›μ΄μ—κ²Œ 2진 μˆ˜μ—΄μ„ κ°€λ₯΄μ³ μ£ΌκΈ° μœ„ν•΄, 지원이 μ•„λ²„μ§€λŠ” κ·Έμ—κ²Œ 타일듀을 μ„ λ¬Όν•΄μ£Όμ…¨λ‹€. 그리고 이 각각의 타일듀은 0 λ˜λŠ” 1이 μ“°μ—¬ μžˆλŠ” λ‚±μž₯의 타일듀이닀. μ–΄λŠ λ‚  짓ꢂ은 동주가 지원이 www.acmicpc.net ν•΄λ‹Ή λ¬Έμ œλŠ”... "00" 타일과 "1" νƒ€μΌλ‘œ λ§Œλ“€ 수 μžˆλŠ” μ΄μ§„μˆ˜μ˜ κ°€μ§“μˆ˜λ₯Ό μ°ΎλŠ” λ¬Έμ œμž…λ‹ˆλ‹€. 이 λ¬Έμ œλ„ κ²°κ΅­ 1타일과 00타일을 μ΄μ „μ˜ νƒ€μž…μ— λΆ™μΉ˜λŠ” λ¬Έμ œμ΄λ―€λ‘œ λ©”λͺ¨μ΄μ œμ΄μ…˜μ„ μ΄μš©ν•œ λ™μ κ³„νšλ²•μœΌλ‘œ ν’€ 수 μžˆλ‹€. 그런데... 직접 μ†μœΌλ‘œ 숫자의 νŒ¨ν„΄μ„ κ³„μ‚°ν•΄λ³΄λ‹ˆ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄κ³Ό μ™„μ Ό λ™μΌν•œ 숫자의 νŒ¨ν„΄μ„ κ°–κ³  μžˆμ—ˆμŠ΅λ‹ˆλ‹€. κ·Έλž˜μ„œ 이 λ¬Έμ œλŠ” ν–‰λ ¬ 멱법을 μ‚¬μš©ν•΄μ„œ ν•΄κ²°ν•  수 μžˆμ—ˆμŠ΅.. 2021. 10. 8.
ν”Όλ³΄λ‚˜μΉ˜ 파이썬으둜 κ΅¬ν•˜λŠ” 3가지 μ•Œκ³ λ¦¬μ¦˜ ν”Όλ³΄λ‚˜μΉ˜ 파이썬 3가지 μ•Œκ³ λ¦¬μ¦˜ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ€ μ•„λž˜μ˜ μˆ˜μ‹μ€ λ§Œμ‘±ν•˜λŠ” μˆ˜μ—΄μž…λ‹ˆλ‹€. λ°”λ‘œ 이전 μˆ«μžμ™€ κ·Έ μ „ 숫자의 합을 μ—°μ†ν•΄μ„œ κ΅¬ν•˜λŠ” μˆ˜μ—΄μ΄κ³  μ•„λž˜μ™€ 같이 μ§„ν–‰λ©λ‹ˆλ‹€. 이번 κΈ€μ—μ„œλŠ” μ‹œκ°„ λ³΅μž‘λ„μ— λ”°λ₯Έ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ κ΅¬ν•˜λŠ” λŒ€ν‘œμ μΈ 3가지 μ•Œκ³ λ¦¬μ¦˜μ— λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ„λ‘ ν•˜κ² μŠ΅λ‹ˆλ‹€. μž¬κ·€ν•¨μˆ˜ 이용 - μ‹œκ°„λ³΅μž‘λ„ O(n^2) 동적 κ³„νšλ²• 이용 - μ‹œκ°„λ³΅μž‘λ„ O(n) ν–‰λ ¬ 멱법 이용 - μ‹œκ°„λ³΅μž‘λ„ O(log n) μž¬κ·€ν•¨μˆ˜ 이용 첫번 μ§Έ 방법은 μž¬κ·€ν•¨μˆ˜λ₯Ό μ΄μš©ν•˜λŠ” λ°©λ²•μž…λ‹ˆλ‹€. def fibo(n): if n in (1,2): return 1 return fibo(n-1) + fibo(n-2) print(fibo(8)) κ°€μž₯ κ°„λ‹¨ν•œ λ°©λ²•μ΄μ§€λ§Œ... μž¬κ·€λ‘œ λ‘κ°œμ˜ λΆ„κΈ°κ°€ κ³„μ†ν•΄μ„œ 생기기 λ•Œλ¬Έμ— μ‹œκ°„λ³΅μž‘λ„κ°€ O(.. 2021. 10. 8.
λ°±μ€€ 9184 파이썬 - μ‹ λ‚˜λŠ” ν•¨μˆ˜ μ‹€ν–‰ - 동적 κ³„νšλ²• λ°±μ€€ 9184 파이썬 https://www.acmicpc.net/problem/9184 9184번: μ‹ λ‚˜λŠ” ν•¨μˆ˜ μ‹€ν–‰ μž…λ ₯은 μ„Έ μ •μˆ˜ a, b, c둜 이루어져 있으며, ν•œ 쀄에 ν•˜λ‚˜μ”© 주어진닀. μž…λ ₯의 λ§ˆμ§€λ§‰μ€ -1 -1 -1둜 λ‚˜νƒ€λ‚΄λ©°, μ„Έ μ •μˆ˜κ°€ λͺ¨λ‘ -1인 κ²½μš°λŠ” μž…λ ₯의 λ§ˆμ§€λ§‰μ„ μ œμ™Έν•˜λ©΄ μ—†λ‹€. www.acmicpc.net λ¬Έμ œμ—μ„œ μœ„μ™€ 같은 쑰건의 μž¬κ·€ν•¨μˆ˜κ°€ μ£Όμ–΄μ§€λŠ”λ°... ν•΄λ‹Ή μž¬κ·€λ₯Ό κ·ΈλŒ€λ‘œ μ‹€ν–‰ν•˜λ©΄ 값을 κ΅¬ν•˜λŠ”λ° λ„ˆλ¬΄ 였래 κ±Έλ¦°λ‹€κ³  ν•œλ‹€. 동적 κ³„νšλ²•μ˜ 기원? 동적 κ³„νšλ²•μ΄λž€ μ•Œκ³ λ¦¬μ¦˜μ΄ μƒκ²¨λ‚˜κ²Œ 된 배경이... λΆ„ν• μ •λ³΅μ—μ„œ μž‘μ—…λ“€μ„ μͺΌκ°œμ„œ ν•  λ•Œ μ€‘λ³΅λ˜μ„œ ν•˜λŠ” μž‘μ—…μ΄ λ§Žμ€ 문제λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄ λ§Œλ“€μ–΄μ‘Œλ‹€κ³  ν•©λ‹ˆλ‹€. κ·Έλž˜μ„œ μž¬κ·€ν•¨μˆ˜μ™€ 같이 뎁슀λ₯Ό 타고 λ‚΄λ €κ°€μ„œ 값을 ꡬ할 λ•Œ... κ³„μ‚°ν•œ 값을 쀑.. 2021. 10. 7.
λ°±μ€€ 1003 파이썬 - ν”Όλ³΄λ‚˜μΉ˜ ν•¨μˆ˜ - 동적 κ³„νšλ²• λ°±μ€€ 1003 파이썬 https://www.acmicpc.net/problem/1003 1003번: ν”Όλ³΄λ‚˜μΉ˜ ν•¨μˆ˜ 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€λ§ˆλ‹€ 0이 좜λ ₯λ˜λŠ” νšŸμˆ˜μ™€ 1이 좜λ ₯λ˜λŠ” 횟수λ₯Ό 곡백으둜 κ΅¬λΆ„ν•΄μ„œ 좜λ ₯ν•œλ‹€. www.acmicpc.net μž¬κ·€λ₯Ό ν†΅ν•œ ν”Όλ³΄λ‚˜μΉ˜λ₯Ό κ΅¬ν•˜κ³  0κ³Ό 1κΉŒμ§€ 내렀갔을 λ•Œ 0κ³Ό 1을 좜λ ₯ν•΄μ£ΌλŠ” ν•¨μˆ˜κ°€ 주어진닀. μ΄λ•Œ 0κ³Ό 1을 좜λ ₯ν•œ 횟수λ₯Ό κ΅¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ λ¬Έμ œμ΄λ‹€. ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ„ μž¬κ·€λ‘œ 주둜 κ΅¬ν˜„ν•˜λŠ”λ°... 동적 κ³„νšλ²•μœΌλ‘œλ„ μΆ©λΆ„νžˆ κ°€λŠ₯ν•˜λ‹€. 특히 이번 λ¬Έμ œμ—μ„œλŠ” 좜λ ₯λ˜λŠ” κ²°κ³Όλ₯Ό κ΅¬ν•˜λŠ” 것이기 λ•Œλ¬Έμ—.... 숫자 Nμ—λŒ€ν•΄μ„œ N-1κ³Ό N-2 λ²ˆμ§Έμ— 좜λ ₯ν•œ 0κ³Ό 1의 수λ₯Ό ν•©μ‚°ν•˜λ©΄ κ²°κ³Όλ₯Ό 얻을 수 μžˆλ‹€. Python 풀이 import sys read = sys.stdin.readline.. 2021. 10. 7.
λ°±μ€€ 9095 파이썬 - 1,2,3 λ”ν•˜κΈ° - 동적 κ³„νšλ²•, DFS λ°±μ€€ 9095 파이썬 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 λ”ν•˜κΈ° 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€λ§ˆλ‹€, n을 1, 2, 3의 ν•©μœΌλ‘œ λ‚˜νƒ€λ‚΄λŠ” λ°©λ²•μ˜ 수λ₯Ό 좜λ ₯ν•œλ‹€. www.acmicpc.net μ •μˆ˜ n이 μ£Όμ–΄μ‘Œμ„ λ•Œ, n을 1,2,3의 ν•©μœΌλ‘œ λ‚˜νƒ€λ‚΄λŠ” λ°©λ²•μ˜ 수λ₯Ό κ΅¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ λ¬Έμ œμž…λ‹ˆλ‹€. 단, μœ„μΉ˜μ˜ μ€‘λ³΅κΉŒμ§€ κ°€λŠ₯ν•œ μ‘°κ±΄μž…λ‹ˆλ‹€. 예λ₯Ό λ“€μ–΄ 4λΌλŠ” μ •μˆ˜λ₯Ό λ§Œλ“€ λ•Œ 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 μ΄λ ‡κ²Œ μœ„μΉ˜μ˜ μ€‘λ³΅κΉŒμ§€ κ°€λŠ₯ν•œ 쑰건 μž…λ‹ˆλ‹€. 이 λ¬Έμ œλŠ” 동적 κ³„νšλ²•μ„ κ³΅λΆ€ν•˜κΈ° μœ„ν•΄ 풀은 λ¬Έμ œμΈλ°μš”... 문제λ₯Ό ν•΄κ²°ν•˜λŠ” 방법을 κ³ λ―Όν•΄ λ³΄λ©΄μ„œ DFSλ₯Ό μ‚¬μš©ν•˜κ³  μ‹Άλ‹€λŠ” 생각이 많이 λ“€μ—ˆμ–΄μš”. μˆœμ—΄μ΄λ‚˜ 쑰합을 ꡬ할 λ•Œ DFSλ₯Ό μ‚¬μš©ν•΄μ„œ .. 2021. 10. 7.
λ°±μ€€ 1463 파이썬 - 1둜 λ§Œλ“€κΈ° - 동적 κ³„νšλ²• λ°±μ€€ 1463 파이썬 https://www.acmicpc.net/problem/1463 1463번: 1둜 λ§Œλ“€κΈ° 첫째 쀄에 1보닀 ν¬κ±°λ‚˜ κ°™κ³ , 106보닀 μž‘κ±°λ‚˜ 같은 μ •μˆ˜ N이 주어진닀. www.acmicpc.net μ •μˆ˜ Xκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ 3으둜 λ‚˜λˆ„μ–΄ 떨어지면 3으둜 λ‚˜λˆ„κ³  2둜 λ‚˜λˆ„μ–΄ 떨어지면 2둜 λ‚˜λˆ„κ³  κ·Έ μ΄μ™ΈλŠ” 1을 λΊ€λ‹€. ν•΄λ‹Ή κ·œμΉ™μ— λ§žμΆ°μ„œ μ—°μ‚° 횟수의 μ΅œμ†Ÿκ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. 문제λ₯Ό 보고 λ”± 생각이 λ‚œ μ•Œκ³ λ¦¬μ¦˜μ΄ 동적 κ³„νšλ²•μ΄μ—ˆμŠ΅λ‹ˆλ‹€. μ΄ˆκΈ°κ°’μœΌλ‘œ μ„€μ •ν•  값이 λͺ…ν™•ν–ˆκ³  기쑴에 μ—°μ‚°λœ 값을 μž¬μ‚¬μš©ν•˜λŠ” λ©”λͺ¨μ΄μ œμ΄μ…˜μ΄ λ”± λ§žμ•„ λ–¨μ–΄μ‘Œλ‹€. Python 풀이 1 import sys read = sys.stdin.readline N = int(read()) cache = [-1] * (N+3) cac.. 2021. 10. 6.
λ°±μ€€ 2839 파이썬 - 섀탕 배달 - 동적 κ³„νšλ²• λ°±μ€€ 2839 파이썬 https://www.acmicpc.net/problem/2839 2839번: 섀탕 배달 μƒκ·Όμ΄λŠ” μš”μ¦˜ 섀탕곡μž₯μ—μ„œ 섀탕을 λ°°λ‹¬ν•˜κ³  μžˆλ‹€. μƒκ·Όμ΄λŠ” μ§€κΈˆ μ‚¬νƒ•κ°€κ²Œμ— 섀탕을 μ •ν™•ν•˜κ²Œ Nν‚¬λ‘œκ·Έλž¨μ„ 배달해야 ν•œλ‹€. 섀탕곡μž₯μ—μ„œ λ§Œλ“œλŠ” 섀탕은 봉지에 담겨져 μžˆλ‹€. λ΄‰μ§€λŠ” 3ν‚¬λ‘œκ·Έ www.acmicpc.net Nν‚¬λ‘œκ·Έλž¨μ˜ 섀탕이 μ£Όμ–΄μ‘Œμ„ λ•Œ, 섀탕을 λ‹΄κΈ° μœ„ν•΄ 3ν‚€λ‘œκ·Έλž¨κ³Ό 5ν‚€λ‘œκ·Έλž¨ λ΄‰μ§€λ‘œ κ°€μž₯ 적은 μ–‘μ˜ 봉지λ₯Ό λ§Œλ“€μ–΄ λ‚΄λŠ” 방법을 κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€. 이 λ¬Έμ œλŠ” 계산 횟수λ₯Ό 쀄이기 μœ„ν•΄ 이전에 κ³„μ‚°ν–ˆλ˜ 값을 κΈ°μ–΅ν•΄λ’€λ‹€κ°€ μž¬μ‚¬μš©ν•˜λŠ” λ©”λͺ¨μ΄μ œμ΄μ…˜μ„ ν™œμš©ν•˜λŠ” 것이 μ λ‹Ήν•˜λ‹€κ³  νŒλ‹¨ν–ˆμŠ΅λ‹ˆλ‹€. 3 ~ Nν‚¬λ‘œκ·Έλž¨κΉŒμ§€ μž‘μ€ μˆ«μžλΆ€ν„°... 각각 κ°€μž₯ 적은 μ–‘μ˜ 봉지λ₯Ό μ €μž₯해두면... ν•΄λ‹Ή 값보닀 3, 5 큰 .. 2021. 10. 5.